| mark | ||||
|---|---|---|---|---|
| 0 | 1 | * | ||
| state | 0 | |||
| 1 | ||||
| 2 | ||||
| 3 | ||||
| 4 | ||||
speed
example rulesets
On this day in 1936, Alan Turing stood before the London Mathematical Society and delivered a paper entitled On Computable Numbers, with an Application to the Entscheidungsproblem, wherein he described an abstract mathematical device that he called a “universal computing engine” and which would later become known as a Turing machine, and used this device to prove that Hilbert’s Entscheidungsproblem (halting problem) was not solvable.
Although Alonzo Church beat the 24 year old Turing to that proof by a matter of months with his lambda-calculus approach, the two models of computation they used are equivalent - either can replicate the behavior of any given (non-quantum) algorithm - and Turing’s model is arguably more intuitive and elegant. And although it is an abstract and physically impossible device, it did help to inspire John von Neumann’s design of the architecture that underlies most of modern computing.
As a Stitch Fix tribute, we’ve melded a Turing machine and a 1936 Singer sewing machine. Although the tape is not infinite (you are limited to 500 entries in either direction), it otherwise functions as an actual Turing machine.
The current state of the machine (which is initialized to zero upon start) is shown at its base. At each step, the machine reads the mark on the tape directly below its needle and then follows the rule specified in the cell of the table that corresponds to that mark and to its current state. The syntax for the rules within each cell of the table is as follows (note that you can leave cells blank if they are never to be used):
1st character = mark to make, by overwriting the mark currently below the needle:
either 0 or 1 or *
(the * is a non-essential convenience for place-marking)
2nd character = direction to move after making that new mark:
"L", "R", "N" (no movement) or "T" (terminate)
3rd character = state to change to:
0-4 (ignored if "T" used as second character)
You can stop the machine to see the current output, then change the table (or try one of the suggested example tables), and click the start button again to watch it carry out your algorithm.
