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

States and Transition Functions

Learn how a finite set of states and a transition function determine the machine's behavior based on current state and symbol.

States and Transition Functions

You'll learn: How a Turing Machine's finite set of states and transition function work together to control its behavior based on what it's currently doing and what it sees on the tape.

The Control Unit's Brain

Think of a Turing Machine's states like the "moods" or "modes" of operation. The machine is always in exactly one state at any moment—maybe it's in a "searching" state, a "writing" state, or a special "accept" or "reject" state. Though the tape can be infinite, the machine itself has only a finite set of states, like a fixed control panel with a limited number of buttons.

The transition function is the rulebook that determines what happens next. It takes two inputs:

  1. The current state the machine is in
  2. The symbol currently under the read/write head on the tape

Based on these two pieces of information, the transition function outputs:

  1. A new state to enter
  2. A symbol to write on the tape (possibly the same one)
  3. A direction to move the head (left or right)

How It Works in Practice

Imagine you're in state q1 and reading symbol 0. The transition function might say: "Write 1, move right, and enter state q2." Now you're in q2 reading whatever symbol is there, and the function dictates your next move. This continues step by step until you reach an accepting or rejecting state (or loop forever).

The transition function is deterministic—given a state and symbol, there's at most one valid action. If no transition is defined for a particular (state, symbol) combination, the machine halts.

Key Takeaway: The finite set of states and the transition function form the "program" of a Turing Machine, dictating every action based on current state and tape symbol—it's a precise, mechanical decision-making process.