The Universal Turing Machine is a Turing Machine Emulator

By

Home / The Universal Turing Machine is a Turing Machine Emulator

Escher Drawing Hands is like Mutual Universal Turing Machines: Image photographed by rrenzoo

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

Leave a Comment