O'Reilly logo

Theory of Computation by George Tourlakis

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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 images. 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 images 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 images. Second, we mathematically establish that this function is a member of images, showing therefore that imagesimages. This says more than “there exists an intuitively computable” f ∉ , since we produce a provably computable such f, by placing ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required