Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.compression > #1899 > unrolled thread

Kolmogorov compression?

Back to article view | Back to comp.compression

Contents

  Kolmogorov compression? Industrial One <industrial_one@hotmail.com> - 2013-04-29 12:14 -0700
    Re: Kolmogorov compression? Thomas Richter <thor@math.tu-berlin.de> - 2013-04-29 23:03 +0200
      Re: Kolmogorov compression? Industrial One <industrial_one@hotmail.com> - 2013-04-29 14:30 -0700
        Re: Kolmogorov compression? Thomas Richter <thor@math.tu-berlin.de> - 2013-04-30 00:28 +0200
        Re: Kolmogorov compression? "George Johnson" <matrix29@charter.net> - 2013-04-29 22:41 -0400
    Re: Kolmogorov compression? Ernst <Ernst_Berg@sbcglobal.net> - 2013-05-01 19:32 -0700
      Re: Kolmogorov compression? jacko <jackokring@gmail.com> - 2013-05-08 18:34 -0700
        Re: Kolmogorov compression? Thomas Richter <thor@math.tu-berlin.de> - 2013-05-09 21:17 +0200
          Re: Kolmogorov compression? jacko <jackokring@gmail.com> - 2013-05-09 15:52 -0700
            Re: Kolmogorov compression? jacko <jackokring@gmail.com> - 2013-05-09 17:08 -0700
            Re: Kolmogorov compression? Thomas Richter <thor@math.tu-berlin.de> - 2013-05-10 11:34 +0200
              Re: Kolmogorov compression? Willem <willem@turtle.stack.nl> - 2013-05-12 20:17 +0000
                Re: Kolmogorov compression? Thomas Richter <thor@math.tu-berlin.de> - 2013-05-12 22:36 +0200
                  Re: Kolmogorov compression? Industrial One <industrial_one@hotmail.com> - 2013-05-12 15:45 -0700
                    Re: Kolmogorov compression? "George Johnson" <matrix29@charter.net> - 2013-05-12 19:37 -0400
                    Re: Kolmogorov compression? Thomas Richter <thor@math.tu-berlin.de> - 2013-05-13 08:48 +0200
    Re: Kolmogorov compression? Ernst <Ernst_Berg@sbcglobal.net> - 2013-05-15 11:04 -0700

#1899 — Kolmogorov compression?

What are the biggest challenges preventing the design of a working Kolmogorov codec in the 21st century? For clarity, a Kolmogorov codec is something that would compress data to the absolute minimum possible.

If I produce a complex picture/video with a simple algorithm of less than 1 KB, saving it in PNG or JPEG would be hundreds of times larger than the 900 bytes of information that was only required to produce it. A Kolmogorov codec would compress such a pic/sequence to the 900 bytes or less if the algorithm was redundant and could in fact be refined.

The problem obviously is that computers by definition are profoundly retarded who can do nothing without human input and only have the strength of performing low-level recursive operations a trillion times a second which humans cannot do, so we employ computers to do exhaustive search techniques to find the best combinations of efficiency that we use for many tasks including compression.

My question is, is this seriously the ONLY technique in the 21st century that today's technology is capable of doing to a refined degree? Blindly try out every combination until you find something?

What are the greatest problems in making Kolmogorov codecs a reality?

[toc] | [next] | [standalone]

#1900

On 29.04.2013 21:14, Industrial One wrote:
> What are the biggest challenges preventing the design of a working Kolmogorov codec in the 21st century?

The halting problem (or theorem). One can prove (!) that the Kolmogorov 
complexity is non-computable, IOW, there is no algorithm that could 
possibly compute it.

> The problem obviously is that computers by definition are profoundly retarded who can do nothing without human input and only have the strength of performing low-level recursive operations a trillion times a second which humans cannot do, so we employ computers to do exhaustive search techniques to find the best combinations of efficiency that we use for many tasks including compression.

This is not the point here, i.e. how "retarded computers are" or not. 
The problem is "what an algorithm is", namely a well-defined sequence of 
operations. Whether that's done by a Turing machine or a human is 
irrelevant. However, an algorithm *can* always be done by a Turing 
machine, if necessary.

> My question is, is this seriously the ONLY technique in the 21st century that today's technology is capable of doing to a refined degree?

It is not a question of technology at all. It is a question of 
mathematics. The K-Complexity is non-compute in the same way that 2+2 is 
never 5, not even for small values of 5 and large values of 2. It is a 
logical obstruction, not a technological one.

> Blindly try out every combination until you find something?

No. That's irrelevant and not the point. Of course you can try faster, 
but faster for a non-halting algorithm still takes infinitely long.

"The new XK-900 computer is so fast, it can do the endless loop in under 
two seconds".

> What are the greatest problems in making Kolmogorov codecs a reality?

Math and logic.

Greetings,
	Thomas

[toc] | [prev] | [next] | [standalone]

#1901

On Monday, April 29, 2013 9:03:52 PM UTC, Thomas Richter wrote:
> On 29.04.2013 21:14, Industrial One wrote:
> 
> > What are the biggest challenges preventing the design of a working Kolmogorov codec in the 21st century?
> 
> 
> 
> The halting problem (or theorem). One can prove (!) that the Kolmogorov 
> 
> complexity is non-computable, IOW, there is no algorithm that could 
> 
> possibly compute it.
> 
> 
> 
> > The problem obviously is that computers by definition are profoundly retarded who can do nothing without human input and only have the strength of performing low-level recursive operations a trillion times a second which humans cannot do, so we employ computers to do exhaustive search techniques to find the best combinations of efficiency that we use for many tasks including compression.
> 
> 
> 
> This is not the point here, i.e. how "retarded computers are" or not. 
> 
> The problem is "what an algorithm is", namely a well-defined sequence of 
> 
> operations. Whether that's done by a Turing machine or a human is 
> 
> irrelevant. However, an algorithm *can* always be done by a Turing 
> 
> machine, if necessary.
> 
> 
> 
> > My question is, is this seriously the ONLY technique in the 21st century that today's technology is capable of doing to a refined degree?
> 
> 
> 
> It is not a question of technology at all. It is a question of 
> 
> mathematics. The K-Complexity is non-compute in the same way that 2+2 is 
> 
> never 5, not even for small values of 5 and large values of 2. It is a 
> 
> logical obstruction, not a technological one.
> 
> 
> 
> > Blindly try out every combination until you find something?
> 
> 
> 
> No. That's irrelevant and not the point. Of course you can try faster, 
> 
> but faster for a non-halting algorithm still takes infinitely long.
> 
> 
> 
> "The new XK-900 computer is so fast, it can do the endless loop in under 
> 
> two seconds".
> 
> 
> 
> > What are the greatest problems in making Kolmogorov codecs a reality?
> 
> 
> 
> Math and logic.
> 
> 
> 
> Greetings,
> 
> 	Thomas

So what I get is that you're confirming the current problem of what current state-of-the-art technology/mathematical algorithms fail to do which is they're only capable of performing redundant, exhaustive searches until they find the best combination. Basically making 99.99% useless computations. Is this the halting problem in a nutshell?

I've talked about this with x264 devs 5 years ago who had visions for what next-gen H.265 should need to become a silver bullet and not an extension.

Basically, H264 takes such an unnecessary amount of computing power and most of it by its motion-estimation algorithm. Being a newb, I studied motion estimation/compensation briefly and got the jist of how it works was "estimate every direction blindly and exhaustively until a good match is found and move onto the next frame".

I suggested getting rid of the ridiculous computation complexity caused by the motion estimation by employing something smarter that doesn't waste time trying to make matches where it shouldn't.

They asked me how I expect it to make optimal motion estimation decisions without it testing a decent amount of vectors?

I had no answer except to speculate that there must be a better, smarter way it can do M.E without wasting so many cycles. Whatever it may be, it would be the silver bullet for video compression. But at this point we were fantasizing, not discussing. We shut the fuck up.

But as of 2013 is there seriously no better method than the common exhaustive searches that have been the norm for the past 30 years? Is there no AI codec that analyzed the data intelligently without too many wasted cycles?

[toc] | [prev] | [next] | [standalone]

#1902

On 29.04.2013 23:30, Industrial One wrote:

> So what I get is that you're confirming the current problem of what current state-of-the-art technology/mathematical algorithms fail to do which is they're only capable of performing redundant, exhaustive searches until they find the best combination.

NO! You are completely missing the point.


> Basically making 99.99% useless computations. Is this the halting problem in a nutshell?


NO! The halting problem is the problem that there is no way of 
determining by an algorithm whether another algorithm ever stops. Note 
the "EVER", not whether the algorithm is slow. An algorithm that tries 
to determine whether another algorithm stops may not stop itself.

By (a not too complicated) argument, one can show that the computation 
of C-complexity is equivalent to solving the halting problem. Which is 
not solvable, i.e. there is no way by checking by computations whether 
an algorithm runs ever into an endless loop. Note "endless", not "very 
long". By just feeding "the wrong string" into a "candidate C-complexity 
computer", one can "crash" any such program in the sense that it will 
never deliver an answer. *NEVER*, not just in a very long time.

> I've talked about this with x264 devs 5 years ago who had visions for what next-gen H.265 should need to become a silver bullet and not an extension.

HEVC seems to be quite a bit better. But it is also quite a monster. 
Just to give you an idea: The reference software of HEVC is about 100 
times (!) slower than JPEG 2000. Ok, it's only a reference software, so 
make this a factor of 10 for a good implementation, but still....

> Basically, H264 takes such an unnecessary amount of computing power and most of it by its motion-estimation algorithm. Being a newb, I studied motion estimation/compensation briefly and got the jist of how it works was "estimate every direction blindly and exhaustively until a good match is found and move onto the next frame".
>
> I suggested getting rid of the ridiculous computation complexity caused by the motion estimation by employing something smarter that doesn't waste time trying to make matches where it shouldn't.

There are plenty of works how to speed up the motion estimation, 
actually. Not only in H.264, but also in its successor. A lot more 
thought was done for HEVC to allow parallelism, for example. The oldest 
alternatives to full search are diamond search and hierarchical search. 
And plenty of others. My average compression conference has at least one 
new method every year. (-;

> They asked me how I expect it to make optimal motion estimation decisions without it testing a decent amount of vectors?

The art is to find a decent compromize (e.g. hierarchical search) that 
uses models of natural images, ehem, videos, to find motion vectors in 
*typical* cases. Not in *all* cases, this is not even necessary. There 
is no necessity to find the best solution, only a convincing solution 
(and a solution that's better than that of your competitor ;-).


> I had no answer except to speculate that there must be a better, smarter way it can do M.E without wasting so many cycles. Whatever it may be, it would be the silver bullet for video compression. But at this point we were fantasizing, not discussing. We shut the fuck up.
>
> But as of 2013 is there seriously no better method than the common exhaustive searches that have been the norm for the past 30 years?

Since when is exhaustive search the matter of choice? Not in my last 20 
years, at least.


Is there no AI codec that analyzed the data intelligently without too 
many wasted cycles?

It doesn't take AI. It just takes statistics.

Greetings,
	Thomas

[toc] | [prev] | [next] | [standalone]

#1903

"Industrial One" <industrial_one@hotmail.com> wrote in message 
news:364392d4-b667-4307-a26c-42a2506d72cf@googlegroups.com...
> On Monday, April 29, 2013 9:03:52 PM UTC, Thomas Richter wrote:
>> On 29.04.2013 21:14, Industrial One wrote:
>>
>> > What are the biggest challenges preventing the design of a working 
>> > Kolmogorov codec in the 21st century?
>>
>>
>>
>> The halting problem (or theorem). One can prove (!) that the Kolmogorov
>>
>> complexity is non-computable, IOW, there is no algorithm that could
>>
>> possibly compute it.
>>
>>
>>
>> > The problem obviously is that computers by definition are profoundly 
>> > retarded who can do nothing without human input and only have the 
>> > strength of performing low-level recursive operations a trillion times 
>> > a second which humans cannot do, so we employ computers to do 
>> > exhaustive search techniques to find the best combinations of 
>> > efficiency that we use for many tasks including compression.
>>
>>
>>
>> This is not the point here, i.e. how "retarded computers are" or not.
>>
>> The problem is "what an algorithm is", namely a well-defined sequence of
>>
>> operations. Whether that's done by a Turing machine or a human is
>>
>> irrelevant. However, an algorithm *can* always be done by a Turing
>>
>> machine, if necessary.
>>
>>
>>
>> > My question is, is this seriously the ONLY technique in the 21st 
>> > century that today's technology is capable of doing to a refined 
>> > degree?
>>
>>
>>
>> It is not a question of technology at all. It is a question of
>>
>> mathematics. The K-Complexity is non-compute in the same way that 2+2 is
>>
>> never 5, not even for small values of 5 and large values of 2. It is a
>>
>> logical obstruction, not a technological one.
>>
>>
>>
>> > Blindly try out every combination until you find something?
>>
>>
>>
>> No. That's irrelevant and not the point. Of course you can try faster,
>>
>> but faster for a non-halting algorithm still takes infinitely long.
>>
>>
>>
>> "The new XK-900 computer is so fast, it can do the endless loop in under
>>
>> two seconds".
>>
>>
>>
>> > What are the greatest problems in making Kolmogorov codecs a reality?
>>
>>
>>
>> Math and logic.
>>
>>
>>
>> Greetings,
>>
>> Thomas
>
> So what I get is that you're confirming the current problem of what 
> current state-of-the-art technology/mathematical algorithms fail to do 
> which is they're only capable of performing redundant, exhaustive searches 
> until they find the best combination. Basically making 99.99% useless 
> computations. Is this the halting problem in a nutshell?
>
> I've talked about this with x264 devs 5 years ago who had visions for what 
> next-gen H.265 should need to become a silver bullet and not an extension.
>
> Basically, H264 takes such an unnecessary amount of computing power and 
> most of it by its motion-estimation algorithm. Being a newb, I studied 
> motion estimation/compensation briefly and got the jist of how it works 
> was "estimate every direction blindly and exhaustively until a good match 
> is found and move onto the next frame".
>
> I suggested getting rid of the ridiculous computation complexity caused by 
> the motion estimation by employing something smarter that doesn't waste 
> time trying to make matches where it shouldn't.
>
> They asked me how I expect it to make optimal motion estimation decisions 
> without it testing a decent amount of vectors?
>
> I had no answer except to speculate that there must be a better, smarter 
> way it can do M.E without wasting so many cycles. Whatever it may be, it 
> would be the silver bullet for video compression. But at this point we 
> were fantasizing, not discussing. We shut the fuck up.
>
> But as of 2013 is there seriously no better method than the common 
> exhaustive searches that have been the norm for the past 30 years? Is 
> there no AI codec that analyzed the data intelligently without too many 
> wasted cycles?

    There is a quicker way and better ways are coming from the Computational 
Photography researchers.
    This is just a 4-direction summed histogram of the image for basic 
alignment.
    Might not handle zoom variances well and also is not tuned to certain 
more sophisticated computations in the link farther below.

    The next big move is to treat video like a 3D scene once cheap camera 
are outfitted with better batteries, faster cheap processers, and more 
onboard addressable RAM.  Once that is in-play, most motion-estimation 
tricks will seem like outdated clumsy overly-computational dead ends.

    Now granted, the trade-off is more memory & CPU time on the user's end 
for simulating disposable alpha-blended deformable 3D planar surfaces 
created and retiled on-the-fly for watchable video, but the bonus is much 
smaller file sizes and better-quality video output.
    Logically, the other necessity is to not simulate overly complex 
surfaces with temporary 3D polygons, but to restrict those surfaces to 
either wasteful bitmap camera sensor frames or lower the resolution enough 
that the pseudo-random patterned noise generators can make the surface match 
the "grain" of the original image with low-computation noise-simulation 
overlays.  I've mentioned this all before a couple of decades ago.  It all 
was obvious then as it is now to a growing segment of the population.

    =====
Viewfinder Alignment
Andrew Adams 	Natasha Gelfand 	Kari Pulli
To appear in Eurographics 2008
http://graphics.stanford.edu/papers/viewfinderalignment/

Abstract
The viewfinder of a digital camera has traditionally been used for one 
purpose: to display to the user a preview of what is seen through the 
camera's lens. High quality cameras are now available on devices such as 
mobile phones and PDAs, which provide a platform where the camera is a 
programmable device, enabling applications such as online computational 
photography, computer vision-based interactive gaming, and augmented 
reality. For such online applications, the camera viewfinder provides the 
user's main interaction with the environment. In this paper, we describe an 
algorithm for aligning successive viewfinder frames. First, an estimate of 
inter-frame translation is computed by aligning integral projections of 
edges in two images. The estimate is then refined to compute a full 2D 
similarity transformation by aligning point features. Our algorithm is 
robust to noise, never requires storing more than one viewfinder frame in 
memory, and runs at 30 frames per second on standard smartphone hardware. We 
use viewfinder alignment for panorama capture, low-light photography, and a 
camera-based game controller.

YOUTUBE
Viewfinder Alignment
Andrew Adams
http://www.youtube.com/watch?&v=lNvEZtLCuMI

Paper
Adobe Acrobat PDF (6 MB)
http://graphics.stanford.edu/papers/viewfinderalignment/paper.pdf

Downloadable Video
MPEG2 Video (37 MB)
http://graphics.stanford.edu/papers/viewfinderalignment/video.mpg

    =====

Unwrap Mosaics: Unwrap Mosaics: A new representation for video editing
http://www.youtube.com/watch?v=FuTZZfS5LZg

 Uploaded on May 24, 2011

Published in 2008 | Official Website: 
http://research.microsoft.com/en-us/u...

Alex Rav Acha of the Weizmann institute of Science,
Pushmeet Kohli of Microsoft Research Cambridge,
Carsten Rother of Microsoft Research Cambridge, and
Andrew Fitzgibbon of Microsoft Research Cambridge

introduce a new representation for video which facilitates a number of 
common editing tasks. The representation has some of the power of a full 
reconstruction of 3D surface models from video, but is designed to be easy 
to recover from a priori unseen and uncalibrated footage. By modelling the 
image-formation process as a 2D-to-2D transformation from an object's 
texture map to the image, modulated by an object-space occlusion mask, we 
can recover a representation which we term the "unwrap mosaic". Many editing 
operations can be performed on the unwrap mosaic, and then re-composited 
into the original sequence, for example resizing objects, repainting 
textures, copying/cutting/pasting objects, and attaching effects layers to 
deforming objects.
 

[toc] | [prev] | [next] | [standalone]

#1909

On Monday, April 29, 2013 12:14:58 PM UTC-7, Industrial One wrote:
> What are the biggest challenges preventing the design of a working Kolmogorov codec in the 21st century? For clarity, a Kolmogorov codec is something that would compress data to the absolute minimum possible.

 So what stops us from having a compression of all files?

Clever indexing.  You got to have game.


 LOL I'm experimenting with surjection. Infinite codes that point to a finite set of objects we collectively called 'File."

 I suppose if we are all a Hologram all we can do is discover our source code.

 If there is a Big Bang then perhaps the "Universe" is a compressed object since space seems to appear everywhere and is expanding us faster and faster.
 I happen to think there is No Big Bang just Cycle.
State-Space and Cycle will replace Space-Time.

[toc] | [prev] | [next] | [standalone]

#1934

The trick with halting, is in the finite scope to realize all non halting HAS TO be a cyclic pattern. A simple f[x]=f[f[y]] detector suffices, though not optimally.

Cheers Jacko

https://dl.dropboxusercontent.com/u/1615413/Own%20Work/Dimensions.pdf and the latest idea in "Free Goldstone Charge."

[toc] | [prev] | [next] | [standalone]

#1936

Am 09.05.2013 03:34, schrieb jacko:
> The trick with halting, is in the finite scope to realize all non halting HAS TO be a cyclic pattern. A simple f[x]=f[f[y]] detector suffices, though not optimally.

Sorry, but this is wrong. Running into a cycle is not the only option a 
Turing machine has. In fact, I can construct a Turing machine that 
cannot halt. (And actually, this is the proof of the halting theorem).

Since Turing machines are all finite state machines, I can just 
enumerate them, i.e. assign to each Turing machine a natural number i. 
Furthermore, the input to a Turing machine is a finite tape, and without 
loss of generality, we can assume that the input is encoded in some kind 
of numeric format (ASCII, binary, whatever). For any finite input, we 
can thus assign this input also a natural number, call this w.

Now assume that you have a "magic Turing machine" G that outputs a one 
("warning, non-stopping machine!") whenever the Turing machine i, 
applied to the input w, does not stop. Thus, G(i,w) = 1 if w feed to i 
does not halt. (Consider this your "cycle detector").

Let's now construct from G a simpler Turing machine F. F works this way: 
It applies G to i and i, i.e. it feeds the Turing machine i its own 
Turing code (the program code) as its input. That is, F checks whether 
the Turing machine i stops if we feed its own input i. If i applied to i 
does not stop, F outputs a one. We add a litte endless loop at the end 
of F if G does return, and returns a zero, i.e. it detected that the 
program i applied to input i.

That is, I feed every program its own program code, and see whether it 
locks up on it. If so, the output is one. If not so, F locks up by the 
endless loop I added at its end. IOW, F can either end, and return one, 
or run into an endless loop. This does not yet sound very useful, but 
please wait!

Now let's do something nasty: Apparently, F is a Turing machine, so it 
has a Turing code. Let's call this f. What happens if we apply now the 
halting-checking algorithm F to itself, i.e. feed your "do not stop 
cycle detector" with its own code.

Now let's think about it: Apparently, it cannot output one. If it would, 
it would just say that the cycle detector just detected that if I apply 
it to its own code does not stop. That is, it found that if we feed it 
by its own code, it must lock up. But since its output was a one, it 
apparently did stop, so the answer "one" as output is wrong!

On the other hand, if F runs into an endless loop if applied to its own 
Turing code, then this is wrong either. Because apparently, it does run 
into an endless loop. And if F runs into an endless loop, your magic 
cycle detector should have detected this case. And if your magic cycle 
detector detects this case, F returns one. Always. And in specific, it 
does not run into an endless loop.

But these where the only possibilities we gave F, namely either return 
one, or run into an endless loop. And neither of these possibilities are 
logically consistent.

Since F is constructed from your magic cycle detector in a trivial way, 
apparently your magic cycle detector cannot exist.

q.e.d.

BTW, if you check the above proof, it is very much identical to the 
diagonal argument that there are more real numbers than rational 
numbers. The trick is all the same. Just give the cow its own milk to 
drink, inverted, and see how it all goes up into flames.

Greetings,
	Thomas

[toc] | [prev] | [next] | [standalone]

#1937

Ignore this man, he's being an obtuse idiot. Get the maximal considered state size X, and reserve 2*X bits. Iterate one step on X bits, and two steps on Y (the other X bits). Compare these two states, and HALT "CYCLIC" if they are the same. Run a background task such that detecting this halt state implies your non halting task. This is because some state of X bits must be repeated in a non halting cycle.

Now as non halting generators will never end up representing a finite decompression, they can be safely ignored by ++ on the state generator uniqueness index. The problem is not halting, the problem is having a representational alphabet which can generate all decompression outputs, or which has tautalogical identity numbers in it, which are neither compressed or decompressed, but passed through. No prefix of any such tautology maybe a compressed generator. This sets expressional bounds for coding the generator.

[toc] | [prev] | [next] | [standalone]

#1938

An interesting generator is when a zero byte swaps with the following byte. On decode this is move all zero bytes one byte earlier in the stream. Now given that purely random data will be evenly weighted for zeros and ones to be at any point in the stream, the zero byte swaps with later bytes slightly makes zeros occur to the end of the stream, and ones closer to the beginning.

So an adaptive code using the slight slope in the mutual information between a stream bit and an interpolation sloped bit probability, as you go toward the end of the stream leads to a compression.

It would be useful to invert the bits in the inter-packet byte slot (first byte of next packet) for the zero ending packet (placing all ones).

Conversely the all ones bytes can move earlier in the stream, so that this inversion can loop to the first byte in a packet from the last byte. The actual bit ratio in the byte can determine direction of motion, with the byte value to scan for (and hence move) selected pseudo-randomly.

[toc] | [prev] | [next] | [standalone]

#1939

On 10.05.2013 00:52, jacko wrote:
> Ignore this man, he's being an obtuse idiot. Get the maximal considered state size X, and reserve 2*X bits.

Your error is that the state of a Turing machine consists of its 
internal state, plus the state of its tape, which is infinite. And thus, 
the overall size of the state of a Turing machine is not finite. Thus, 
you cannot detect cycles of a Turing machine this way.

Greetings,
	Thomas

[toc] | [prev] | [next] | [standalone]

#1940

Thomas Richter wrote:
) On 10.05.2013 00:52, jacko wrote:
)> Ignore this man, he's being an obtuse idiot. Get the maximal considered state size X, and reserve 2*X bits.
)
) Your error is that the state of a Turing machine consists of its 
) internal state, plus the state of its tape, which is infinite. And thus, 
) the overall size of the state of a Turing machine is not finite. Thus, 
) you cannot detect cycles of a Turing machine this way.

His point is that the halting problem can be easily sidestepped by limiting
the length of the tape, which means it's not a true Turing machine, but
no existing computer is a true Turing machine in that exact same sense.

In fact, it's quite easy to construct a compressor that just enumerates
through all possible input programs, running them for a finite amount of
time in a sandbox, and to output the one that produces the desired output.
The only problem is that the runtime of the compressor will be longer
than the lifespan of the universe for any interesting data sizes.


SaSW, Willem
-- 
Disclaimer: I am in no way responsible for any of the statements
            made in the above text. For all I know I might be
            drugged or something..
            No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT

[toc] | [prev] | [next] | [standalone]

#1941

On 12.05.2013 22:17, Willem wrote:
> Thomas Richter wrote:
> ) On 10.05.2013 00:52, jacko wrote:
> )>  Ignore this man, he's being an obtuse idiot. Get the maximal considered state size X, and reserve 2*X bits.
> )
> ) Your error is that the state of a Turing machine consists of its
> ) internal state, plus the state of its tape, which is infinite. And thus,
> ) the overall size of the state of a Turing machine is not finite. Thus,
> ) you cannot detect cycles of a Turing machine this way.
>
> His point is that the halting problem can be easily sidestepped by limiting
> the length of the tape, which means it's not a true Turing machine, but
> no existing computer is a true Turing machine in that exact same sense.

But the infinite tape is crucial. For any finite state machine, one can 
"trivially" find a loop, but this is not the question of the halting 
theorem, which talks about Turing machines, and not anything else.

Where "trivial" does not mean "by any trivially to archive technology", 
see below, but by a trivial algorithm which, at least in principle, 
works. (-:

> In fact, it's quite easy to construct a compressor that just enumerates
> through all possible input programs, running them for a finite amount of
> time in a sandbox, and to output the one that produces the desired output.
> The only problem is that the runtime of the compressor will be longer
> than the lifespan of the universe for any interesting data sizes.

Sure enough. But let's see... for a realistic computer, we have probably 
about 1TB of storage, that is, we have 2^((1024)^4*2^3) possible states. 
If we would want to enumerate them, we would probably need one bit per 
state, which requires as many bits as the above, or 2^((1024)^4*2^3)/2^3 
bytes, which is a number of approximately
q = log_10(2^((1024)^4*2^3) - log_10(8) = 2^3*1024^4 * log_10(2) - 
log_10(8) > 2647887843771 digits. A bit too long to be written down. 
Given that there are about 10^80 particles in the universe (a number 
with "only" 80 digits), there is actually no hope one can realistically 
do that, not with any storage technology in this universe, at least. (-:

So long,
	Thomas

[toc] | [prev] | [next] | [standalone]

#1942

I get it, algorithms end up in an infinite loop and can't stop themselves and other algorithms instructed when to stop them then go into an infinite loop themselves later.

But this is related to the moronic state of technology we're in and the prospect of "search a shitload of combinations until you find a good match" that's yet to be obsoleted. Not sure if Quantum computing will improve any of that.

George, I've already seen those demos like 5 years ago. I'm not convinced the ideas will work unless they've found a reliable formula that can define depth in a 2D image. Human eyes obviously can but how exactly will a computer know which pixel is closer. Is it brighter?

I wonder, does Kolmogorov Complexity have a limit and does it have to include all the data it depends on to produce its output?

Like, a 4K demo 10 years ago were crappy quality when compared to the ones made this year. I can't view them because I lack a DirectX11-capable video card so I have to download the 50MB lower-quality MPEG recordings.

Would a properly-working Kolmogorov codec in 2003 compress raw footage of this 2013 awesome demo to 4KB that would then be unplayable because no such library/video card exists at the time or compress it to the minimum it would take with current DirectX and hardware to reproduce the scenery which would be say, 500KB in 2003 but 4 in 2013?

Because procedurally-compressed media work by just instructing how to make something be in due time (hopefully real-time), Ernst's post got me wondering if Kolmogorov complexity really has a defined limit at all.

All software in the world is a product of a simple page-long patent and procedure started a long time ago that took 100 years to formulate so far in the hundreds of exabytes it got to today.

Same thing with what Ernst said about the universe, just have a single atom and a short procedure on how to explode it and you got the whole thing compressed in one KB with an expected decompression time of about 5 billion years.

Basically, does Kolmogorov complexity have a limit within the context of the hardware/libraries available in the current environment or is the law absolute?

If it's absolute, is every file potentially able to be compressed into nothing?

[toc] | [prev] | [next] | [standalone]

#1943

"Industrial One" <industrial_one@hotmail.com> wrote in message 
news:315de5db-a7ae-40b5-8dc8-9c2a8b991af7@googlegroups.com...
> I get it, algorithms end up in an infinite loop and can't stop themselves 
> and other algorithms instructed when to stop them then go into an infinite 
> loop themselves later.
>
> But this is related to the moronic state of technology we're in and the 
> prospect of "search a shitload of combinations until you find a good 
> match" that's yet to be obsoleted. Not sure if Quantum computing will 
> improve any of that.
>
> George, I've already seen those demos like 5 years ago. I'm not convinced 
> the ideas will work unless they've found a reliable formula that can 
> define depth in a 2D image. Human eyes obviously can but how exactly will 
> a computer know which pixel is closer. Is it brighter?
>
> I wonder, does Kolmogorov Complexity have a limit and does it have to 
> include all the data it depends on to produce its output?
>
> Like, a 4K demo 10 years ago were crappy quality when compared to the ones 
> made this year. I can't view them because I lack a DirectX11-capable video 
> card so I have to download the 50MB lower-quality MPEG recordings.
>
> Would a properly-working Kolmogorov codec in 2003 compress raw footage of 
> this 2013 awesome demo to 4KB that would then be unplayable because no 
> such library/video card exists at the time or compress it to the minimum 
> it would take with current DirectX and hardware to reproduce the scenery 
> which would be say, 500KB in 2003 but 4 in 2013?
>
> Because procedurally-compressed media work by just instructing how to make 
> something be in due time (hopefully real-time), Ernst's post got me 
> wondering if Kolmogorov complexity really has a defined limit at all.
>
> All software in the world is a product of a simple page-long patent and 
> procedure started a long time ago that took 100 years to formulate so far 
> in the hundreds of exabytes it got to today.
>
> Same thing with what Ernst said about the universe, just have a single 
> atom and a short procedure on how to explode it and you got the whole 
> thing compressed in one KB with an expected decompression time of about 5 
> billion years.
>
> Basically, does Kolmogorov complexity have a limit within the context of 
> the hardware/libraries available in the current environment or is the law 
> absolute?
>
> If it's absolute, is every file potentially able to be compressed into 
> nothing?

    Finally, an intelligent question.

    Simple answer.  No.  Every file cannot be compressed into nothing.
    A general purpose bulk data-compressor untuned for the data set it is 
compressing (think of an audio data compressor taking a stab at a JPG file), 
will produce non-optimal results.

    However, since a very large variety of data compression functions are 
available (most not tuned for "General Function" bulk data compression 
functions), then there will always be sets of files that are optimally 
compressed by one data compression routine and not another and vice-versa.

    The key thing to remember is that there is always a Piper to Pay at the 
end of the day.
    If I am compressing a large set of 2D bitmaps, the data compressor that 
is optimal for that will usually fail at compressing audio files.
    So usually, with the current "Box Head" thinking of the Data Compression 
program makers, the result will be a minimum of two data compressors & 
decompressors for 2 different "file types".  What is optimal with one data 
compressor is non-optimal with another.

    However, if you mentally reduce these "file types" to be results of a 
data-function operation then you also realize that a large variety of data 
functions are possible for achieving smaller data files.  The program that 
compresses-decompresses these files will eat up a certain amount of space as 
will the computer OS that it parasites off to function.

    Another logical deduction is that if "FILE X" is appended to "FILE Y" 
that you have now a "new file" "FILEXY" with new exploitable repetition 
fields that may not have existed alone in either "FILE X" or "FILE Y".  As 
such, adding one file to another existing file can change the resulting 
compressibility factor for a smaller output file.

    The final logical output of these simple and obvious deductions means 
that every file can indeed be compressed to a smaller output file.
    However, this result cannot ever be achieved with a single data 
compressor function.
    This result also requires an increase of coding operations to utilize 
multiple data compressor functions (tuned to each possible input data set).
    The other downside is that in order to exploit multiple tuned data 
compression functions, the indexing of the compressed file will begin to 
negate any cost savings.

    Right now, the popular thing is "Low Entropy" data compressors (because 
they are easy to code).
    All tuned to find simple redundancies and reduce them to symbolic 
statistical representations.

    There exists a vast number of "Medium Entropy" & "High Entropy" data 
compressors unwritten for general public usage.
    The same rules apply, but the CPU time plus memory allocation required 
is much higher.
 

[toc] | [prev] | [next] | [standalone]

#1944

On 13.05.2013 00:45, Industrial One wrote:
> I get it, algorithms end up in an infinite loop and can't stop themselves and other algorithms instructed when to stop them then go into an infinite loop themselves later.
>

Exactly.

> But this is related to the moronic state of technology we're in and the prospect of "search a shitload of combinations until you find a good match" that's yet to be obsoleted.

No, it isn't. This is a theoretical argument that does not apply to a 
specific technology. It is a math argument, and thus technology-agnostic.

> Not sure if Quantum computing will improve any of that.

Not sure either. The question is "is a general quantum computer a Turing 
machine", and I don't know that. But there is at least some thing about 
quantum computing that bothers me, and this is the "correspondence 
principle". Saying that for large quantum numbers, quantum mechanics has 
to approach classical mechanics. If applied to quantum computing, it 
just means that you cannot generate quantum computers with "too many 
states" because otherwise they would become classical where you don't 
have all the linear quantum laws. Which again means that either 
something is wrong with quantum computing *or* something is wrong with 
quantum mechanics. Nobody has ever seen a quantum device of a 
macroscopic scale, and quantum computers are likely no exception.

In either way, this is at least an interesting topic for research in the 
next years, so at least one of two things will improve: Quantum 
computing, or our understanding of quantum mechanics.


> George, I've already seen those demos like 5 years ago. I'm not convinced the ideas will work unless they've found a reliable formula that can define depth in a 2D image. Human eyes obviously can but how exactly will a computer know which pixel is closer. Is it brighter?

How is that related to anything? The human brain has adopted to natural 
scenes, and thus is trained to typical images where it can deduce depth 
from typical images. But to really know depths, you need two eyes. And 
with two cameras, one can of course create a depth map. This is known 
and working technology. See MPEG.

> I wonder, does Kolmogorov Complexity have a limit and does it have to include all the data it depends on to produce its output?

A limit in which sense? The limit is the KC itself, i.e. this is defined 
*as* the limit. Just that you cannot approach it, it is uncomputable.

> Like, a 4K demo 10 years ago were crappy quality when compared to the ones made this year. I can't view them because I lack a DirectX11-capable video card so I have to download the 50MB lower-quality MPEG recordings.

MPEG is a classical transformation quantizer in the sense of information 
theory. There is nothing "theorically new" there, except that it is very 
bright engineering. But no new math, if this is what you ask for.

> Would a properly-working Kolmogorov codec in 2003 compress raw footage of this 2013 awesome demo to 4KB that would then be unplayable because no such library/video card exists at the time or compress it to the minimum it would take with current DirectX and hardware to reproduce the scenery which would be say, 500KB in 2003 but 4 in 2013?

MPEG JPEG and so on are not trying any KC approach. They are classical 
approaches.

> Because procedurally-compressed media work by just instructing how to make something be in due time (hopefully real-time), Ernst's post got me wondering if Kolmogorov complexity really has a defined limit at all.

It does not "have a limit", it "is the limit".

>
> All software in the world is a product of a simple page-long patent and procedure started a long time ago that took 100 years to formulate so far in the hundreds of exabytes it got to today.

Not really. Besides, you cannot patent those things. Patents need to be 
related to effects of nature, but what we're currently discussing is 
about math. The "patented technology" that is used today (MPEG, and 
friends) are "only" applications of old mathematical results, go back to 
Shannon, for example, and many others. We're standing on the shoulders 
of giants, so to say.

> Same thing with what Ernst said about the universe, just have a single atom and a short procedure on how to explode it and you got the whole thing compressed in one KB with an expected decompression time of about 5 billion years.

That is not related to the universe and everything. The answer you seek 
is 42. But you should know that.

> Basically, does Kolmogorov complexity have a limit within the context of the hardware/libraries available in the current environment or is the law absolute?

It is absolute, and applies to *all* Turing machines. So all computers 
we have today. For quantum computers, the relevant question is whether 
they are "only massively parallel Turing machines", in which case it 
applies to them as well, or whether there are "something else". The 
answer of which I do not know, but if I want to give you my gut feeling, 
then I would say they are also "only" Turing machines, and thus the same 
restrictions apply. There is nothing for free in this universe.

> If it's absolute, is every file potentially able to be compressed into nothing?

No. It can be compressed to at most its K-complexity. However, as I 
already said, there is no Turing machine that *could* compress it to 
K-complexity itself because the K-complexity is not computable. You can 
compress it to *approximate* K-complexity, i.e. "just a little bit 
longer if you just wait long enough", which could be *very* long.

Greetings,
	Thomas

[toc] | [prev] | [next] | [standalone]

#1950

On Monday, April 29, 2013 12:14:58 PM UTC-7, Industrial One wrote:
> What are the biggest challenges preventing the design of a working Kolmogorov codec in the 21st century? For clarity, a Kolmogorov codec is something that would compress data to the absolute minimum possible.
> 
> 
> 
> If I produce a complex picture/video with a simple algorithm of less than 1 KB, saving it in PNG or JPEG would be hundreds of times larger than the 900 bytes of information that was only required to produce it. A Kolmogorov codec would compress such a pic/sequence to the 900 bytes or less if the algorithm was redundant and could in fact be refined.
> 
> 
> 
> The problem obviously is that computers by definition are profoundly retarded who can do nothing without human input and only have the strength of performing low-level recursive operations a trillion times a second which humans cannot do, so we employ computers to do exhaustive search techniques to find the best combinations of efficiency that we use for many tasks including compression.
> 
> 
> 
> My question is, is this seriously the ONLY technique in the 21st century that today's technology is capable of doing to a refined degree? Blindly try out every combination until you find something?
> 
> 
> 
> What are the greatest problems in making Kolmogorov codecs a reality?


The Answer of 42 is only valid when you do not understand the question.

I find 40-bits to be the answer when we do.  Yes that is a joke but I do have a number generator running matching 40-bit words of the Million Digit File.
 It just "generated" a "last match" so now it is possible to construct sets of elements, which are codes, that generate the 40-bit words that make up the MDF.
 It may be possible to compress these "surjective codes" (SCODES) and in turn compress MDF. I have much study ahead and will keep my hope up.

 The concept of Quantum computing is interesting. 
 Lets see we now have the theory that the Universe is a kind of hologram with actual "bits" the size on the Planck scale http://en.wikipedia.org/wiki/Planck_scale

 That would suggest we are a program ourselves if all is reduced to "bits."

 The least of these things is it keeps us thinking.

[toc] | [prev] | [standalone]

Back to top | Article view | comp.compression

csiph-web