Can one Turing machine emulate another? Are Turing machines guaranteed to finish a task? As Tolkien said about the advice that elves provide, the answer is “both yes and no.”
Essentially, the Universal Turing machine represents the ability for a “computer” to manipulate a program just as it deals with data.
Review of a Standard Turing Machine
A standard Turing machine, or ‘TM’, is able to solve a great variety of problems in mathematics, pattern recognition, and pattern creation, although it is only a theoretical construct rather than a physical computer.
The Turing machine’s program consists of a set of states. Such a program can process any number of different patterns on its input tape, with the option to accept or reject the input or to update cells on the tape.
Variations on Turing machines include having more than one tape and a read/write head for each tape. This may make it easier to describe a program, but does not add any greater “power” to the class of problems it can solve. One tape can always be segregated by special symbols, and any length of symbol can be shifted onto blank areas of the tape. Using multiple tapes allows the program to omit these tedious steps.
Introducing the Universal Turing Machine
A “Universal Turing Machine,” or ‘UTM,’ can emulate any other specific Turing machine, by defining states and symbols. The UTM is defined with certain capabilities.
- The UTM can define the symbols that the specific Turing machine will use.
- It can define the symbols that encode the states and transition rules for the specific Turing machine.
- It can encode the rules for that specific Turing machine onto the input tape.
A single-tape UTM needs to define a marker to mark the end of the “specific” program and the start of the specific machine’s initial tape. It must also shuffle the read/write head between the specific TM’s program and its data. As noted, it is simpler to describe a UTM with multiple tapes.
The Universal Turing Machine is remarkably similar to the Von Neumann model of a computer, where both programs and data can be stored on the same medium. Any modern computer capable of copying a program file from one medium to another, and later running that program, follows this architecture.
Decoding Science. One article at a time.