[Overview] [Previous] [Next]
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
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
M. We could write this as
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.
Copyright © 1996 by David Matuszek
Last modified Apr 14, 1996