[Overview] [Previous] [Next]

Program Self-Application

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

Such a program can sometimes be applied to itself.

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).

Copyright 1996 by David Matuszek
Last modified Apr 14, 1996