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

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

  1. Read as the description of TM
  2. Run on and get
  3. Print and

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

  1. Reads string as input
  2. Run on and get
  3. 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.

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