|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).
Next: Using the Interface
Back to the applet
Site Updated: 2023/Oct/6
Copyright © 2023, All Rights Reserved. Check the credits before you borrow any of the graphics on these pages.