Kolmogorov compression?

[Industrial One]

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?

[Thomas Richter]

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

[Industrial One]

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?

[Thomas Richter]

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

[George Johnson]

"Industrial One" <industr...@hotmail.com> wrote in message
news:364392d4-b667-4307...@googlegroups.com...

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.

[Ernst]

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.

[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.

Cheers Jacko

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

[Thomas Richter]

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

[jacko]

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.

[jacko]

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.

[Thomas Richter]

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

[Willem]

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

[Thomas Richter]

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

[Industrial One]

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?

[George Johnson]

"Industrial One" <industr...@hotmail.com> wrote in message

news:315de5db-a7ae-40b5...@googlegroups.com...

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.

[Thomas Richter]

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

[Ernst]

On Monday, April 29, 2013 12:14:58 PM UTC-7, Industrial One wrote:

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.