0

Assume that we have a Turing machine which on an empty input, with $n > 100$ states worked $n^{ n^n}$ steps. Can we guarantee that in this case the computation will never stop?

fenry
  • 35
  • 1
    Are you familiar with the halting problem? – sbares May 03 '20 at 11:40
  • 1
    @Hayden if running for $n^{n^{n}}$ steps, or indeed any computable function of $n$, was sufficient to prove the TM does not halt, then you could solve the halting-problem by simply running the machine for $n^{n^{n}}$ steps. – sbares May 03 '20 at 11:47
  • @SBareS Yes, and the condition that there are at least 101 states can be dispensed with by simply adding additional states which do nothing. – Hayden May 03 '20 at 11:49
  • 1
    The busy-beaver function $\Sigma(n)$ which gives the number of steps we would need to be sure that the machine never halts grows with $n$ faster than every computable function $f(n)$. The bound $n^{n^n}$ would already fail for $n=7$ since it is known that $\Sigma(7)$ is much much larger than $7^{7^7}$. Wythagoras showed that $\Sigma(7)$ is larger than a power tower of five tens , hence $7^{7^7}$ is totally left in the dust. – Peter May 03 '20 at 12:05

1 Answers1

1

I'll elaborate a bit on my comments. Let $f$ be any computable function, for example $f(n)=n^{n^n}$. If an $n$-state Turing machine running for $f(n)$ steps was sufficient to prove that it never halts, then you could solve the halting problem by simply simulating the TM for $f(n)$ steps. Since the halting problem is undecidable, no computable function of the number of states can give an upper bound for how long a TM can run before halting. Incidentally, there is such an upper bound in the form of the busy beaver function, but the catch is that it is not computable.

sbares
  • 4,063