# Does the recursion theorem give quines?

Wikipedia claims that the recursion theorem guarantees that quines (i.e. programs that output their own source code) exist in any (Turing complete) programming language.

This seems to imply that one could follow the algorithm given in the proof of the recursion theorem to create a quine. However, the proof of the recursion theorem (and indeed the recursion theorem itself) only seems to guarantee the existence of a program that outputs its own index, which is, strictly speaking, different from outputing it's source code.

The simple observation that no Turing machine whose tape alphabet consists solely of $0$'s and $1$'s can output its own source code, since its source code is a finite set of tuples, implies that quines cannot exist there. However, it seems likely as long as the alphabet is sufficiently rich (or the language sufficiently limited) it should be possible to write a bona fide quine.

Question 1. Can the proof of the recursion theorem be transformed into a quine in any sufficiently expressive programming language?

Question 2. If the answer to Question 1. is "no", how do we know if and when quines exist?

-
If we're talking about programs that output numbers (in some particular encoding), it must be possible to interpret the source code as such a number. In a reasonably expressive language it is possible (maybe even easy) to write a program that will translate from one particular encoding to another. – Robert Israel Oct 22 '12 at 22:48
In the context of Turing machines, a Quine would be a Turing machine program that takes no input, writes itself as output, and then halts. Such Turing machine programs do exist, by the recursion theorem; they are fixed points of the Turing-computable function $F$ that given $e$ produces a Turing machine program to print $e$. – Carl Mummert Oct 29 '12 at 0:43
@Quinn Culver: is there an aspect of the question that hasn't been answered? – Carl Mummert Oct 30 '12 at 11:49
@CarlMummert I'm still considering it. In particular, I'm trying to figure out how I would follow the proof to write a quine in any (sufficiently rich) language (other than one like LISP where self-reference is inherently possible). I'm not sure if I agree that it's just as good to output an index. It somehow seems better to output the bona fide code. Henning indicated that even that is possible, so I want to know exactly why and how. – Quinn Culver Oct 30 '12 at 12:17
Also, for all you know the index is the source code of the program, literally, if we use finite strings for our indexes. The use of natural numbers instead is just a choice of presentation, because we mathematicians typically study number-based rather than string-based models of computation. But we could perfectly well use "idealized C" as our model of computation, in which case all the inputs and outputs could be finite strings, literally including programs. – Carl Mummert Oct 30 '12 at 12:57

The Wikipedia article has an explicit example in LISP of how to use the method of the proof to generate a Quine. The proof of the recursion theorem is entirely constructive and syntactic, so it can be implemented in any other Turing complete language.

Looking at the section there called Proof of the second recursion theorem:

1. The programming language will be able to implement the function $h$ defined at the top of the proof, because $h$ is computable and the language is Turing-complete

• In particular, $h$ is a program that takes as input a program (source code) $x$ and produces as output a program (source code) $h(x)$. The source code given by $h(x)$ does the following: on input $y$, $h(x)$ first simulates the running of source code $x$ with itself as input. If that produces an output $e$, then $h(x)$ proceeds to simulate running the program $e$ with input $y$.
• The program $h$ can be implemented in any Turing complete language; the main point is that you have to write an interpreter for the language within the language itself, so that $h(x)$ can use that interpreter as a subroutine to simulate running any source code on any input.
2. Furthermore, the language will be able to implement $F \circ h$ because $F$ is also computable. To do this, just use the source code for $h$ and then use its output as an input to the source code for $F$.

3. Let $e_0$ be a specific program (source code) that implements $F \circ h$. Let $e = h(e_0)$.
4. Then the program $e$ will compute the same function as the program $F(e)$, as the proof shows.
5. Thus, in the special case where $F(e)$ returns source code for a program that does nothing but return $e$, because program $e$ computes the same function as $F(e)$, program $e$ also returns the source code for $e$ when it is run.

• In fact, program $e$ does something stronger than computing the same function: examining the proof show that program $e$ actually computes the source code for $F(e)$ and then runs (or interprets, or simulates) that. So if $F(e)$ has side effects, like printing something, $e$ has the same side effects.

For any Turing complete language, you can follow this sequence of steps to get a Quine in that language.

The interest for people who write Quines is generally to make ones that are shorter than the ones obtained by this method. The proof of the second recursion theorem is more general than is needed for that special purpose, and the Quines it generates would be very long, because the program that computes $h$ includes, in most cases, an interpreter for the language at hand. So to implement $h$ in $C$, you have to write a $C$ interpreter in $C$. This is why LISP gives a better example, because it is much more straightforward to interpret LISP in LISP.

-
I think my main concern is that we must consider every string to be a program; i.e. we must have a (computable) bijection between strings and programs. Of course, some of those strings were already programs, but many were not. I'm worried that what will be output will be only the program's corresponding string and that then the "quine" gotten by following the recursion theorem's proof will only output its corresponding string. – Quinn Culver Nov 1 '12 at 21:24
The construction still works if only some strings are valid programs. In that situation the simulator can do whatever it wants with an invalid program. Regardless of what it does, the output of $h$ will always be a syntactically valid program (regardless whether the input $x$ is valid), and $e$ will still be a syntactically valid program, which will be a quine. – Carl Mummert Nov 1 '12 at 21:32
When you say, "then the program $e$ will compute the same function as the program $F(e)$, as the proof shows.", I think you mean "then the program $h(e)$ will compute the same function as the program $F(h(e))$, as the proof shows." – Quinn Culver Nov 1 '12 at 22:31
I'm now convinced. I think what I didn't realize is that $F$, in the proof, doesn't have to be an arbitrary function from strings to strings, but can merely be one that only takes programs and always outputs programs, as the special case in your point 5. can be taken to be. – Quinn Culver Nov 1 '12 at 23:37
The usual literature doesn't emphasize that it would be possible to have a numbering where not every index is actually a valid program. This is because, in any reasonable programming language, the set of syntactically valid programs is decidable (in fact primitive recursive), and so we could just declare by fiat that any program that is syntactically incorrect will now compute some fixed function, at which point every string is now a "valid" program in the new sense. But even if the set of indices that are valid programs is not decidable, most results go through anyway. – Carl Mummert Nov 2 '12 at 0:20

The variant of the recursion theorem you have seen is formulated in terms of indices because it assumes a "programming language" where indices of Turing machines are what program texts look like. We define that a "program" in this language consists of an index in some well-defined enumeration of Turing machine, so if we find a machine that outputs its own index, that index is a quine from the perspective of this programming language.

However, the theorem generalizes to any reasonably behaved notion of programming language, as long as we fix a way to encode a program text as something that can be (part of) the input and output of a running program. Here's how the theorem is stated in Jones, Computability and Complexity from a Programming Perspective:

Theorem 14.2.1 (Kleene's second recursion theorem.) For any $\tt L$-program $\tt p$, there is an $\tt L$-program $\tt q$ satisfying, for all inputs ${\tt d}\in{\tt L}\text{-}\mathit{data}$: $$\tt [\!\![q]\!\!](d) = [\!\![p]\!\!](q,d)$$ Typically $\tt p$'s first input is a program, which $\tt p$ may apply to various arguments, transform, time, or otherwise process as its sees fit. The theorem in effect says that $\tt p$ may regard $\tt q$ as its own text, thus allowing self-referential programs.

(Here $\tt[\!\![{\cdot}]\!\!]$ is the function that takes a program text to its meaning as a partial function, and the equals sign means that either the two sides are defined with the same value, or both sides diverge).

In particular if $\tt p$ is a program that outputs its first argument, $\tt q$ will be a quine.

This more general statement can be proved using basically the same techniques as the one for Turing machine enumerations that one finds in mathematicians' textbooks.

-
I don't fully understand your answer, since I don't know exactly how the coding works in Jones' book (though I intend to understand). But are you saying that one could indeed write a program (in, say, C) that outputs its own code simply by following the proof of the recursion theorem? – Quinn Culver Oct 23 '12 at 21:46
@QuinnCulver: The point is that it works with any coding you'll care to specify, as long as program executions and certain other, very simple, program manipulations are computable with the coding you select. The general technique can certainly be used to produce a C quine, though it would be a very complex one, incorporating one or several layers of C self-interpreters to do the job. – Henning Makholm Oct 24 '12 at 12:24
Okay. Does your current answer make that point clear? I.e. is it clear from your answer that if I wanted to write my own bona fide quine (I use 'bona fide' to distinguish between programs that output their own index and ones that output their actual source code) in, say, the language C, I could follow the proof of the recursion theorem to write one? – Quinn Culver Oct 25 '12 at 13:19
@QuinnCulver: It does not make sense to "distinguish between programs that output their own index and ones that output their actual source code" -- in the "programming language" we're considering here the index IS THE SOURCE CODE. To answer your question: The general technique can certainly be used to produce a C quine, though it would be a very complex one, incorporating one or several layers of C self-interpreters to do the job. – Henning Makholm Oct 25 '12 at 13:30
Indeed "index" is just a jargon term for "program", which we use because we want to emphasize that the results we prove work for any acceptable indexing, not just for some specific programming language. – Carl Mummert Oct 29 '12 at 0:38

Regarding your doubts about source code being the same as the index (or not), you can think of it this way:

The source code of a program is some string of characters.
Those characters are encoded in some way with numbers, let's say ASCII codes.
Now you can think of each character as a digit in a base-$256$ number system.
So you start with the first character and take its ASCII value, then add to it the second character's ASCII value multiplied by $256$ (the first power of $256$), then add the third character's ASCII value multiplied by $256^2$ (second power of $256$), and so on, up to the last character.
This way you will get a very huge natural number, which uniquely represents this particular program (its source code). So this number is the index of that program.

Sure, there would be indices which does not represent any valid program (since not all possible outputs are programs, just a subset of them are). But it doesn't matter. The only important thing is that every program has its own unique index.

Here's an example program in my own toy language:

say "Hi!";

and here's its index:

279 249 219 322 602 409 517 427

and how I calculated it:

$'s'\cdot256^0 \;+\; 'a'\cdot256^1 \;+\; 'y'\cdot256^2 \;+\; '\ '\cdot256^3 \;+\; '"'\cdot256^4 \;+\; 'H'\cdot256^5 \;+\; 'i'\cdot256^6 \;+\;\\ '!'\cdot256^7 \;+\; '"'\cdot256^8 \;+\; ';'\cdot256^9 \\=\\ 115\cdot256^0 \;+\; 97\cdot256^1 \;+\; 121\cdot256^2 \;+\; 32\cdot256^3 \;+\; 34\cdot256^4 \;+\; 72\cdot256^5 \;+\; 105\cdot256^6 \;+\;\\ 33\cdot256^7 \;+\; 34\cdot256^8 \;+\; 59\cdot256^9 \\=\\ 115\cdot1 \;+\; 97\cdot256 \;+\; 121\cdot65\,536 \;+\; 32\cdot16\,777\,216 \;+\; 34\cdot4\,294\,967\,296 \;+\;\\ 72\cdot1\,099\,511\,627\,776 \;+\; 105\cdot281\,474\,976\,710\,656 \;+\; 33\cdot72\,057\,594\,037\,927\,936 \;+\;\\ 34\cdot18\,446\,744\,073\,709\,551\,616 \;+\; 59\cdot4\,722\,366\,482\,869\,645\,213\,696 \\=\\ 115 \;+\; 24\,832 \;+\; 7\,929\,856 \;+\; 536\,870\,912 \;+\; 146\,028\,888\,064 \;+\; 79\,164\,837\,199\,872 \;+\; 29\,554\,872\,554\,618\,880 \;+\; 2\,377\,900\,603\,251\,621\,888 \;+\; 627\,189\,298\,506\,124\,754\,944 \;+\; 278\,619\,622\,489\,309\,067\,608\,064 \\=\\ 279\,249\,219\,322\,602\,409\,517\,427$

Therefore, when a quine prints its own source code, it can be thought of as outputting a single natural number, which is exactly the same as the number which represents its source code (its index).

-
I understand how Gödel numbers work. My problem was that I wanted a program that output not it's index, but it's actual, human-readable, code (which can be gotten from the index). – Quinn Culver Jun 9 '15 at 11:15
This is just a matter of interpreting the output of the program. After all, it's just a stream of bits, which can be interpreted as bytes (base-256 digits of that number), and then those bytes as characters. But it is not the problem of the program how do we interpret these bytes. It's the choice of the operating system, execution environment and the user. You can set up your execution environment to display stream of bits instead of textual output, but it doesn't affect the program and how it works. We, users, see characters. Computers see only streams of bits. – SasQ Jun 9 '15 at 18:16
My point is that if I wanted, say, to impress someone by writing a Quine, but all they saw was a program that output it's own Gödel number, the person probably wouldn't be too impressed. See what I mean? – Quinn Culver Jun 10 '15 at 14:14