Formal Description of Turing’s Machine
A more formal description of a Turing machine says that it has a finite, or limited, set of states and a finite set of symbols, including the current status and a transition function. The current status includes the “state,” or the ordered set of symbols (as written in cells on the “tape”), and the index number of which cell is in use, which is the only cell whose value may change in one transition.
This formal Turing machine is simply an abstraction, rather than a change in the capabilities of the machine.
Differences Among Turing Machines
Starting with the classic definitions, there are many varieties of Turing machine, including the following possible differences between models:
- Alan Turing’s classic definition specified that the tape could only hold the symbols zero and one; most current definitions allow any finite number of symbols.
- The classic definition allowed the machine to rewrite the current cell, and also move by one position in one operation; both actions were specified as a single “instruction” or transition. The formal definition separates these capabilities.
- One Turing Model might start at the left-most cell on the tape; another type may start at an specific cell in a tape that extends for an infinite distance in both directions.
- A Turing machine with the fewest features might be preferred to demonstrate a fundamental principle, for example using only two symbols. Another TM with more symbols might need fewer instructions, or take fewer steps, to perform the same task.
When it has been demonstrated that two Turing machines with different formulations can nonetheless perform the same task, they are “equivalent.” Such changes may make the “programming” simpler without changing the basic power of the machine: the class of problems it can solve.
Decoding Science. One article at a time.