# A question about the “information-content” of a very simple type of Turing machine.

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.

-

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