In fact, it happens that any recursive function can be written down using minimization at most once (the other primitive recursive operations are used numerous times); this follows from proving that Turing machines can compute any recursive function, and then seeing that when you simulate a Turing machine using recursive functions, computing the state of the machine and its tape at time T is primitive recursive; to simulate the machine until it halts, one needs only add one minimization.

The fact that the definitions of computable functions and recursive functions are so different, yet the resulting class of functions is the same, leads to the Church Turing thesis.

Log in or register to write something here or to contact authors.

Sign up