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?
Solution 1:
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:
-
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.
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$.
- Let $e_0$ be a specific program (source code) that implements $F \circ h$. Let $e = h(e_0)$.
- Then the program $e$ will compute the same function as the program $F(e)$, as the proof shows.
-
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.
Solution 2:
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.
Solution 3:
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).