Course contentsShow
← Computer Science
Lesson 1855 of 2,87242. Turing Machines and ComputabilityFree lesson

Transition Rules and Execution

Understand how transition rules specify the next state, symbol to write, and head direction (left, right, or stay).

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:

  1. What symbol should I write? (Possibly the same symbol, effectively leaving it unchanged)
  2. Where should the head move? (Left L, Right R, or Stay S)
  3. What state should I enter next?

Execution Step-by-Step

When a Turing Machine executes:

  1. It examines its current state and the symbol under the tape head
  2. It looks up the matching transition rule
  3. It writes the new symbol to the tape (overwriting the old one)
  4. It moves the head according to the rule's direction
  5. It transitions to the specified next state
  6. 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 state q₂

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.