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.

1. It consists of a tape of infinite length, a two-way read-write head and a state register
2. An alphabet of symbols, a finite set of states and a set of state transition rules are predefined
3. 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 machine1
• two-stack PDA
• lambda calculus

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

## Recursion theorem2

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$:

1. Read string $w$ as input
2. 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$.

1. Read $\langle T \rangle$ as the description of TM $T$
2. Run $Q$ on $\langle T \rangle$ and get $P_{\langle T \rangle}$
3. Print $P_{\langle T \rangle}$ and $\langle T \rangle$

Finally, it is able to construct the TM $R$ that we need.

1. Reads string $w$ as input
2. Run $Q$ on $\langle S \rangle$ and get $\langle P_{\langle S \rangle} \rangle$
3. 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.

1. It differs from deterministic one by multiple possible states after a state transition.

2. https://www.edx.org/course/li-lun-ji-suan-ji-ke-xue-ji-chu-pekingx-04830260x-0