[Overview] [Previous] [Next]

Program Self-Application

In computer science, we often write programs that process other programs.

• A compiler reads a program in one language and produces the equivalent program in another language.
• A preprocessor reads a program with embedded processor commands and produces an equivalent program without those commands.
• A prettyprinter reads a program and writes a "cleaned up" version of the same program.

Such a program can sometimes be applied to itself.

• A prettyprinter, written in and for the same language, can prettyprint itself.
• A compiler can be written in language X for a new, improved version of language X. This process is called bootstrapping.

The input to a Turing machine is a string. Turing machines themselves can be written as strings, and these strings can be used as input to other Turing machines.

In particular, we have already discussed the notion of a universal Turing machine whose input consists of a description M of some arbitrary Turing machine, and some input w to which machine M is to be applied (we will write this combined input as M+w), and produces the same output that would be produced by M. We could write this as UTM(M+w)=M(w).

Since a Turing machine can be represented as a string, it is entirely possible to supply a Turing machine as input to itself, e.g. UTM(UTM).