3
$\begingroup$

All the Turing machines we consider have (1) a two-way infinite tape (2) one and only one halting state (3) an alphabet of exactly two symbols-"1" and " "(or "blank"). Let n be any positive integer. Let H(n) be the smallest number of active states that such a Turing machine needs in order that, starting with one of its active states scanning an all "blank" tape, it will eventually halt when exactly n of the cells on its tape contain the symbol "1". Can H(n) be a recursive function of n? I believe the answer is "no" because of certain theorems due to G. Chaitin which apply to situations that are rather similar. But I do not see a way to prove it.

$\endgroup$

1 Answer 1

3
$\begingroup$

Suppose your function were computable. First observe that the function $H$ cannot be bounded, because there are only finitely many programs of a given size. Consider now the algorithm that searches for a number $n$ for which $H(n)$ is very large. For example, we could design such a program using some fixed $r$ number of states, that searched for a number $n$ such that $H(n)\gt r$, outputting it when found. (We can do this because with comparatively few states, we can produce enormous numbers, such as stacks of powers of $2$, and then with comparatively few extra states beyond the size of the program computing $H$, we can implement our algorithm to search for $n$ whose $H(n)$ value is at least that enormous number, and then pad with extra dummy states.) By our observation about $H$ not being bounded, our algorithm will succeed. This is a contradiction, since our program outputs $n$ but uses only $r$ states, whereas $H(n)\gt r$.

$\endgroup$
4
  • $\begingroup$ This is just like the usual argument that Kolmogorov complexity is not computable. $\endgroup$ Commented Feb 26, 2011 at 19:26
  • $\begingroup$ Thanks alot, Joel, for your answer. I am trying to prove that it implies the follwing: Let Q(n) be a recursive mapping of the set of all non-negative integers into itself which approaches infinity as n does. $\endgroup$ Commented Mar 3, 2011 at 18:40
  • $\begingroup$ Then there exist positive integers k,r such that (1)Q(k) is greater than r and (2)a Turing machine of the type described above having at most r active states, if started from one of its active states on an all "blank" tape, eventually halts when exactly k cells on the tape contain the symbol "1". $\endgroup$ Commented Mar 3, 2011 at 18:51
  • $\begingroup$ I believe that I have found a proof, provided that I change my hypothesis so as to require Q(n) to be a recursive mapping of the set N of all non-negative integers onto itself. This change does not cause any problems since H(n)-which I am trying to prove non-computable-is also , in fact, a mapping of N onto itself. $\endgroup$ Commented Mar 7, 2011 at 20:08

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.