Skip to content
Tutorials Center
My learning

Topics

Lesson 54 of 59 ยท Projects

Project: A Turing Machine Simulator

Build a Turing machine simulator that reads rules from plain text, prints step-by-step traces, decides palindromes and increments binary numbers, and searches for busy beavers.

A Turing machine is the simplest model of a general-purpose computer, but nobody wants to hand-trace one on paper for more than a few steps. In this project you will write a Turing machine simulator that reads a machine from a short text description, runs it, and prints a trace. Then you will use it to run three classic machines and even to search for the machines that run longest.

Writing a simulator is a fitting end to the theory chapters: the program you write is itself a small universal Turing machine, a machine that takes the description of another machine as input and imitates it. That idea underlies every interpreter, every virtual machine and the proofs of undecidability.

The text format

One rule per line, five fields, in the order current state, read symbol, new state, written symbol, move:

TEXT
q0 1 q0 1 R        # in q0, reading 1: stay in q0, write 1, move right
q0 _ q1 _ L        # _ is the blank symbol
q1 0 halt 1 S      # S means stay; "halt" is the accepting/stopping state

If no rule matches the current (state, symbol), the machine rejects (it stops in a non-halting state). When it enters the state named halt it accepts. The tape is a dictionary from position to symbol, so it is infinite in both directions at no cost.

flowchart LR
    TXT["Machine text<br/>(rules)"] --> PARSE["parse()<br/>dict (state, sym)"]
    IN["Input string"] --> TAPE["tape dict + head"]
    PARSE --> LOOP["step loop"]
    TAPE --> LOOP
    LOOP --> OUT["result, steps,<br/>trace, final tape"]

The simulator is a parser plus one loop.

Step 1: the simulator and a binary incrementer

Here is the whole simulator. run returns the final status, the number of steps, the tape contents and (optionally) a trace of every configuration. A configuration is the tape with the head marked as [state] before the symbol it reads, the way textbooks write them.

Our first machine adds 1 to a binary number written on the tape. It moves to the right end, then walks left turning 1s into 0s (the carry) until it finds a 0 or a blank, which becomes 1.

Python The simulator and a binary incrementer

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The trace shows the head sweeping right, then carrying leftwards: 1011 (11) becomes 1100 (12). Checking all numbers from 0 to 199 against Python's own arithmetic is the quickest way to trust the rules.

Step 2: a palindrome decider and its cost

Now a machine that decides a language rather than computing a function: palindromes over {a, b}. The strategy is to erase the first symbol, remember it in the state, run to the other end, check that the last symbol is the same, erase it, and repeat on what is left. Each round crosses the tape twice, so the running time is quadratic.

Python A palindrome decider, verified on every short string

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The step counts grow quadratically, matching the time complexity lesson. A second tape would let you do the same job in linear time: copy the input, then compare the copy backwards.

Step 3: busy beavers

Here is a fun use of a simulator. The busy beaver game asks: among all n-state, 2-symbol Turing machines that halt when started on a blank tape, which one runs the longest (or leaves the most 1s)? The answer function BB(n) is not computable. It is closely tied to the halting problem: if you could compute BB(n), you could decide whether any n-state machine halts by running it for BB(n) steps.

For tiny n we can still find the answer by brute force: enumerate every machine, run each one for a bounded number of steps and keep the champion. A machine with n states has 2n table entries, and each entry chooses a symbol to write, a direction, and a next state (n states or halt). For n = 2 there are (2ยท2ยท3)^4 = 20,736 machines.

Python Searching all 2-state machines for the busy beaver

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The search finds that no two-state machine halting on a blank tape runs longer than 6 steps or leaves more than 4 ones. (The count of steps includes the final halting move.) For three states the champion runs 21 steps; for four states, 107; for five states the record is 47,176,870 steps, and for six states, no one knows an upper bound: the numbers outgrow every computable function. This is a vivid, concrete picture of uncomputability.

We capped each run at 60 steps. That is safe for two states only because we can check the result against the known theory; in general you cannot know whether a machine that has not stopped yet will ever stop. That is the halting problem, living inside our search loop.

Extension ideas

  • Multi-tape machines: keep a list of tape dictionaries and make rules read and write tuples. Re-implement the palindrome decider in linear time.
  • Nondeterminism: store a list of moves for each key and explore configurations breadth-first. Then your simulator decides NP-style guess-and-check machines.
  • A universal machine: write a machine description as a string (say "q0 1 q0 1 R;..."), feed it to your own simulator as the input of a program that parses and runs it. You have just seen why the halting problem proof works: programs can be data.
  • Tracing visualizer: print the trace as a table (time down, tape across), the same tableau used in the Cook-Levin proof.
  • Macros: build a library of reusable sub-machines (move to the end, copy a block, compare two blocks) and compose bigger machines.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. In the simulator, what happens when no rule matches the current state and symbol?

    A missing transition means the machine cannot continue and halts in a non-accepting state, which counts as rejection.
  2. 2. Why does the one-tape palindrome decider take quadratic time?

    About n/2 rounds of roughly n steps each give O(n^2) steps.
  3. 3. Why is the busy beaver function BB(n) not computable?

    If BB(n) were computable, run an n-state machine for that many steps: if it has not halted by then it never will, which would decide halting.
  4. 4. What does the busy beaver search over all 2-state machines show?

    Brute force over the 20,736 machines gives champions of 6 steps and 4 ones, the known values BB(2) in both versions of the game.

Summary

  • A Turing machine simulator is a text parser plus one loop over a dictionary-based tape.
  • Machines are easiest to trust when you test them against ordinary Python on every short input.
  • Step counting reproduces the quadratic cost of one-tape palindrome checking.
  • Brute-force search finds the 2-state busy beavers, and the uncomputable growth of BB(n) makes the halting problem tangible.

Next: Practice: Finite Automata and Regular Languages