Return Styles: Pseud0ch, Terminal, Valhalla, NES, Geocities, Blue Moon. Entire thread

Infinite Compression techniques

Name: FrozenVoid !!mJCwdV5J0Xy2A21 2011-11-09 9:48

I present a system which would be capable of unlimited compression of any data.
Theory:
Every number can be mapped 1:1 to positive unsigned integer(representing the number itself)
Every integer can be represented as range of floating point numbers
i.e. 3 is range from 3.000... to 3.999...
Now if we multiply the original number by 10: 3*10=30
the range is also multiplied, 30.000... to 39.999... all of these numbers divided by 10 give 3 as integer.
Suppose we can alter original number by shifting the range up or down by supplying an extra factor
3+1 or 3-1, with these 3.000...-3.999... ranges become 4.000...-4.999.. and 2.000...-2.999... respectively
The compression is as follows. The original number is multiplied by a huge scale to create number
which is at least twice longer in file length, giving very large floating point range.
Now we multiply this range by adding a 64bit scale modifier(applied to original number) which shifts the range up and down so the space of the range is now 2^64 times bigger than original.
The compression is search for Any number in that huge range which can be represented more compactly
when one of these is found(for some function like e^A) A is recorded along with scale modifier.
Since the range is enormous there are certainly some numbers which can be represented in short form as
function(x)=number_in_range.
The decoding is as follows,function(x) is runs and results number is divided by scale, then a scale modifier is applied
to get the original number, which is converted to file.

Name: Anonymous 2011-11-09 12:55

You only need 0 bits to compress all possible data and maybe even everything in existence, including yourself (all natural numbers).
However, finding anything you want within such a large amount of data may be unfeasible as it'd be like searching a particular, special small needle in an infinite haystack of small needles.
The next question would be, what would be the shortest program that can generate my data? You'll need to learn about Algorithmic Information Theory and Kolmogorov Complexity to answer that question. What about compressing any data? If we could pick any number at random, we'd expect a good deal of numbers to be Kolmogorov random (no algorithm shorter than the data), however there is the question if we can truly perform this 'pick'. If your random number is generated by a pseudo-random-number-generator, it is computable, thus it will be very compressible. If you random number is generated by, let's say: quantum noise, then it depends on a number of factors, for example, which interpretation of quantum mechanics is the real one. In the case the world is fully computable (PRNGs being used where we assume true randomness), then everything is very easy to compress. In the case some variant of MWI is true (what I consider to be the case, first because when considered independently it's the one that makes most sense, it also is the most probable when considered in the light of various formalizations of Occam's Razor; secondly, my current (with high enough, but not absolute confidence) metaphysical beliefs include Arithmetical Realism and a form of mathematical monism, which essentially gives rise to MWI-like quantum mechanics way too easily when the Anthropic Principle is considered over them, while making most other interpretations highly unlikely), quantum noise will be less likely to be compressable (by a computable function, or Kolmogorov random).
If you don't share my opinion on the nature of quantum mechanics, there is a simpler way to attain the same effect of uncompressability. Consider this thought experiment: You exist at time t0 here in some room, at time t0+delta_t, n (choose a sufficiently large n) identical (be it subparticle-scale, or merely just identical quantum states) copies of yourself and the room you are in are made (they can be placed in various random spatial locations, this part is irrelevant, as long as the locations don't overlap), and the room is altered by adding an index which is visible to each copy, corresponding to the number of the copy (your initial room has number 0 as the index). You are now asked: What number do 'you' see as the index? This assumes that all copies are conscious and philosophical zombies are likely nonsense (please don't consider souls or silly stuff). If you must insist of crazy metaphysics (souls, zombies, etc), then consider a computer or some other digital device instead of yourself and ask yourself from the perspective of the computer, what index does it see?
The obvious answer is that it would seen any number from 0 to n and this number would be truly random (experience is not shared, physical states are consistent with mental states). In a more simplified, and more joking form it would be like looking at the set of natural numbers (or a finite subset of them) and asking those numbers what would the probability of being one of those numbers be (from the perspective of each number, it's 1, but from your 'god'/birds-eye perspective it's 1/n). Anthropic reasoning can be confusing at times.


tl;dr: Computable data is likely to be compressible. Uncomputable or truly random data is likely to not be compressible. "Infinite" compression (0 bit) may be achieved, but that doesn't mean you'll be able to find any data in the infinite mess that it generated (all possible data can be found in a normal number, such as the square root of 2, or the set of natural numbers and so on, which can be computed, even if the algorithm may never halt).

Immediately relevant reading:
"An Introduction to Kolmogorov Complexity and Its Applications" by Li M., Vitanyi P.

Very interesting reading for the more philosophically inclined:
http://www.hpcoders.com.au/nothing.html
http://arxiv.org/abs/0912.5434


(Wait, why am I responding seriously to this reposted thread? /autism)

Newer Posts
Don't change these.
Name: Email:
Entire Thread Thread List