Turing Machine

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

Current State: q0

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