User:IssaRice/Computability and logic/Sipser's quine in Python

Michael Sipser's Introduction to the Theory of Computation describes a quine using Turing machines.

Here is an implementation of the machine SELF.

TAPE = ""

def Q():
    global TAPE
    TAPE = 'TAPE = "' + TAPE.replace("\n", "\\n") + '"\n'

# A
TAPE = "M = TAPE\nQ()\nTAPE += M"

# B
M = TAPE
Q()
TAPE += M

The output is:

>>> import quine
>>> print(quine.TAPE)
TAPE = "M = TAPE\nQ()\nTAPE += M"
M = TAPE
Q()
TAPE += M

This implementation is complicated by several aspects of the Python programming language:

• Python distinguishes between printing and returning, whereas Sipser's model of Turing machines just has an output tape. Thus, in Sipser's quine, part A can just run and leave things on the tape for part B to use, whereas this sort of thing isn't automatic in Python (if we used separate methods for A and B, then we would have to pass the output of A to B, by e.g. calling B(A())). To emulate this behavior, we use a global variable TAPE where each part reads from and writes to.
• Python has local and global variables, so in the method Q we must explicitly declare global TAPE.

The above is not exactly a quine because the definition of Q was not printed. This isn't too hard to fix but is somewhat annoying.