Is the Kolmogorov complexity of the truth tables of the halting problem known asymptotically?

Question

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'', 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...

Answer 1

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.