Tape, head and a table of rules
A Turing machine is a very simple computer. It has an endless tape of cells, a head that reads and writes one cell at a time, and a table of rules. Alan Turing described it in 1936.
It matters because anything a real computer can compute, a Turing machine can compute too. So it lets us ask what computing can and cannot do.
By the end of this lesson
Note
I can trace a Turing machine on a tape.
Key words
| Word | What it means | Example |
|---|---|---|
| Tape | a row of cells, each holding one symbol | |
| Head | the part that reads and writes one cell at a time | |
| Blank | the symbol in a cell nobody has written | _ |
| Rule | in this state, on this symbol: write, move, change state | |
| Halt | to stop because the machine has finished or no rule fits | |
| Turing machine | a tape, a head, states and rules together |
The cells students fill in are left blank in this preview.
A Turing machine writes as well as reads
A finite automaton only reads. A Turing machine also writes to its tape, and it can move its head left or right.
Each rule looks at two things: the current state and the symbol under the head. It then says what to write, which way to move, and which state comes next. The machine halts when it enters the state halt or no rule fits.
Worked example: rules that flip every bit
| State | Reads | Writes | Moves | Next state |
|---|---|---|---|---|
| go | 0 | 1 | Right | go |
| go | 1 | 0 | Right | go |
| go | _ | _ | Stays | halt |
The cells students fill in are left blank in this preview.
Tracing the tape 101 step by step
| Step | Tape, head in brackets | Rule used |
|---|---|---|
| 0 | [1]01 | Start in go |
| 1 | 0[0]1 | Read 1, write 0, move right |
| 2 | 01[1] | Read 0, write 1, move right |
| 3 | 010[_] | Read 1, write 0, move right |
| 4 | 010[_] | Read blank, stay, halt |
The cells students fill in are left blank in this preview.
The bit-flipper by hand
# The bit-flipper by hand: read a cell, write the opposite, move right.
tape = list("10110")
head = 0
while head < len(tape):
print("head at", head, "reads", tape[head])
if tape[head] == "0":
tape[head] = "1"
else:
tape[head] = "0"
head = head + 1
print("".join(tape))
# Change the tape to "0011" and run again.
The shell flips bits the same way
echo 10110 | tr 01 10Shown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
Flip another tape
echo 1011 | tr 01 10Shown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
A second machine adds one in binary
This machine walks right to the end of the number, steps back, then carries leftwards. A 1 becomes 0 and the carry moves on. The first 0 it meets becomes 1, and the machine halts.
Leave one spare 0 on the left for a number of all ones. On the tape 011 it takes seven steps and leaves 100.
Rules for adding one in binary
| State | Reads | Writes | Moves | Next state |
|---|---|---|---|---|
| right | 0 or 1 | The same | Right | right |
| right | _ | _ | Left | carry |
| carry | 1 | 0 | Left | carry |
| carry | 0 | 1 | Stays | halt |
The cells students fill in are left blank in this preview.
Check the answer for 0111
python3 -c "print(bin(int('0111', 2) + 1))"Shown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
A common mistake
Warning
Many people think a Turing machine is weaker than a real computer because it is so simple. It can compute everything a real computer can. It is only slower. That is why we study it: if a problem is impossible for this machine, no ordinary computer can solve it either.
Why one simple machine matters
A finite automaton is a Turing machine that never writes and only moves right. Letting the head write and move both ways is what gives the machine unlimited memory.
A machine can also be built that reads another machine's rules from its tape and runs them. That is a universal Turing machine, and it is the idea of a stored program.