7-tuple Definition
The standard Turing machine model is defined by the following 7-tuple:
$$M = \langle Q, \Sigma, \Gamma, \delta, q_0, B, F \rangle$$
\(Q\): Finite set of states
如 \(Q = \{q_0, q_1, q_2, \text{halt}\}\)
\(\Sigma\): Input alphabet
本实验 \(\Sigma = \{1, +, \times\}\)
\(\Gamma\): Tape alphabet
\(\Gamma = \{1, +, \times, B, X, Y,
\dots\}\)
\(\delta\): Transition function
\(\delta: Q \times \Gamma \to Q \times \Gamma
\times \{L, R\}\)
\(q_0\): Initial state
通常为 \(q_0 \in Q\)
\(B\): Blank symbol
Represents empty cell on tape
\(F\): Set of final states
\(F \subseteq Q\),通常包含 \(\text{halt}\)
状态
Transition Function
\(\delta(q, a) = (q', b, D)\)
→
Current State \(q \in Q\)
Current state of the machine
●
Read Symbol \(a \in \Gamma\)
Character at current head position
✎
Write Symbol \(b \in \Gamma\)
Overwrite character in current cell
←/→
Move Direction \(D \in \{L, R\}\)
L for left, R for right
✓
Next State \(q' \in Q\)
New state after transition
"The machine determines the next action based on current state and tape symbol"
Binary Turing Machine Definition
Based on the standard 7-tuple, adapted for binary arithmetic operations:
$$M = \langle \{q_0, \dots\}, \{0, 1\}, \{0, 1, +, B, x, y\}, \delta, q_0, B, F
\rangle$$
\(\Sigma = \{0, 1\}\)
Input accepts only binary digits (0 and 1)
Auxiliary symbols \(\{x, y\}\)
Used to mark processed bits (x=0, y=1)
💡 Operation Principle (Ripple Carry): The machine alternately reads the least significant bits from two numbers (right end). After reading a bit from the right number, it erases it, carries the value leftward, adds it to the corresponding position on the left, handles carry, and returns.
Current State Panel
Current State
IDLE
Step
0
Read
-
BIN
ACTION LOG >
Waiting for instructions...
Current Arithmetic Rule Set
\(q_0 \xrightarrow{0/1} R, \quad q_{add} \xrightarrow{Carry} L, \quad q_{return}
\xrightarrow{Find \ Y} R\)