Repeated minimization

Question

As I understand, the Ackerman function is not primitive recursive because it needs unbounded number of primitive recursion (to oversimplify things, addition needs one primitive recursion. Multiplication needs two primitive recursion. Exponentiation needs three primitive recursion, and so on, so A(n) in general needs n primitive recursion.)

With minimization, the Ackerman function can be defined. The question is, isn't there an "Ackerman function for minimization"? That is, isn't there a function that needs unbounded number of minimization? The answer seems to be no because if there is one, then the function is not recursive and yet seems to be "computable", violating the Church-Turing thesis. But why isn't there one?

Answer 1

Kleene's normal form theorem says that there are two total computable (actually primitive recursive) functions $U$ and $T$ so that, for every computable function $\phi(n)$ there is an $e$ so that $$ \phi(n) \simeq U(\mu s. T(e,n,s)). $$ So every computable function can be implemented with exactly one minimization, applied to a total computable predicate.

In particular, the normal form theorem applies to any function $\phi(n)$ that can be programmed into a Turing machine. So no matter how you try to program the machine to use multiple minimizations, the overall function could be re-implemented to use just one.

The method is not to combine the minimizations. Instead, we simply simulate the original Turing machine for one step, two steps, three steps, etc., and if we ever see it halt, then we return its result. This simulation up to $s$ steps is done by $T$, so there is only one minimization, over the number of steps that the Turing machine runs.