# Minimal requirements for Kleene's recursion theorem

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.

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.