What is a Turing Machine?
A Turing Machine is a mathematical model of computation that defines an abstract machine capable of implementing any computer algorithm. Invented by Alan Turing in 1936, it is widely considered the foundation of modern computer science.
Key Components
- The Tape: An infinite strip of memory divided into discrete cells. Each cell contains a symbol from a finite alphabet or is blank.
- The Head: A generic read/write pointer that can move left (L) or right (R) one cell at a time.
- State Register: Stores the current internal state of the Turing machine, starting in an initial configuration.
- Transition Function: The rules that tell the machine what to do next based on its current state and the symbol the head is reading.
How it Works
In each step, the machine:
- Reads the symbol on the tape under the head.
- Looks up the Transition Rule for the current state and symbol.
- Writes a new symbol to the cell.
- Moves the head one cell to the left (L) or right (R).
- Changes to the new internal state.
Example: Replacing 0s with 1s
If the machine is in state q0 and reads a 0, it writes a 1, moves R (right), and stays in state q0.
It continues this until it reads a blank symbol (_), where it moves L and changes to a halting state.
Transition Diagram
100%
Legend:
Start
Intermediate
Accept/Halt
Active State
Labels:
[read/write, dir]
Tape Visualization
Ready
Machine Configuration
| State | Read | Write | Move | Next |
|---|
Execution Log
Initialize and run to view execution steps.