The halting problem is well-known to be uncomputable. However, it is possible to exponentially "compress" information about the halting problem, so that decompressing it is computable.

More precisely, it is possible to compute from a description of $2^{n}-1$ Turing machines and an $n$-bit advice state the answer to the halting problem for all $2^{n}-1$ of the Turing machines, assuming the advice state is trustworthy - we let our advisor choose the bits to describe how many of the Turing machines halt in binary, wait until that many halt, and output that the remainder do not halt.

This argument is a simple variant of the proof that Chaitin's constant can be used to solve the halting problem. What surprised me is that it is sharp. There is no computable map from a description of $2^n$ Turing machines and an $n$-bit advice states to $2^n$ bits of halting output that gets the right answer, for each tuple of Turing machines, for some tuple of bits. If there were, we could produce a counterexample by diagonalizing, with each of the $2^n$ Turing machines simulating what the program does on one of the $2^n$ possible arrangements of the $n$ bits and then choosing its own halting state to violate the prediction.

It is not possible to compress information about the halting problem for Turing machines with a halting oracle at all (without access to some kind of oracle yourself). The machines can just simulate what you predict on all possible inputs, ignoring the ones where you don't halt, and choosing their halting times to give the lexicographically first answer you didn't predict on any input.

This motivated me to think about what happens for other oracles:

Is there an example of an oracle where the halting problem for Turing machines with that oracle can be compressed at an intermediate growth rate between linear and exponential?

More formally, given an oracle, let $f(n)$ be the greatest $m$ such that there exists a computable partial function from $m$ oracle Turing machines and $n$ bits to $m$ bits, such that for each $m$-tuple of oracle Turing machines, there is an $n$-tuple of bits, where the value of the function evaluated on that input equals the $m$-tuple of $1$ for each oracle Turing machine that halts and $0$ for each oracle Turing machine that runs forever.

Is there an oracle where $n<f(n)<2^{n}-1$? Is there an oracle where $\omega(n)=f(n)=o(2^n)$?


1 Answer 1


Let $J^A(e)$ be the output of the $e$th Turing machine equipped with oracle $A$, on input $e$. Here $J$ stands for "jump". (In case of non-halting, $J^A(e)$ is undefined.)

An oracle $A$ is jump-traceable if there is a computable nondecreasing function $h:\mathbb N\to\mathbb N$ such that for all $e$, $J^A(e)\in T_e$ for some computably enumerable family of finite sets $(T_e)_{e\in\mathbb N}$ with $|T_e|\le h(e)$ for all $e$.

Let's consider $f^A(k,n)=$the string of length $n$ indicating which are the first $k$ of the Turing machines numbers $0,\dots,n-1$ to halt. (If fewer than $k$ halt, $f^A(k,n)$ is undefined.)

Note that $f^A$ is partial computable relative to $A$. Thus there is a computable function $g$ such that $f^A(k,n)=J^A(g(k,n))$.

To compress the first $n$ bits of the halting set for $A$ it suffices to say which one of of the $h(e)$ many elements of $T_e$ is the right one, where $e=g(k,n)$ and $k$ is the correct number of halting TMs.

There is a proper hierarchy of jump-traceable oracles (Nies, Computability and Randomness, Theorem 8.5.2). So by choosing $h$ appropriately small, we get a candidate for an oracle $A$ as you asked for.

It is a reasonably good candidate in the sense that we have one direction (the upper bound on the growth rate) and that provably the method by which we obtained the upper bound does not give any much smaller upper bound than that.

  • $\begingroup$ This looks like an approach to a slightly different problem, which asks about the first $n$ Turing machines rather than an arbitrary set of $n$ Turing machines. However, that problem seems interesting too. I agree that it is plausible that, for a "generic" jump-traceable oracle, the upper bound you give should be close to tight. $\endgroup$
    – Will Sawin
    Oct 4, 2017 at 23:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.