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

IssaRice at 00:59, 25 June 2019

2019-06-25T00:59:11Z

← Older revision		Revision as of 00:59, 25 June 2019
Line 30:		Line 30:
	* 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 <code>A</code> and <code>B</code>, then we would have to pass the output of <code>A</code> to <code>B</code>, by e.g. calling <code>B(A())</code>). To emulate this behavior, we use a global variable <code>TAPE</code> where each part reads from and writes to.		* 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 <code>A</code> and <code>B</code>, then we would have to pass the output of <code>A</code> to <code>B</code>, by e.g. calling <code>B(A())</code>). To emulate this behavior, we use a global variable <code>TAPE</code> where each part reads from and writes to.
	* Python has local and global variables, so in the method <code>Q</code> we must explicitly declare <code>global TAPE</code>.		* Python has local and global variables, so in the method <code>Q</code> we must explicitly declare <code>global TAPE</code>.

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

IssaRice: Created page with "Michael Sipser's ''Introduction to the Theory of Computation'' describes a quine using Turing machines. Here is an implementation of the machine ''SELF''.

TAPE = ""  de..."

2019-06-19T00:09:19Z

Created page with "Michael Sipser's ''Introduction to the Theory of Computation'' describes a quine using Turing machines. Here is an implementation of the machine ''SELF''. <pre>TAPE = "" de..."

New page

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

Here is an implementation of the machine ''SELF''.

<pre>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</pre>

The output is:

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

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 <code>A</code> and <code>B</code>, then we would have to pass the output of <code>A</code> to <code>B</code>, by e.g. calling <code>B(A())</code>). To emulate this behavior, we use a global variable <code>TAPE</code> where each part reads from and writes to.
* Python has local and global variables, so in the method <code>Q</code> we must explicitly declare <code>global TAPE</code>.