Fig. 43. §3 AI and Computing
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.
1Facts
- Shelf
- AI and Computing
- Kind
- Built from a recipe
- Your own
- Your own number
- Sound
- Yes
- Hands-on
- Yes
- Licenses
- Own work (made in the page)
2How to play
Tap it to run the program. Hands-on: slide the tape by hand; tap a tile to flip it.
3Its controls
Table I. Every control on this Splash.
| Control | Kind | Range | Start |
|---|---|---|---|
| Run the program | Tap | ||
| Run | Button | ||
| Flip | Button | ||
| Program | List | 3 choices | Add one |
4About it
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. 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.
5Details
- Splats
- Opens at 200,000 at Mid Detail, 119,838 at Low, and up to 820,000 at Max
6Is 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.
- [1]On Computable Numbers, with an Application to the Entscheidungsproblem, Alan Turing, 1936; University of Virginia copy
- [2]Busy 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.
7Sources and credits
Made in Splashery. Its code is MIT.
