Problem Detail: Suppose that $TM_{halting}$ is the set of machines that halt. Given a number of states $m$ and a length $n$ of the input, let $f(m,n)$ be the maximum number of steps a machine with $m$ states in $TM_{halting}$ can take on an input of length $n$. Is the function $f(m,n)$ computable?
Asked By : revisingcomplexity
Answered By : Yuval Filmus
Hint: If you could compute $f(m,n)$, then given a Turing machine $M$ with $m$ states and an input $x$ of length $n$, the Turing machine will either stop within $f(m,n)$ steps or never halt. This argument actually shows that it is impossible to compute any upper bound on $f(m,n)$. In other words, $f(m,n)$ grows faster than any computable function.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/41926
