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