Theory of Computation

2.4   A DOUBLE RECURSION THAT LEADS OUTSIDE THE PRIMITIVE RECURSIVE FUNCTION CLASS

We saw in Subsection 2.2.2 that there are intuitively computable total functions that are not in . This means that this class is an inadequate, or incomplete, formalization of the concept “total computable function”. While the proof that our counterexample function is not in can be trivially completed into a mathematical proof, the part about it being “intuitively” computable was informal by virtue of the imprecision in the term “intuitively computable”. The current section revisits this issue in a totally mathematical fashion. First, we produce a total function that is provably not in . Second, we mathematically establish that this function is a member of , showing therefore that ⊂ . This says more than “there exists an intuitively computable” f ∉ , since we produce a provably computable such f, by placing ...