What's a Turing Machine?

A Turing Machine is a theoretical computer consisting of a tape of infinite length and a read-write head which can move left and right across the tape. When started, a Turing machine executes a series of discrete transitions, as determined by its transition table and by the initial characters on the tape. For each transition, the machine checks what state it is in and what character is written on the tape below the head. Based on those, it then changes to a new state, writes a new character on the tape, and moves the head one space left or right. The machine stops after transferring to the special HALT state. So, a transition table for a 2-state TM might look like this:

	State 1	State 2
"x"	2, y, right	1, y, left
"y"	2, x, left	halt, x, right

So, for instance, if the machine was in state 1 and an "x" was the current character, it would write a "y", move right, and enter state 2. If it were in state 2 looking at a "y", it would write an "x", move right, and halt. Technically, a valid TM should have an action defined for every state/character pair that might occur. The simulator applet implicitly halts if it finds no transition that applies to its current situation.

However odd it may sound for so simple a machine, the Turing Machine is the most powerful computing model known to computer scientists. In this context, "powerful" refers only to what it is capable of doing, not to how fast or efficiently it does it. It has been proven that a TM is capable of performing any computation that a modern computer can, given enough time. Infact, it is technically MORE powerful than modern computers, since it has no storage limitations.

Classically, a Turing Machine is thought of as having its tape bounded on the left but extending infinitely to the right, though its power is not expanded by making it unbounded on both ends. The simulator, of course, is bounded on both ends, which is really the only detail that makes it a simulator and not the real thing. In addition, the classical TM has 4-tuple transitions: (state, character) --> (new state, new character OR direction), meaning that it cannot both write a character and move the head in the same transition. The 5-tuple transitions used in the applet make things a bit simpler and do not actually change the power of the machine, but a 4-tuple machine can be simulated if desired (see How to Program).

Top
Next: Using the Interface
Back to the applet