Collection · 13 machines · curated by @thethinkmachine
Turing machines that compute
Machines that leave an answer on the tape rather than only accepting: addition and multiplication in unary, increment and counting in binary, copying, reversing and sorting.
Essay
Most Turing machines in a course decide something: they halt in an accepting state or they do not. The machines here compute — they halt with an answer written on the tape, which is the sense in which Turing defined a computable function. Every one of them was checked twice over: the app decided each input, and a separate simulator confirmed what was left on the tape.
Arithmetic in unary
In unary, a number n is n marks in a row, and arithmetic becomes editing. Addition turns the + into a 1 and erases the last 1 — two edits, whatever the numbers. Multiplication is repeated addition at walking pace: for each mark of the first number, the machine copies the whole second number to the end of the tape, one mark per trip, marking what it has used and restoring it afterwards. Its running time grows with the product of the inputs, times the distance it walks.
Binary
Binary is exponentially shorter, and the machines are different in kind. Increment is the carry rule done by hand. Counting to n converts unary to binary by erasing one mark at a time and incrementing a counter that grows leftwards. Binary addition on one tape transfers a unit per lap, which is slow; on three tapes the same job is a single sweep with the carry as the only state.
Moving things around
A Turing machine’s tape is its only memory, so even copying is work. Copying w to w#w carries one symbol per round trip and takes time proportional to n². Reversing takes the last symbol each time — and needs to know where the left end of a one-way tape is, which a machine can only find by having marked it. Sorting 0s before 1s is insertion sort, one swap at a time.
Every machine on one tape pays for distance. A tape head that must fetch something n cells away spends n steps doing it, and a computation that needs to compare or copy all of its input does that n times. A second tape removes most of the walking, which is why the multi-tape machines here are so much faster — and why a one-tape machine can still simulate them, at most quadratically slower.
At a glance
| Machine | Size | Steps | Non-blank | Standard format | |
|---|---|---|---|---|---|
| Unary addition | 1 | 0 | |||
| Unary multiplication | 1 | 0 | |||
| Binary increment | 2 | 1 | |||
| Counting to n in binary | 2 | 1 | |||
| Binary addition a+b | 1 | 0 | |||
| Copy a string: w ↦ w#w | 1 | 1 | |||
| Reverse a string | 1 | 0 | |||
| Sort the 0s before the 1s | 1 | 0 | |||
| Say every letter twice | 1 | 0 | |||
| Binary to unary: counting down | 2 | 0 | |||
| Unary remainder: a mod b | 1 | 0 |