<p>The question was answered by Emil Jerabek at <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>

CC BY-SA 3.0
2012-12-06T06:45:41.320Z
I think this should be a CW.
Kaveh
CC BY-SA 3.0
2012-12-03T18:34:41.000Z
2012-12-03T18:34:41.000Z
2017-04-13T12:57:54.777Z
Vanessa
<p>Just an extended comment: I'm not an expert, but for what regards 1., something can be said if you interpret: $HALT(k) = 1$ iif $TM_k$ halts on the <em>empty tape</em>.</p>

<p>In this case the string $s$ that lists the first $n$ bits $HALT(k)$, $k = 1,2,...,n$ is highly compressible:</p>

<ul>
<li>$|s|=n$</li>
<li>let $h$ be the number of halting TMs between $1$ and $n$ ($h \leq n$)</li>
</ul>

<p>If you know $h$, in order to build $s$ you can simply simulate all TMs between $1$ and $n$ and when $h$ of them stops you have enough information to reconstruct $s$ (you have the positions of the $1$s, the other can be set to $0$s).</p>

<p>So $K(s) = \lceil \log h \rceil + c$</p>

<p>If you interpret $HALT(k) = 1$ iif $TM_k$ halts on <em>all inputs</em>, then:</p>

<p>$K(s) =  min\{n, K(\lceil \log n \rceil, \lceil \log z \rceil )\} + c$</p>

<p>Where $z$ is the minimum number such that for every <em>non halting</em> $TM_k$ in 1..n exists $y \leq z$ such that $TM_k(y)$ doesn't halt. Informally you can simulate the $n$ TMs on inputs $1..z$ being sure that those who halts are the only TMs that always halts on all inputs.</p>

<p>Perhaps the same reasoning can be applied to points 2. and 3.</p>

CC BY-SA 3.0
2012-11-23T15:58:03.207Z
In the question $K(n)=(\mathrm{HALT}(1),...,\mathrm{HALT}(2^n))$. Your argument is quite similar to the argument given in the question for $K(n)=O(n)$.
Colin McQuillan
CC BY-SA 3.0
2012-11-23T16:28:47.480Z
@ColinMcQuillan: you are right, the bound is the same (the exponent confused me).
Marzio De Biasi
CC BY-SA 3.0
2012-11-23T14:13:16.710Z
2012-11-23T14:13:16.710Z
Marzio De Biasi
<p>One of the most celebrated results in computer science is that the halting problem is undecidable. However there are still notions of complexity that are applicable. Here are 3 that I have in mind:</p>

<ol>
<li>$K(n)$ is the Kolomogorov complexity of the string $h_{&lt;2^n}$ of length $2^n$ whose $k$-th bit is 1 iff the $k$-th program halts</li>
<li>$C(n)$ is the minimal size of a Boolean circuit solving the halting problem for programs of size at most $n$</li>
<li>$T(n)$ is the time complexity of the halting problem made solvable by introducing an extra-tape into our Turing machine on which an infinite bit-string is written in the initial state. For example the bit-string can be an infinite look-up table: the $k$-th bit is 1 iff the $k$-th program halts. This allows a simple look-up algorithm to solve the halting problem but the complexity would be $O(2^n)$</li>
</ol>

<p>$K$ is at most $O(n)$ since we can construct a program which encodes the longest-running program of length $n$ and checks whether the input program halts before that one. $C(n)$ is at most $O(2^n)$ because we can construct a "look-up table" circuit and $T(n)$ is at most $O(2^n)$ as noted above</p>

<p>What other bounds on $K$, $C$, $T$ can be found? In particular, are $C$ and/or $T$ less than exponential?</p>

<p>EDIT: Actually, $K(n) = n + O(1)$. To see this, consider $H_n$ an algorithm solving the halting problem for all inputs of length at most $n$ and $P$ the following program. </p>

<p>$P$ runs $H_n$ on $P$ itself. If result is "halts", it goes into an infinite loop. If result is "doesn't halt", it terminates.</p>

<p>$H_n$ fails to evaluate $P$'s halting correctly therefore the length of $P$ is greater than $n$. On the other hand $P$ is only longer than $H_n$ by a constant so $H_n$ can't be much shorter than $n$.</p>

<p>EDIT: If the halting problem is in $P/poly$ i.e. $C$ is polynomial, then $NP \subset P/poly$ (which implies $PH = \Sigma_2$). To see this consider $S \subset \{0,1\}^*$ a decision problem in $NP$ and $V$ a verifier program for $S$. Deciding whether $x \in S$ is equivalent to solving the halting problem for the following program $Q_x$: "Loop over all $p \in \{0,1\}^*$, halt if $V(x,p) = 1$". The size of $Q_x$ is the same as the size of $x$, up to a constant. Therefore if we can solve the halting problem for $Q_x$ in polynomial time with polynomial advice, we can decide $x \in S$ in polynomial time with polynomial advice</p>

<p>Note that $C$ is polynomial iff $T$ is polynomial. Consider $R_n$ a family of circuits solving the halting problem. Then we can construct an infinite-advice program $H$ for solving the halting problem by encoding $R_n$ as advice. This yields</p>

<p>$$T(n) = O(n \, C(n) \ln C(n))$$</p>

<p>On the other hand if we have $H$ an infinite-advice program solving the halting problem, we can construct a circuit $R_n$ representing the computation process of $H$ on an input of size $n$. The size of this circuit is the product of the spatial complexity by the temporal complexity so</p>

<p>$$C(n) = O(T(n)^2)$$</p>

<p>EDIT: If the halting problem is in $coNP/poly$ then $NP \subset coNP/poly$. This is due to reasoning similar to above i.e. an existential quantifier can be replaced by a universal quantifier at the cost of requiring polynomial advice. I think this also implies some kind of collapse of the polynomial hierarchy</p>

<p>EDIT: It is possible to construct a specific infinite-advice algorithm of optimal complexity, analogous to Levin search for $NP$ problems. As opposed to the case of $NP$, there is no way to verify correctness of solutions, on the other hand it is possible to restrict the dovetailing only to valid programs. This is done by encoding all programs which solve the halting problem together with their respective infinite advice sequences in the infinite advice of our algorithm. The penalty incurred by using this encoding is at most polynomial, hence the resulting algorithm has complexity which is optimal up to a polynomial</p>

CC BY-SA 3.0
2012-11-23T20:07:25.763Z
There is no algorithm $H$ that solves the halting problem for all inputs of length $n$ where $n$ is an input of $H$. So you should say that $H_k$ solves the halting problem for all programs of length less than a constant $k$ (and on the other programs outputs DONTKNOW or loop forever). But P *can run* H on P itself (and avoid a  DONTKNOW result) only if $|P| < k$.
Marzio De Biasi
CC BY-SA 3.0
2012-11-23T20:19:41.357Z
@Marzio De Biasi : $n$ is not an input of $H$. $n$ is a fixed constant i.e. we need a different $H$ for each $n$. I'll rename $H$ to $H_n$ and hopefully it will clarify.
Vanessa
CC BY-SA 3.0
2012-11-23T20:24:45.910Z
ok, but with my comment I only wanted to underline the condition that if you run (simulate) $H_n$ on $P$, the length of $P$ *must* be $\leq n$
Marzio De Biasi
CC BY-SA 3.0
2012-11-23T20:32:41.247Z
@MarzioDeBiasi: You are saying essentially the same thing I'm saying only I'm saying it a bit differently. For me $H_n$ *can* be run on inputs longer than $n$ but then the result is not necessarily correct. Thus $P$ *can* run $H_n$ on itself but the result will be wrong, since a right result would result in a contradiction. *Since* the result is wrong, the length of $P$ is greater than $n$
Vanessa
CC BY-SA 3.0
2012-11-23T20:57:12.760Z
ok, now it's clear :)
Marzio De Biasi
CC BY-SA 3.0
2012-11-23T21:28:58.073Z
As far as 2 goes, isn't it known that circuits in $\mathsf{P}_{/\mathsf{Poly}}$ can decide HALT, due to non-uniformity?
Nicholas Mancuso
CC BY-SA 3.0
2012-11-24T04:54:50.333Z
@NicholasMancuso The *unitary* form of *any* decision problem is in P/poly. This is obvious, it is equivant to the statement that C is at most exponential. However if HALT itself is in P/poly then NP is contained in P/poly, for a reason I will explain soon in the body of the question
Vanessa
CC BY-SA 3.0
2012-11-24T18:36:19.713Z
@Squark, Ah I see. Thank you for explaining.
Nicholas Mancuso
CC BY-SA 3.0
2012-12-03T18:40:19.920Z
somewhat related see eg answer to [algorithm to solve halting problem](http://cs.stackexchange.com/a/4866/699), cs.se
vzn
<cc.complexity-theory><time-complexity><circuit-complexity><advice-and-nonuniformity><halting-problem>
Complexity of the halting problem
Vanessa
# Complexity of the halting problem

(Asked by: username_0 on 2012-11-23)

One of the most celebrated results in computer science is that the halting problem is undecidable. However there are still notions of complexity that are applicable. Here are 3 that I have in mind:

1. $K(n)$ is the Kolomogorov complexity of the string $h\_{<2^n}$ of length $2^n$ whose $k$-th bit is 1 iff the $k$-th program halts
2. $C(n)$ is the minimal size of a Boolean circuit solving the halting problem for programs of size at most $n$
3. $T(n)$ is the time complexity of the halting problem made solvable by introducing an extra-tape into our Turing machine on which an infinite bit-string is written in the initial state. For example the bit-string can be an infinite look-up table: the $k$-th bit is 1 iff the $k$-th program halts. This allows a simple look-up algorithm to solve the halting problem but the complexity would be $O(2^n)$

$K$ is at most $O(n)$ since we can construct a program which encodes the longest-running program of length $n$ and checks whether the input program halts before that one. $C(n)$ is at most $O(2^n)$ because we can construct a "look-up table" circuit and $T(n)$ is at most $O(2^n)$ as noted above

What other bounds on $K$, $C$, $T$ can be found? In particular, are $C$ and/or $T$ less than exponential?

EDIT: Actually, $K(n) = n + O(1)$. To see this, consider $H\_n$ an algorithm solving the halting problem for all inputs of length at most $n$ and $P$ the following program.

$P$ runs $H\_n$ on $P$ itself. If result is "halts", it goes into an infinite loop. If result is "doesn't halt", it terminates.

$H\_n$ fails to evaluate $P$'s halting correctly therefore the length of $P$ is greater than $n$. On the other hand $P$ is only longer than $H\_n$ by a constant so $H\_n$ can't be much shorter than $n$.

EDIT: If the halting problem is in $P/poly$ i.e. $C$ is polynomial, then $NP \subset P/poly$ (which implies $PH = \Sigma\_2$). To see this consider $S \subset \{0,1\}^\*$ a decision problem in $NP$ and $V$ a verifier program for $S$. Deciding whether $x \in S$ is equivalent to solving the halting problem for the following program $Q\_x$: "Loop over all $p \in \{0,1\}^\*$, halt if $V(x,p) = 1$". The size of $Q\_x$ is the same as the size of $x$, up to a constant. Therefore if we can solve the halting problem for $Q\_x$ in polynomial time with polynomial advice, we can decide $x \in S$ in polynomial time with polynomial advice

Note that $C$ is polynomial iff $T$ is polynomial. Consider $R\_n$ a family of circuits solving the halting problem. Then we can construct an infinite-advice program $H$ for solving the halting problem by encoding $R\_n$ as advice. This yields

$$T(n) = O(n \, C(n) \ln C(n))$$

On the other hand if we have $H$ an infinite-advice program solving the halting problem, we can construct a circuit $R\_n$ representing the computation process of $H$ on an input of size $n$. The size of this circuit is the product of the spatial complexity by the temporal complexity so

$$C(n) = O(T(n)^2)$$

EDIT: If the halting problem is in $coNP/poly$ then $NP \subset coNP/poly$. This is due to reasoning similar to above i.e. an existential quantifier can be replaced by a universal quantifier at the cost of requiring polynomial advice. I think this also implies some kind of collapse of the polynomial hierarchy

EDIT: It is possible to construct a specific infinite-advice algorithm of optimal complexity, analogous to Levin search for $NP$ problems. As opposed to the case of $NP$, there is no way to verify correctness of solutions, on the other hand it is possible to restrict the dovetailing only to valid programs. This is done by encoding all programs which solve the halting problem together with their respective infinite advice sequences in the infinite advice of our algorithm. The penalty incurred by using this encoding is at most polynomial, hence the resulting algorithm has complexity which is optimal up to a polynomial

**Tags:** cc.complexity-theory, time-complexity, circuit-complexity, advice-and-nonuniformity, halting-problem
> **Comments:**
> **username_1**: There is no algorithm $H$ that solves the halting problem for all inputs of length $n$ where $n$ is an input of $H$. So you should say that $H_k$ solves the halting problem for all programs of length less than a constant $k$ (and on the other programs outputs DONTKNOW or loop forever). But P *can run* H on P itself (and avoid a  DONTKNOW result) only if $|P| < k$.  
> **username_0**: @Marzio De Biasi : $n$ is not an input of $H$. $n$ is a fixed constant i.e. we need a different $H$ for each $n$. I'll rename $H$ to $H_n$ and hopefully it will clarify.  
> **username_1**: ok, but with my comment I only wanted to underline the condition that if you run (simulate) $H_n$ on $P$, the length of $P$ *must* be $\leq n$  
> **username_0**: @MarzioDeBiasi: You are saying essentially the same thing I'm saying only I'm saying it a bit differently. For me $H_n$ *can* be run on inputs longer than $n$ but then the result is not necessarily correct. Thus $P$ *can* run $H_n$ on itself but the result will be wrong, since a right result would result in a contradiction. *Since* the result is wrong, the length of $P$ is greater than $n$  
> **username_1**: ok, now it's clear :)  
> **username_2**: As far as 2 goes, isn't it known that circuits in $\mathsf{P}_{/\mathsf{Poly}}$ can decide HALT, due to non-uniformity?  
> **username_0**: @NicholasMancuso The *unitary* form of *any* decision problem is in P/poly. This is obvious, it is equivant to the statement that C is at most exponential. However if HALT itself is in P/poly then NP is contained in P/poly, for a reason I will explain soon in the body of the question  
> **username_2**: @Squark, Ah I see. Thank you for explaining.  
> **username_3**: somewhat related see eg answer to [algorithm to solve halting problem](http://cs.stackexchange.com/a/4866/699), cs.se  

---

## 2 answers

### Answer by username_0 on 2012-12-03. Score: 4 | Accepted answer

The question was answered by Emil Jerabek at <https://mathoverflow.net/questions/115275/non-uniform-complexity-of-the-halting-problem>

> **Comments:**
> **username_4**: I think this should be a CW.  

---

### Answer by username_1 on 2012-11-23. Score: 4

Just an extended comment: I'm not an expert, but for what regards 1., something can be said if you interpret: $HALT(k) = 1$ iif $TM\_k$ halts on the *empty tape*.

In this case the string $s$ that lists the first $n$ bits $HALT(k)$, $k = 1,2,...,n$ is highly compressible:

* $|s|=n$
* let $h$ be the number of halting TMs between $1$ and $n$ ($h \leq n$)

If you know $h$, in order to build $s$ you can simply simulate all TMs between $1$ and $n$ and when $h$ of them stops you have enough information to reconstruct $s$ (you have the positions of the $1$s, the other can be set to $0$s).

So $K(s) = \lceil \log h \rceil + c$

If you interpret $HALT(k) = 1$ iif $TM\_k$ halts on *all inputs*, then:

$K(s) = min\{n, K(\lceil \log n \rceil, \lceil \log z \rceil )\} + c$

Where $z$ is the minimum number such that for every *non halting* $TM\_k$ in 1..n exists $y \leq z$ such that $TM\_k(y)$ doesn't halt. Informally you can simulate the $n$ TMs on inputs $1..z$ being sure that those who halts are the only TMs that always halts on all inputs.

Perhaps the same reasoning can be applied to points 2. and 3.

> **Comments:**
> **username_5**: In the question $K(n)=(\mathrm{HALT}(1),...,\mathrm{HALT}(2^n))$. Your argument is quite similar to the argument given in the question for $K(n)=O(n)$.  
> **username_1**: @ColinMcQuillan: you are right, the bound is the same (the exponent confused me).  

---

