Turing machines

Tape, head, states and transition functions; tracing a Turing machine; the universal Turing machine and why it matters.

A6.9Theory of computationA level25 min

To prove the Halting problem had no solution, Turing first had to say exactly what "an algorithm" is. His answer, in 1936, was an imaginary machine simple enough to reason about and powerful enough to carry out any algorithm at all. It is still the model computer scientists use to define what can be computed. A finite state machine is the control unit of a Turing machine; the Turing machine adds the one thing an FSM lacks, unlimited memory.

The parts of a Turing machine

• A tape, divided into cells, that is infinitely long. Each cell holds one symbol. Cells that have never been written hold a blank, written _ here (books also use □).
• A read/write head that is over one cell at a time. It can read the symbol there, write a new symbol, and move one cell left or right.
• A finite alphabet of symbols the tape can hold, such as {0, 1, _}.
• A finite set of states, with one start state and one or more halting states.
• A transition function saying, for each state and the symbol under the head, what to write, which way to move and which state to go to.

The machine starts in the start state with the input written on the tape and the head on the first symbol. It then repeats one step: read, look up the transition, write, move, change state. It stops when it reaches a halting state.

Transition functions

Each transition rule is written with the Greek letter delta, δ:

δ(S0, 1) = (S1, 1, →)

Read it as: "in state S0, reading a 1, go to state S1, write a 1 and move right". The arrow → means move right and ← means move left. Some books write the output in a different order or use R and L, so read the question's key. A whole machine is a list of these rules, one for each state and symbol the machine can meet.

This machine adds an even parity bit to the end of a binary string: it writes a 1 if the string has an odd number of 1s, and a 0 otherwise, so the result always has an even number of 1s.

• δ(S0, 0) = (S0, 0, →)
• δ(S0, 1) = (S1, 1, →)
• δ(S1, 0) = (S1, 0, →)
• δ(S1, 1) = (S0, 1, →)
• δ(S0, _) = (SH, 0, →)
• δ(S1, _) = (SH, 1, →)

S0 means "even number of 1s so far" and S1 means "odd so far", exactly like the parity FSM in lesson A6.1. The difference is that when this machine reaches the blank at the end, it writes its answer on the tape. SH is the halting state.

State transition diagrams

A Turing machine's diagram looks like an FSM's, with each arrow labelled with the symbol read, the symbol written and the move. Here 1/1,R means read 1, write 1, move right. The halting state has a double circle.

Hand-tracing

Trace the machine on the input 1101, with the head starting on the first 1. Positions count from 0 at the first symbol of the input.

The machine halts in SH with 11011 on the tape: four 1s, even. In an exam trace, show the state, the head position and the tape after every step.

A Turing machine in Python

The tape is infinite in both directions, which a dictionary from position to symbol models well: any position never written is blank. The transition function is a dictionary from (state, symbol) to (next state, write, move).

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

parity = {
    ("S0", "0"): ("S0", "0", "R"),
    ("S0", "1"): ("S1", "1", "R"),
    ("S1", "0"): ("S1", "0", "R"),
    ("S1", "1"): ("S0", "1", "R"),
    ("S0", "_"): ("SH", "0", "R"),
    ("S1", "_"): ("SH", "1", "R"),
}

def run(table, text, trace=False):
    tape = dict(enumerate(text))
    head = 0
    state = "S0"
    steps = 0
    while state != "SH":
        symbol = tape.get(head, "_")
        state, write, move = table[(state, symbol)]
        tape[head] = write
        head = head + 1 if move == "R" else head - 1
        steps = steps + 1
        if trace:
            print(steps, state, "".join(tape[i] for i in sorted(tape)))
    return "".join(tape[i] for i in sorted(tape)).strip("_")

print(run(parity, "1101", trace=True))
print(run(parity, "1001"))

Run this in the simulator

Look at run. It knows nothing about parity: all of that is in the table. Give it a different table and it becomes a different machine.

The universal Turing machine

Each Turing machine does one job, like a computer with a single program built into its wiring. Turing's greatest step was to show that one machine can do every job. A universal Turing machine (UTM) reads, from its own tape, a description of any other Turing machine (its transition rules, written out as symbols) followed by that machine's input. It then simulates the described machine step by step and produces the same result.

Why this matters:

• The stored program concept. A UTM treats a program as data on the tape. That is the idea behind every general-purpose computer since: the same hardware runs any program loaded into memory, and von Neumann's design put it into practice.
• A definition of computable. Anything a real computer can compute, a Turing machine can too, given enough tape and time; it is just far slower. Turing machines and every programming language can compute exactly the same things. So "computable" means "computable by a Turing machine", and a problem no Turing machine can solve, like the Halting problem, no computer can solve.
• A tool for proofs. Because the machine is so simple, it is possible to prove things about every algorithm at once, which is how the Halting problem was settled.

The run function above is a small universal machine written in Python: the table it is given is the program.

Task: add one in binary

Write the transition table for a Turing machine that adds 1 to a binary number, and run it with run.

• run(table, text) is written for you. The head starts on the first (leftmost) symbol in state "S0", the machine halts when it reaches state "SH", blanks are "_", and run returns what is left on the tape with the blanks at either end removed. It gives up and returns None after 1000 steps.
• Write table: each key is (state, symbol) with symbol one of "0", "1", "_", and each value is (next_state, write, move) with move either "L" or "R". Use as many states as you need, with "S0" as the start state.
• The arithmetic must be done by the machine: no int, bin or format.
• For each string in tests, in order, print it, ->, then the result of running your machine on it. For example 1011 -> 1100. Four lines in all.

Think about how you add 1 by hand: where do you start, and what happens to a run of 1s at the end?

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

tests = ["1011", "111", "0", "1001"]

def run(table, text):
    tape = dict(enumerate(text))
    head = 0
    state = "S0"
    for steps in range(1000):
        if state == "SH":
            return "".join(tape[i] for i in sorted(tape)).strip("_")
        symbol = tape.get(head, "_")
        state, write, move = table[(state, symbol)]
        tape[head] = write
        head = head + 1 if move == "R" else head - 1
    return None

table = {}

Challenges

1. Trace your machine on 111 in a table like the one above. How many steps does it take?
2. Write a Turing machine that flips every bit (0 to 1, 1 to 0) and halts at the first blank.
3. Why can a Turing machine recognise {0ⁿ1ⁿ | n ≥ 1} when no FSM can? What does it use that an FSM does not have?