Kleene's Recursion Theorem in his Introduction to Metamathematics $\S66$ is written

Theorem XXVI:
For any $n\geq0$, let $\textbf{F}(\zeta;x_1,...,x_n)$ be a partial recursive functional, in which the function variable $\zeta$ ranges over partial functions of $n$ variables. Then the equation $$\zeta(x_1,...,x_n)\simeq\textbf{F}(\zeta;x_1,...,x_n)$$ has a solution $\phi$ for $\zeta$ such that any solution $\phi'$ for $\zeta$ is an extension of $\phi$, and this solution $\phi$ is partial recursive.

After proving this he very briefly discusses how this theorem supports Thesis I (Church): Every effectively calculable function is general recursive.

My question is: In w does this theorem support Church's thesis? What might be a good example of an effectively calculable function using ordinary language which through Theorem XXVI is shown to be partial recursive?


The theorem you quote says, essentially, that the class of "partial recursive" functions is closed under general recursive definitions. ($\mathbf F$ serves as a defintion of $\phi$ in terms of itself, that is, a general recursive definition).

This sounds somewhat tautological, but I assume that "partial recursive" at this point already has a meaning that has been defined without allowing general recursive definitions.

Church's thesis states that there is a natural class of functions that we ought to call "effectively calculable", in the sense that a wide range of attempts to formalize "effectively calculable" functions turn out all to define this class. Whenever we investigate a new proposal for formalizing "effectively calculable" and find that it gives us the same class as before, that's a measure of support for the general thesis.

In this case, I think the idea is that we have already tentatively identified the "partial recursive" functions as the effectively calculable ones. Now we're considering this class of functions

Everything that we already allowed for "partial recursive" functions is allowed, and in addition you can use general recursive definitions.

The theorem then shows that this gives you exactly the partial recursive functions once again. So this is one of the many equivalent ways to define "effectively calculable", supporting the thesis that there are many such ways.

Since the point is that the new form of definition does not increase the expressive power, you can't get a function where you need this theorem to show it is partial recursive. But it can be a shortcut. For example, if we want to define Ackermann's function, $$ A(m, n) = \begin{cases} n+1 & \text{if } m = 0 \\ A(m-1, 1) & \text{if } m > 0 \text{ and } n = 0 \\ A(m-1, A(m, n-1)) & \text{if } m > 0 \text{ and } n > 0. \end{cases} $$ we can apply the theorem to the functional $$ \mathbf F(\zeta; m, n) = \begin{cases} n+1 & \text{if } m = 0 \\ \zeta(m-1, 1) & \text{if } m > 0 \text{ and } n = 0 \\ \zeta(m-1, \zeta(m, n-1)) & \text{if } m > 0 \text{ and } n > 0. \end{cases} $$ Since the $A$ we have defined (informally) above is clearly (?) the unique solution to $\zeta(\cdots)=\mathbf F(\zeta;\cdots)$ in this case, the theorem tells us that there is some way to define $A$ using the machinery already allowed for partial recursive functions (which is typically something like primitive recursion, plus successor, projections and composition, plus some kind of minimization or unbounded search operator). This definition might be complex and not particularly intuitive, however -- all the theorem tells us that it exists.

  • $\begingroup$ @BENG: Hmm, no, then I've got nothing. $\endgroup$ – hmakholm left over Monica Jun 13 '19 at 0:48
  • $\begingroup$ I reread what you mentioned where you allow partial recursive functions as well as general recursive functions. That is the class you are talking about, highlighted. $\endgroup$ – BENG Jun 13 '19 at 0:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.