A theoretical computational model proposed by Alan Turing that defines the concept of "computability" and forms the theoretical foundation of modern computer science.
Standard Introduction
Turing Machine is an abstract computational model proposed by British mathematician Alan Turing in 1936. It consists of an infinitely long tape, a read/write head, and a state register.
Core Components:
- Tape: Infinitely long, divided into cells, each can hold a symbol
- Head: Can read, write, move left, move right
- State: Current internal state of the machine
- Transition Rules: Determine next action based on current state and symbol read
Simplified Explanation
Imagine a person working on an infinitely long tape with a pen and eraser. Following a rulebook, based on the symbol they see and their current "mood" (state), they decide what to write, where to move, and what their next "mood" will be. That's a Turing Machine!
Interactive Turing Machine Simulator
Example: Binary increment operation
Transition Table:
| Current State | Read Symbol | Write Symbol | Move | Next State |
|---|---|---|---|---|
| q0 | 0 | 0 | R | q0 |
| q0 | 1 | 1 | 右 | q0 |
| q0 | _ | _ | L | q1 |
| q1 | 0 | 1 | N | HALT |
| q1 | 1 | 0 | 左 | q1 |
Theoretical Significance
Defines the concept of "computability" and proves that some problems are undecidable (halting problem)
Practical Impact
Theoretical foundation of modern computers; all programming languages are Turing-equivalent
Church-Turing Thesis
Any problem solvable by an algorithm can be solved by a Turing machine