Transition Rules and Execution
What You'll Learn
You'll understand how transition rules guide a Turing Machine step-by-step through computation by specifying exactly what to do at each moment.
How Transition Rules Work
Think of a Turing Machine as following a recipe where each step depends on what you're currently doing and what ingredient you see. A transition rule is like one line in that recipe: "If you're in state A and see symbol X, then write symbol Y, move your position (left or right or stay), and switch to state B."
Each transition rule answers three questions:
- What symbol should I write? (Possibly the same symbol, effectively leaving it unchanged)
- Where should the head move? (Left
L, RightR, or StayS) - What state should I enter next?
Execution Step-by-Step
When a Turing Machine executes:
- It examines its current state and the symbol under the tape head
- It looks up the matching transition rule
- It writes the new symbol to the tape (overwriting the old one)
- It moves the head according to the rule's direction
- It transitions to the specified next state
- Repeat until reaching a halting state (or running forever)
This process is deterministic—given a configuration, the next step is completely determined by the transition function.
Example Walkthrough
Suppose you're in state q₁ reading symbol 0:
- Rule:
δ(q₁, 0) = (q₂, 1, R) - Action: Write
1, move Right, enter stateq₂
The machine methodically follows these rules, transforming the tape one symbol at a time.
Key Takeaway: Transition rules are the "brain" of a Turing Machine—they precisely define how the machine updates the tape, repositions its head, and changes state during each computational step.