But really, only one part of the proof is hard, and that is proving that the halting problem can be Turing-reduced to the problem of calculating Kolmogorov complexity.
The core of the argument is this: there exists short strings with short minimal programs, whose runtime is insanely long. That's really it.
In detail, consider the following sentence:
The least string that is not output in N steps by any program of length $\le 2n$, where N = runtime of program p.where p is a program of length $\le n$, whose runtime is the longest among all programs of length $\le n$. That is, it's an n-Busy Beaver Runtime champion.
The string $x$ described by that sentence has Kolmogorov complexity $K(x) \le n + \log_2(x) + C$, where $n$ comes from $p$, $\log_2(x)$ comes from $n$, and $C$ comes from the rest of the sentence.
If $n$ is big, such that $2n > n + \log_2(x) + C$, the string $x$ thus described has a minimal program that has length $ < 2n$, which, by the description of $x$, must have runtime longer than the n-Busy Beaver Runtime champion.
Further, $x$ is short, that is, $l(x) \le 2n + 1$, since there are only so many possible outputs from programs with length $\le 2n$.
Thus, this following program calculates a function that dominates over the Busy Beaver Runtime function for all big n:
Input n.From this, a program that dominates over Busy Beaver Runtime function for all n can be constructed, which can be used to calculate Busy Beaver Runtime function, which can be used to solve the halting problem.
List all strings $x$ of length $\le 2n + 1$.
For each $x$, get its Kolmogorov complexity $K(x)$ using the oracle.
Run each program of length $K(x)$, until one of them outputs $x$. Record the runtime as $n_x$.
After all the $n_x$ are recorded, output the biggest one.
No comments:
Post a Comment