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.
1 Answer
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$.
-
$\begingroup$ This is just like the usual argument that Kolmogorov complexity is not computable. $\endgroup$ 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$ 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$ 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$ Mar 7, 2011 at 20:08