[Solved]: Turing Machine that computes maximum steps of halting machines

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