MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
up vote 3 down vote accepted

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$.

share|cite|improve this answer
This is just like the usual argument that Kolmogorov complexity is not computable. – Joel David Hamkins Feb 26 '11 at 19:26
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. – Garabed Gulbenkian Mar 3 '11 at 18:40
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". – Garabed Gulbenkian Mar 3 '11 at 18:51
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. – Garabed Gulbenkian Mar 7 '11 at 20:08

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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