The Turing Machine animation (and EM animation) allow construction of diagrams for Turing Machines and Computation Machines (and Enumeration Machines, respectively); these can be saved via [Alt]-S and loaded from your My Turing Machines page. A TM accepting the set {anbncn : n ≥ 0} is shown below.
States and Transitions
The top state with an incoming arrow is the start state; additional states can be added by clicking, and transitions are formed by dragging from one state to another (or dragging to nothing, which creates a new state at the head of the transition), just as in the DFA/NFA/NPDA animations.
Selecting a state, it can be converted to a few special state types:
- [Alt]-A marks the state as a halt-and-accept state (each TM must have exactly one of these).
- [Alt]-R marks the state as a halt-and-reject state (each TM must have exactly one of these).
- [Space] sets the state as a regular TM state.
- Enumeration Machines only: [!] sets the state as an output state, marked with a pencil, which outputs the string to the right of the current position until the first empty spot Δ on the tape.
The TM’s here are deterministic, so at most one transition from each state for each symbol of the tape alphabet can be made; any undrawn transition implicitly goes to the halt-and-reject state, so rejecting transitions can be omitted in the diagram.
Selecting a transition, the steps it taken (read, then write, then move) are selected as follows (the symbol Δ for an empty spot on the tape is entered via [Alt]-[Shift]-D):
- Typing a symbol selects the symbol read from the current position on the tape triggering the transition.
- Pressing [↓] and then a symbol optionally selects the symbol to write at the current spot on the tape.
- Pressing [←] or [→] optionally selects the direction for the read/write head to move.
Running the TM
The TM, CM, or EM can be run by clicking the Check Machine button at the top-left; if it checks out (no, this does not check whether machines are total, because it can’t! 🙂). For a TM or CM, enter an input string at the top and click the Run button at the top right; for an EM, simply click the Run button. Press [Space] to step through the computation, and you’re off! Press [Esc] to enter a new input string, or the Edit Machine button to go back to editing again.