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?
Turing Machine that computes maximum steps of halting machines
turing machines;halting problem
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.