<p>Hmm, turns out there's actually an matching upper bound that isn't too hard:</p>
<p>To produce the truth table <span class="math-container">$HALT_n$</span> in a finite amount of time, the only information that is needed is the number of machines of description length at most <span class="math-container">$n$</span> which halt. This number is not more than <span class="math-container">$2^{n}$</span>, so it can be represented with about <span class="math-container">$n$</span> bits, and say the number is <span class="math-container">$m$</span>. Then we can start all such machines in parallel and run them until <span class="math-container">$m$</span> many of them halt and so we can stop simulating since the remainder are known not to be halting</p>
<p>So, I guess the folklore argument is tight here. We have</p>
<p><span class="math-container">$n - \omega(1) \leq K(HALT_n) \leq n + O(1)$</span></p>
<p>and <span class="math-container">$K(HALT_n)$</span> is only well-defined up to additive <span class="math-container">$O(1)$</span> anyways, depending on our choice of universal Turing machine.</p>
<p>N.B.: As a cute bonus, this proof shows that the <span class="math-container">$n$</span>-bit string corresponding to the number of machines of description length at most <span class="math-container">$n$</span> which halt is an incompressible string -- if it were compressible, then the upper bound here would be tighter, contradicting the lower bound.</p>

CC BY-SA 4.0
2021-09-22T09:06:30.893Z
This bound is also mentioned in https://cstheory.stackexchange.com/q/14445.
Emil Jeřábek
CC BY-SA 4.0
2017-01-30T20:32:50.787Z
2021-09-22T04:16:13.203Z
2021-09-22T04:16:13.203Z
Chris Beck
<p>Let <span class="math-container">$HALT_n$</span> denote the string of length <span class="math-container">$2^n$</span> corresponding to the truth table of the halting problem for inputs of length <span class="math-container">$n$</span>.</p>

<p>If the sequence of Kolmogorov complexities <span class="math-container">$K(HALT_n)$</span> were <span class="math-container">$O(1)$</span>, then one of the advice strings would be used infinitely often, and a TM with that string hard-coded would be able to solve <span class="math-container">$HALT$</span> uniformly infinitely often, which we know isn't the case.</p>

<p>A closer inspection of the diagonalization argument actually shows that <span class="math-container">$K(HALT_n)$</span> is at least <span class="math-container">$n - \omega (1)$</span>, so together with the trivial upper bound, we have:</p>

<p><span class="math-container">$n - \omega(1) \leq K(HALT_n) \leq 2^n + O(1)$</span></p>

<p>This lower bound is noted in the intro of a recent paper of Fortnow and Santhanam <a href="http://drops.dagstuhl.de/opus/volltexte/2016/5850/pdf/29.pdf" rel="nofollow noreferrer">``New Non-uniform Lower Bounds for Uniform Complexity Classes''</a>, and they attribute it to folklore. Basically, if the advice string is shorter than the input length, then we can still diagonalize against machines with at most that amount of advice.</p>

<p>(Edit: Actually, in an earlier version of the paper they attributed it to folklore, I guess now they just say it's an adaptation of Hartmanis and Stearns.)</p>

<p>Actually, in that paper they are concerned with Time-hierarchy theorems, and they state things relative to a resource bound of <span class="math-container">$t$</span> time steps, rather than the unrestricted Kolmogorov complexity. But, the proof of the ``folklore'' result is the same in the unrestricted case.</p>

<hr>

<p>One of the reasons they care about advice lower bounds, is that it is connected to circuit lower bounds and derandomization in the ``hardness vs. randomness'' paradigm. For instance, if the canonical problem solvable in time <span class="math-container">$2^n$</span> has truth tables which require advice <span class="math-container">$2^{\epsilon n}$</span> in order to be computed in time <span class="math-container">$2^{\epsilon n}$</span>, then those truth tables don't have circuits of size <span class="math-container">$2^{\epsilon n}$</span> either, so <span class="math-container">$P = BPP$</span> by a celebrated result of Impagliazzo and Wigderson.</p>

<p>Asking about <span class="math-container">$K(HALT_n)$</span> instead doesn't have any such applications afaik, but it might be easier to resolve. It's also easier to state, lacking any dependence on a time bound parameter -- it's a rather natural problem which might already have been studied.</p>

<p>Are there any better lower or upper bounds on <span class="math-container">$K(HALT_n)$</span> known besides the ``folklore'' result? Is either of the lower or upper bounds above tight?</p>

<hr>

<p>Note: There is another nice post about the <em>circuit complexity</em> of the halting problem, which can be seen to be nearly maximal by an argument sketched by Emil Jerabek here: <a href="https://mathoverflow.net/questions/115275/non-uniform-complexity-of-the-halting-problem">https://mathoverflow.net/questions/115275/non-uniform-complexity-of-the-halting-problem</a></p>

<p>Basically, it uses a trick where we can compute (with random access) the lexicographically first truth table of (large) circuit complexity within the class <span class="math-container">$E^{NP^{NP}}$</span>. And we can reduce this computation to a query to the halting problem, and this reduction has low circuit complexity. So, <span class="math-container">$HALT$</span> must have large circuit complexity -- if it didn't then this function would have low complexity also.</p>

<p>Although it seems related, I don't think this argument gives anything for <span class="math-container">$K(HALT_n)$</span>. (It could be that the time-bounded Kolmogorov complexity of <span class="math-container">$HALT$</span> is large, as implied by the circuit complexity bound, but as the time restriction is relaxed the complexity drops off dramatically.) I think the analogous argument shows that, if we had an oracle to the halting problem, then we could support random-access queries to the lexicographically first incompressible string. But, we must make a series of adaptive queries, and this can't be reduced directly to <span class="math-container">$HALT$</span> as far as I know. Also, the query strings must be exponentially large afaik, so it ends up showing only that <span class="math-container">$HALT_{2^n}$</span> has complexity at least <span class="math-container">$2^n$</span> afaict, and this doesn't beat the ``folklore'' argument.</p>

<p>My background in Kolmogorov complexity is rather weak unfortunately, is <span class="math-container">$K(HALT_n)$</span> already known by some other argument? Perhaps there's a trick using Symmetry of Information?</p>

<p>Or, is there a better upper bound that I've missed?</p>

<p>One thing that may seem odd is that, switching back to the <span class="math-container">$DTIME$</span> setting, we only expect to get an advice lower bound when we reduce the time below the naive algorithm. When you have enough time to run the naive algorithm, then obviously it is compressible. In the case of <span class="math-container">$K(HALT_n)$</span>, there's no time bound at all, so perhaps we have ``the same'' amount of time as the adversary, and shouldn't expect it to be maximally incompressible. Nevertheless, diagonalization works in the unrestricted setting too -- it seems that for any machine, there's a machine that does the same thing as that machine and then does something else, so there's always someone who has more time than you do. So perhaps the adversary always has more time than us after all...</p>

<cc.complexity-theory><reference-request><computability><lower-bounds>
Is the Kolmogorov complexity of the truth tables of the halting problem known asymptotically?
Chris Beck
# Is the Kolmogorov complexity of the truth tables of the halting problem known asymptotically?

(Asked by: username_0 on 2017-01-30)

Let $HALT\_n$ denote the string of length $2^n$ corresponding to the truth table of the halting problem for inputs of length $n$.

If the sequence of Kolmogorov complexities $K(HALT\_n)$ were $O(1)$, then one of the advice strings would be used infinitely often, and a TM with that string hard-coded would be able to solve $HALT$ uniformly infinitely often, which we know isn't the case.

A closer inspection of the diagonalization argument actually shows that $K(HALT\_n)$ is at least $n - \omega (1)$, so together with the trivial upper bound, we have:

$n - \omega(1) \leq K(HALT\_n) \leq 2^n + O(1)$

This lower bound is noted in the intro of a recent paper of Fortnow and Santhanam [``New Non-uniform Lower Bounds for Uniform Complexity Classes''](http://drops.dagstuhl.de/opus/volltexte/2016/5850/pdf/29.pdf), and they attribute it to folklore. Basically, if the advice string is shorter than the input length, then we can still diagonalize against machines with at most that amount of advice.

(Edit: Actually, in an earlier version of the paper they attributed it to folklore, I guess now they just say it's an adaptation of Hartmanis and Stearns.)

Actually, in that paper they are concerned with Time-hierarchy theorems, and they state things relative to a resource bound of $t$ time steps, rather than the unrestricted Kolmogorov complexity. But, the proof of the ``folklore'' result is the same in the unrestricted case.

---

One of the reasons they care about advice lower bounds, is that it is connected to circuit lower bounds and derandomization in the ``hardness vs. randomness'' paradigm. For instance, if the canonical problem solvable in time $2^n$ has truth tables which require advice $2^{\epsilon n}$ in order to be computed in time $2^{\epsilon n}$, then those truth tables don't have circuits of size $2^{\epsilon n}$ either, so $P = BPP$ by a celebrated result of Impagliazzo and Wigderson.

Asking about $K(HALT\_n)$ instead doesn't have any such applications afaik, but it might be easier to resolve. It's also easier to state, lacking any dependence on a time bound parameter -- it's a rather natural problem which might already have been studied.

Are there any better lower or upper bounds on $K(HALT\_n)$ known besides the ``folklore'' result? Is either of the lower or upper bounds above tight?

---

Note: There is another nice post about the *circuit complexity* of the halting problem, which can be seen to be nearly maximal by an argument sketched by Emil Jerabek here: <https://mathoverflow.net/questions/115275/non-uniform-complexity-of-the-halting-problem>

Basically, it uses a trick where we can compute (with random access) the lexicographically first truth table of (large) circuit complexity within the class $E^{NP^{NP}}$. And we can reduce this computation to a query to the halting problem, and this reduction has low circuit complexity. So, $HALT$ must have large circuit complexity -- if it didn't then this function would have low complexity also.

Although it seems related, I don't think this argument gives anything for $K(HALT\_n)$. (It could be that the time-bounded Kolmogorov complexity of $HALT$ is large, as implied by the circuit complexity bound, but as the time restriction is relaxed the complexity drops off dramatically.) I think the analogous argument shows that, if we had an oracle to the halting problem, then we could support random-access queries to the lexicographically first incompressible string. But, we must make a series of adaptive queries, and this can't be reduced directly to $HALT$ as far as I know. Also, the query strings must be exponentially large afaik, so it ends up showing only that $HALT\_{2^n}$ has complexity at least $2^n$ afaict, and this doesn't beat the ``folklore'' argument.

My background in Kolmogorov complexity is rather weak unfortunately, is $K(HALT\_n)$ already known by some other argument? Perhaps there's a trick using Symmetry of Information?

Or, is there a better upper bound that I've missed?

One thing that may seem odd is that, switching back to the $DTIME$ setting, we only expect to get an advice lower bound when we reduce the time below the naive algorithm. When you have enough time to run the naive algorithm, then obviously it is compressible. In the case of $K(HALT\_n)$, there's no time bound at all, so perhaps we have ``the same'' amount of time as the adversary, and shouldn't expect it to be maximally incompressible. Nevertheless, diagonalization works in the unrestricted setting too -- it seems that for any machine, there's a machine that does the same thing as that machine and then does something else, so there's always someone who has more time than you do. So perhaps the adversary always has more time than us after all...

**Tags:** cc.complexity-theory, reference-request, computability, lower-bounds


---

## 1 answers

### Answer by username_0 on 2017-01-30. Score: 17 | Accepted answer

Hmm, turns out there's actually an matching upper bound that isn't too hard:

To produce the truth table $HALT\_n$ in a finite amount of time, the only information that is needed is the number of machines of description length at most $n$ which halt. This number is not more than $2^{n}$, so it can be represented with about $n$ bits, and say the number is $m$. Then we can start all such machines in parallel and run them until $m$ many of them halt and so we can stop simulating since the remainder are known not to be halting

So, I guess the folklore argument is tight here. We have

$n - \omega(1) \leq K(HALT\_n) \leq n + O(1)$

and $K(HALT\_n)$ is only well-defined up to additive $O(1)$ anyways, depending on our choice of universal Turing machine.

N.B.: As a cute bonus, this proof shows that the $n$-bit string corresponding to the number of machines of description length at most $n$ which halt is an incompressible string -- if it were compressible, then the upper bound here would be tighter, contradicting the lower bound.

> **Comments:**
> **username_1**: This bound is also mentioned in https://cstheory.stackexchange.com/q/14445.  

---

