2
$\begingroup$

Consider a set $M_n$ of all Turing machines with at most $n$ states. What is the smallest number of states (asymptotically in $n$) a Turing machine must have in order to solve halting problems for all machines in $M_n$?

Clearly, the answer is at least $n-O(1)$ (use the standard argument showing that the halting problem is undecidable). It is also clear that $\approx n^n$ states suffice since this is roughly the cardinality of the set $M_n$.

Is it possible to prove an exponential lower bound, say?

Improve this question
$\endgroup$
2
  • $\begingroup$ Though the exact asymptotics may need to be checked, it seems to me that your question is answered by the section “Relationship to the halting problem” in Wikipedia's article on Chaitin's constant. $\endgroup$
    – Gro-Tsen
    Commented Aug 15, 2019 at 23:03
  • $\begingroup$ @Gro-Tsen Thanks! It seems like passing to the prefix-free universal computable function will slightly increase the length, though. Or is it possible to do with the length being $O(n)$ where $n$ is the number of states? If you directly do the sum over possible Turing machines summing something like $n^{-10n}$ for each machine that halts, then knowing $O(n\log{n})$ bits of that number should suffice. $\endgroup$
    – Dmitry Krachun
    Commented Aug 16, 2019 at 1:17

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .