# A Program Printing Itself

Is it possible to find a program that prints itself?

This is a common thought that would occur to everyone when we begin to learn programming. You can find lots of sample code written in C or some language else on Google. But here we will not confine this problem to a certain programming language and discuss how the existence of this program is ensured.

## Turing machine

First, it is necessary to formalize programs with a general computational model. Consider a machine with following features.

- It consists of a tape of infinite length, a two-way read-write head and a state register
- An alphabet of symbols, a finite set of states and a set of state transition rules are predefined
- It halts when the state in the register is either accepting or rejecting

This is a basic deterministic single-tape Turing machine, the most widely used computational model ever. It is equivalent to many variants and other computational models such as

- multi-tape Turing machine
- nondeterministic Turing machine
^{1} - two-stack PDA
- lambda calculus

Now the problem is abstracted as finding a TM that prints the description of itself.

## Recursion theorem^{2}

We use \(\langle T \rangle\) to denote the description of a TM \(T\). Suppose there is a single-tape TM \(P_w\) that reads any input and output the string \(w\). \(\langle P_w \rangle\) denotes the description above. And then define another TM \(Q\):

- Read string \(w\) as input
- Print \(\langle P_w \rangle\) on the tape

Obviously \(Q\) is a legitimate TM. After introducing the TMs above, come back to the problem and consider whether there exists a TM \(R\) that prints the description of itself on the tape.

Construct a TM \(S\).

- Read \(\langle T \rangle\) as the description of TM \(T\)
- Run \(Q\) on \(\langle T \rangle\) and get \(P_{\langle T \rangle}\)
- Print \(P_{\langle T \rangle}\) and \(\langle T \rangle\)

Finally, it is able to construct the TM \(R\) that we need.

- Reads string \(w\) as input
- Run \(Q\) on \(\langle S \rangle\) and get \(\langle P_{\langle S \rangle} \rangle\)
- Print \(\langle P_{\langle S \rangle} \rangle\) and \(\langle S \rangle\)

Here \(\langle R \rangle = \langle P_{\langle S \rangle}S \rangle\).

In fact it is a conclusion derived from the famous recursion theorem. It ensures that self-reference is allowed in a TM. Therefore it is possible to construct a TM or program that prints itself.