4
$\begingroup$

Kleene's recursion theorem guarantees that any Turing complete language must have quines. However, consider the following quine (in C, taken from the Quine page):

 char*f="char*f=%c%s%c;main()
 {printf(f,34,f,34,10);}%c";
 main(){printf(f,34,f,34,10);}

It makes no use of while or recursive functions, or any other of the features that make C Turing complete. It would work just fine in a subset of C that included only printf and basic string manipulations.

This makes me wonder whether Turing completeness is really necessary for the proof of Kleene's recursion theorem. Does the proof actually require it? If not, what is the most general class of languages to which the theorem applies?

Note that I'm not asking for the most general class of languages that have quines (which would be rather trivial), but the most general class of languages that have quines because of Kleene's recursion theorem. That is, I'm asking for the minimal set of language features needed to implement the recursion trick that's used in the most conservative proof of the theorem, thus guaranteeing that all languages within that class must have quines. Presumably the set of all languages that implement these features will be a subset of the set of all languages that exhibit quines, but it might be a superset of the Turing complete languages.

The Wikipedia page hints at this with the following text:

However, a direct proof of Kleene's theorem (Kleene 1952: p. 352-353) does not make use of a universal program, which means that the theorem holds for certain subrecursive programming systems that do not have a universal program.

I don't currently have access to that reference, and I would like to know precisely which set of "subrecursive programming systems" this is referring to.

$\endgroup$
4
$\begingroup$

I stumbled upon a (partial) answer myself, in David Madore's essay about quines. I quote,

A different, perhaps more satisfactory, way of stating the fixed-point theorem would be to eliminate the universality theorem from it, and to say: for every computable function $k$ there exists a $n$ such that $\phi_n(\dots) = k(n\dots)$. This corresponds more precisely to the intuitive content we have described. It is proved without the use of the universality theorem, using only the s-m-n theorem (for the actual proof, take the proof we have just given, and replace $\phi_{h(x)}(\dots)$ by $k(x\dots)$ everywhere). The advantage of formulating things like this is we see that it also works for primitive recursive functions (which satisfy s-m-n but not universality), so in effect a primitive recursive function can also make use of its own number. By applying the universality theorem (the function $\phi_{h(x)}(\dots)$ is computable, so we can call it $k(x\dots)$) we recover the fixed-point theorem as we have stated it.

So Kleene's fixed point theorem goes through at least for primitive recursive functions. It might still be that there's an even simpler class of languages that it also applies to, and I won't accept my own answer in case someone else has more to say on that topic. But for now I'm happy knowing this.

$\endgroup$

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.