A Universal Turing Machine Can Emulate Itself
Since any specific Turing machine can be emulated by a Universal Turing machine, it follows that a UTM could emulate itself. Again, it would be simplest to add another program tape for the emulated UTM, and an extra data tape as well.
M.C. Escher’s famous sketch, “Drawing Hands”, of a pair of hands drawing each other visually evokes the complexity of a Turing machine emulating itself.
The infinity of reflections in paired mirrors is another illustration.
The Importance of the Universal Turing Machine
Alan Turing’s goal in defining his Turing machines, including non-deterministic Turing machines, was to set out a formal mathematical methodology for recognizing or creating patterns, or messages. This capability was an alternative to other means of developing mathematical proofs.
The capability of the Universal Turing machine to emulate any other TM strongly indicated that several types of mathematical processes might be capable of solving the same classes of problems.
Perhaps the most important example of such a capability is the Universal Turing Machine’s role in resolving the Halting Problem and David Hilbert’s “Decision Problem.”
Reference:
Barker-Plummer, D. Turing Machines. (2011). The Stanford Encyclopedia of Philosophy. Edward N. Zalta (ed.). Accessed March 29, 2012.
Click to Return to Page One: Universal Turing Machines
Decoding Science. One article at a time.