Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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
1  
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
2  
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

2 Answers 2

up vote 4 down vote accepted

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.

share|improve this answer
    
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
1  
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.

share|improve this answer
    
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
1  
@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
1  
@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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.