# A program that prints 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 to denote the description of a TM . Suppose there is a single-tape TM that reads any input and output the string . denotes the description above. And then define another TM :

- Read string as input
- Print on the tape

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

Construct a TM .

- Read as the description of TM
- Run on and get
- Print and

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

- Reads string as input
- Run on and get
- Print and

Here .

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.