Felienne describes how she, Daan van Berkel and some other friends went away for a weekend to hack a Turing machine out of Excel formulas. Lacking an infinitely long tape, they had to kludge around a bit, but the outcome is both cool and instructional (here's the machine itself). The Turing Machine is Alan Turing's "hypothetical device that manipulates symbols on a strip of tape," which formed the basis for modern, general-purpose computers.
Then, lets have a look at the machine itself. Since we are only using formulas, we cannot continuously change the tape. Therefore, we use one row in the spreadsheet to represent one state of the tape. Each following line represents the state of the tape after one transition. As Willem van de Ende poetically put it: “No state was harmed in the making of this Turing Machine”
This means the top most line of the spreadsheet (shown in yellow in the following screen shot) represents this initial state of the machine. C2 shows the row where we reach the halting state and D2 counts the number of 1′s from there. As the first line contains three 1′s, this machine indeed seems to be calculating the successor.
Now, how do we get from one state to the other? For this we need to do some administration. In column A, we save the column position of the head. In column B, we save the current state. With that we can calculate the value of one square on the tape, by looking at the state and the previous value on the tape, with the formula below:
Excel Turing Machine
(via Hacker News)
Matthew Borgatti, purveyor of such Boing Boing favorites as the Guy Fawkes Bandanna, the War Boy Bandanna, and the Lockpick Earrings, offers you your choice of his wares at at 20% discount, with the coupon code “jackhammerjill.”
Boing Boing readers already know about MakieLab, the startup where my friends and I make 3D printed, customizable dolls called Makies.
Sgt Crispy writes, “XKCD creator Randall Munroe, has made a spiffy little hoverboard game. Looks to be small, however, when you realize that boundaries are made to be broken, A massive world opens up to be explored.”
Celebrate Cyber Monday with some brain food. Save on any eLearning deal in the Boing Boing Store today using coupon code: CYBERMONDAY25. Below are a couple of our favorite eLearning offers: eduCBA Tech Training Bundle: Lifetime Subscription:Welcome to your personal online classroom, where you can finally study at your own pace, on your own time (and […]
This minimalist multi-tool will see to it that instead of rocking a tool belt, you’ll carry just one. It’s shaped slightly like a key and weighs less than an ounce, so it plays nice with your keychain. The strong surgical-grade stainless steel blade will last, and is handy for everyday tasks like opening boxes and […]
The Code Black is our top-selling drone of all time—and for good reason. This powerful, palm-size drone is not only insanely fun to fly, but can capture some serious video footage from up above. With a flight time of about 10 minutes and an ultra-smooth ride, it’s a great introductory drone for anyone looking to […]