[Math] Does the recursion theorem give quines

computabilitycomputer science

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?

Best Answer

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.

Related Question