6
$\begingroup$

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

Improve this question
$\endgroup$
9
  • $\begingroup$ 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$. $\endgroup$
    – Marzio De Biasi
    Nov 23, 2012 at 20:07
  • $\begingroup$ @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. $\endgroup$
    – Vanessa
    Nov 23, 2012 at 20:19
  • $\begingroup$ 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$ $\endgroup$
    – Marzio De Biasi
    Nov 23, 2012 at 20:24
  • $\begingroup$ @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$ $\endgroup$
    – Vanessa
    Nov 23, 2012 at 20:32
  • $\begingroup$ ok, now it's clear :) $\endgroup$
    – Marzio De Biasi
    Nov 23, 2012 at 20:57

2 Answers 2

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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)$. $\endgroup$
    – Colin McQuillan
    Nov 23, 2012 at 15:58
  • $\begingroup$ @ColinMcQuillan: you are right, the bound is the same (the exponent confused me). $\endgroup$
    – Marzio De Biasi
    Nov 23, 2012 at 16:28
4
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ I think this should be a CW. $\endgroup$
    – Kaveh
    Dec 6, 2012 at 6:45

Your Answer

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