Continuing the discussion from Contradictory Points in ID and Information Theory Arguments?:
[Optimal] Compression is Uncomputable
Halting oracle comes into play when you have a process that you do not know if it has terminated or not.
Take an arbitrary configuration of atoms in space, perfectly known, velocities and positions.
Our task is to compute the optimal compression of these atoms at a particular snap shot. We do not want near optimal. We want to have the precisely optimal compression. We do not want lossy compression. We want to be able to reconstruct the whole system precisely down to the bit. We do not want just salient parts of the atoms (e.g. their temperature), we want to be able to save and restore this without a single extra bit of storage. We do not care how long the compression/decompression algorithm takes to run, but it cannot run infinitely.
We do this by looking for patterns. Every pattern we find reduces the compression size. We can also run a simulation forward (or backwards), and see if that new snap shot is easier to compress, and compress that snap shot with the time offset from where we are, to get a better compression.
Here is the algorithm to find this optimal compression:
def find_best_compression(X) for compression in all_possible_compressions: #an infinite set if best_compression(compression, X): return compression
The problem is that “best_compression” is undecidable without a halting oracle. We could make a naive implementation of this like so:
def best_compression_looper(compression, X): for other_compression in all_possible_compressions: if other_compression(X) < compression(X): return false return true # we never reach here
The problem is that all_possible_compressions is an infinite set. If we have the best compression, the function will never return. We will never find out, so the program find_best_compression will never halt. So we need to wrap this looper in halting oracle, just like this:
def best_compression(compression, X): return will_not_halt(best_compression_looper, args=(compression, X))
Now, we we have an algorithm that can compute the best possible compression of a sequence. However, it relies on a logical impossible entity, a halting oracle. So we cheated. This is not possible. That is why optimal compression is incomputable. How does this relate with MI? Well, “pattern” is synonymous with MI here (between different parts of the system) or redundant information in the system. We can never compute for certain how much MI there is because we do not have a halting oracles.
This itself is NOT the proof of that compressibility is uncomputable. That is a different proof. Rather, this is an example of an implementation which shows how a halting oracle could overcome the uncomputability problem. [note: this paragraph was corrected; in first draft, it erroneously claimed this was the proof of uncomputability]
In practice, however, we are not interested in this problem of finding the verifiably optimal compression. We are happy to get nearly optimal solutions, and that does not require a halting oracle.
Law of Information Non Growth
I already explained LoING.
We can see here that measuring the information in a system is equivalent to finding the optimal compression of a system. We cannot do this. It requires a logically impossible program. This means that we cannot actually measure the true amount of order in any system.
LoiNG and 2nd Law of Thermodynamics
So information in the system can be staying constant (or decreasing), but we would have no way of telling this. This how you resolve the paradox of the 2nd Law with LoiNG. The 2nd Law teaches that information/entropy is always increasing. LoiNG states that it is always constant (or decreasing in non-reversible systems). How can both be true? The entropy of the 2nd Law is measurable macroscopic quantity about the number of possible state a system can be in. The information of LoING is the precise one of those states the system is in, which cannot ever be known. So we have two types of information/entropy alongside one another. One is measurable in the empirical domain, and one is not and is provably impossible to access.
That is how Halting Oracles and LoiNG are connected. It is not that Halting Oracles are required for new information. Rather, if we observe information growth, our lack of Halting Oracles prevent us from really know if this is informaiton growth or not. So LoiNG still applies in systems that apparently follow the 2nd law of thermodynamics.