Plate 43
Turing Machine
In 1936 the mathematician Alan Turing imagined the simplest possible computer: a long tape of squares, a head that reads and writes one square at a time, and a short table of rules.
- Family
- AI and Computing
- Origin
- Raised from a recipe
- Habit
- Diurnal: kept on the page
- Voice
- Yes, with the sound on
- Hands-on
- Yes
- Your own
- Your own number
- Licenses
- Own work (made in the page)
How to play
Tap it to run the program. Hands-on: slide the tape by hand; tap a tile to flip it.
Notes
Each rule says: in this state, reading this symbol, write this, move left or right, and switch to that state. Anything a modern computer can work out, a machine like this can too, given enough tape and time.
Tap it: the head reads a tile, flips it to write, and the tape slides, following the lit row of the rule card, until the machine halts with a bell. Add one turns 1011 into 1100 as the carry ripples left; tap again to count on. The busy beavers write as many 1s as a machine of their size can and still halt. With ✋ Hands-on on, drag the tape along by hand and it settles on a whole tile, so the head reads a new cell; tap a tile to flip it from 0 to 1 and back.
Its controls
| Control | Kind | Range | Start |
|---|---|---|---|
| Run the program | Tap | ||
| Run | Button | ||
| Flip | Button | ||
| Program | List | 3 choices | Add one |
Details
- Splats
- Opens at 200,000 at Mid Detail, 119,838 at Low, and up to 820,000 at Max
Is it right?
The transition tables correctly increment every supported 12-bit integer and run the two busy-beaver examples. The busy-beaver machines leave four and six ones. This is a finite, bounded demonstration of Turing’s tape model.
Correct
Turing described tape-and-rule computation in 1936.1
The head, states, write actions, and moves illustrate his model; the universal-computation claim presumes enough tape and time.
Correct
The add-one program implements binary carry.1
Every integer from 0 through 4095 produces its independently calculated increment; 1011 becomes 1100.
Correct
The two- and three-state busy beavers write four and six ones.2
Independent rule traces agree with all writes, moves, states, halts, and final tapes, taking six and 13 transitions respectively.
Simplified
The tape picture is a bounded illustration.1
The input parser caps the bit count and the interpreter caps the transition count; this is not an implementation with unlimited tape and time.
- 1On Computable Numbers, with an Application to the Entscheidungsproblem, Alan Turing, 1936; University of Virginia copy
- 2Busy beaver research, Heiner Marxen
- Simplified
- Input is at most 12 bits and runs stop after 60 transitions. A 13th overflow bit can lie outside the visible strip. The three-state six-one example runs in 13 steps; the separate maximum-runtime record is 21, not 13.
Sources and credits
Made in Splashery. Its code is MIT.