Recently, I stumbled upon my copy of Michael Sipser’s “Introduction to the Theory of Computation.” I eagerly browsed through the first 6 chapters and the Turing Machine (TM) SELF described in Chapter 6 (Lemma 6.1) caught my eye.
Basically, SELF TM is defined as :
TM SELF = A Turning Machine which when run computes and outputs its own description
So the TM SELF is roughly equivalent to a program written in a high-level language that, when run, outputs its source code by computing it. The crucial requirement is that the program compute its description (i.e., the source code) from transient memory (e.g., RAM) and should not resort to reading the code from a persistent store (i.e., opening up its own source code file or some source code database and printing it would be cheating).
I spent a few hours doing a literal translation of the idea in the book to implement a Java program that prints its own source code.
We use angle brackes “< >” around a TM to denote its description.
For example, <SELF> represents the description of the Turning Machine SELF. Or equivalently, <SELF> denotes the string representation of the source code in Turning Machine SELF.
From here on, we will just follow the idea in the book which divides SELF into two modules A and B. In programming terms, it means SELF contains 2 methods : method A followed by method B. Therefore the description (source code) of SELF is nothing but a juxtaposition of the description (code) of A followed by description (code) of B.
Therefore, <SELF> = <A><B>
When SELF is run :
1) the control starts with A which prints <B>. This is because we arranged that a copy of <B> is literally embedded in <A> as a string.
2) After A outputs the string <B>, A calls the method B(). In TM terminology, this is equivalent to passing the control to module B.
3) B computes <A> from the output left on the tape after A has finished execution.
This is to say that the code in method B() will read the contents of the “tape” (as you will see, in the code below, the “tape” is nothing but a StringBuffer) and somehow from that B will figure out what A’s code (i.e., <A>) looks like.
4) This part is crucial so it’s worth repeating : when method A finished its run, we have <B> on the tape. So this is the ‘input’ B will work on when A passes the control to it.
5) After B gets the input of <B>, all it does is compute the code that A uses to print a string (the string being <B>). Effectively, computing <A>.
6) Once it computes <A>, B just “prepends” <A> to what is already there on the tape (remember that the “tape” / StringBuffer still has <B> from when A finished running)
Module/Method –> Tape contents after execution of this module
A –> <B>
After A outputs <B> to the tape, it calls module B and the control goes to B. B computes A’s description by adding some additional “code” around the existing tape contents i.e., <B>. In TM speak, we can say that B applies a computable function “q” to its input and computes <A>. That is : q(<B>) = <A>. Then B prepends its output <A> to the tape contents.
Module/Method –> Tape contents after execution of this module
B –> q(<B>) <B> = <A><B> = <SELF>
So that means, when module B finishes, the whole program finishes (because calling method B is the last statement in method A) and the tape contains the code for both methods A and B which is nothing but the entire program <SELF>.
That is to say : the program prints itself.
====
Here’s the program cut-n-pasted below. Note that it’s a literal translation of the above idea without any regard for program length.
You can copy the whole code into a file called Self.java and compile and run it. The output from running Self.java should be exactly identical to the source code in Self.java.
A few technicalities :
Of course, you would not exactly write code on a mathematical TM or for that matter directly in machine code. What we do is write it on a computer in some high-level programming language like Java. This itself engenders a few differences between the theory of computation and the practice of programming. For example, in Java, you cannot just have methods A and B, you have to have a Class that encompasses these methods. Also, if you want to run Self.java (the code below) from the command line, you need to have a Main() method. Which is why in our implementation below, the module A is the method Main and not some method “A”. Module B is method B which gets the contents of the tape (i.e., StringBuffer) as its input when A calls it.
In the end, we output the contents of the tape to the standard output.
Also, I resorted to a hack to avoid using ‘escaped double-quotes’ instead choosing
char[] s = {'f', 'o', 'o'}
instead of
String s = "foo"
Actually, I wrote a quick program that does this kind of code translation from the String s to the char[] s syntax.
The actual program is only 2 “lines” long!
Essentially, the first line is <A>. The second line is <B>. I have mentioned in Step (1) that we will embed a copy of <B> in <A>. In fact, in the following code, if you search for the second line in the first line, you will find an exact copy of the second line in the first.
When you run Self.java , it outputs its own code.
=====Copy the code to a file Self.java and run it=====
public class Self { public static void main(String args[]) { StringBuffer sb = new StringBuffer();sb.append("private static void B(StringBuffer sb) {StringBuffer sb2 = new StringBuffer(sb); char[] arrChars = {'p','u','b','l','i','c',' ','c','l','a','s','s',' ','S','e','l','f',' ','{',' ','p','u','b','l','i','c',' ','s','t','a','t','i','c',' ','v','o','i','d',' ','m','a','i','n','(','S','t','r','i','n','g',' ','a','r','g','s','[',']',')',' ','{',' ','S','t','r','i','n','g','B','u','f','f','e','r',' ','s','b',' ','=',' ','n','e','w',' ','S','t','r','i','n','g','B','u','f','f','e','r','(',')',';','s','b','.','a','p','p','e','n','d','(',34,}; String str2 = new String(arrChars); sb2.insert(0, str2); char[] arrChars2 = {34,')',';',}; str2 = new String(arrChars2); sb2.append(str2); char[] arrChars3 = {' ','B','(','s','b',')',';','}',}; str2 = new String(arrChars3); sb2.append(str2); System.out.println(sb2.toString());System.out.println(sb.toString());}}"); B(sb);}
private static void B(StringBuffer sb) {StringBuffer sb2 = new StringBuffer(sb); char[] arrChars = {'p','u','b','l','i','c',' ','c','l','a','s','s',' ','S','e','l','f',' ','{',' ','p','u','b','l','i','c',' ','s','t','a','t','i','c',' ','v','o','i','d',' ','m','a','i','n','(','S','t','r','i','n','g',' ','a','r','g','s','[',']',')',' ','{',' ','S','t','r','i','n','g','B','u','f','f','e','r',' ','s','b',' ','=',' ','n','e','w',' ','S','t','r','i','n','g','B','u','f','f','e','r','(',')',';','s','b','.','a','p','p','e','n','d','(',34,}; String str2 = new String(arrChars); sb2.insert(0, str2); char[] arrChars2 = {34,')',';',}; str2 = new String(arrChars2); sb2.append(str2); char[] arrChars3 = {' ','B','(','s','b',')',';','}',}; str2 = new String(arrChars3); sb2.append(str2); System.out.println(sb2.toString());System.out.println(sb.toString());}}
public class Self { public static void main(String args[]) { StringBuffer sb = new StringBuffer();sb.append("private static void B(StringBuffer sb) {StringBuffer sb2 = new StringBuffer(sb); char[] arrChars = {'p','u','b','l','i','c',' ','c','l','a','s','s',' ','S','e','l','f',' ','{',' ','p','u','b','l','i','c',' ','s','t','a','t','i','c',' ','v','o','i','d',' ','m','a','i','n','(','S','t','r','i','n','g',' ','a','r','g','s','[',']',')',' ','{',' ','S','t','r','i','n','g','B','u','f','f','e','r',' ','s','b',' ','=',' ','n','e','w',' ','S','t','r','i','n','g','B','u','f','f','e','r','(',')',';','s','b','.','a','p','p','e','n','d','(',34,}; String str2 = new String(arrChars); sb2.insert(0, str2); char[] arrChars2 = {34,')',';',}; str2 = new String(arrChars2); sb2.append(str2); char[] arrChars3 = {' ','B','(','s','b',')',';','}',}; str2 = new String(arrChars3); sb2.append(str2); System.out.println(sb2.toString());System.out.println(sb.toString());}}"); B(sb);}
private static void B(StringBuffer sb) {StringBuffer sb2 = new StringBuffer(sb); char[] arrChars = {'p','u','b','l','i','c',' ','c','l','a','s','s',' ','S','e','l','f',' ','{',' ','p','u','b','l','i','c',' ','s','t','a','t','i','c',' ','v','o','i','d',' ','m','a','i','n','(','S','t','r','i','n','g',' ','a','r','g','s','[',']',')',' ','{',' ','S','t','r','i','n','g','B','u','f','f','e','r',' ','s','b',' ','=',' ','n','e','w',' ','S','t','r','i','n','g','B','u','f','f','e','r','(',')',';','s','b','.','a','p','p','e','n','d','(',34,}; String str2 = new String(arrChars); sb2.insert(0, str2); char[] arrChars2 = {34,')',';',}; str2 = new String(arrChars2); sb2.append(str2); char[] arrChars3 = {' ','B','(','s','b',')',';','}',}; str2 = new String(arrChars3); sb2.append(str2); System.out.println(sb2.toString());System.out.println(sb.toString());}}
============
Now if you are at this point, be nice and run the ‘hello world’ program first.