Chapter 3 · Turing Machines
Interactive lab

Lab: Run a Turing machine

Watch a Turing machine compute. The head reads the highlighted cell, writes a new symbol, and shuffles left or right according to its transition function.

Machine

Decides the classic non-regular language of equal numbers of 0s followed by 1s. It crosses off one 0 (→x) and one matching 1 (→y) on each pass.

stateq0· steps 0
0
0
1
1
Try this
Run the { 0ⁿ1ⁿ } decider on 000111 and step slowly: you can see it cross off a 0 (→x) and its matching 1 (→y) on each sweep across the tape.