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)
John Scalzi’s on tour with his new novel, The Collapsing Empire: he’s posted a list of ten things every touring author knows, and very few other people ever get to see.
Steven Boyett writes, “Humble Bundle has released a unicorn-themed Bundle, with proceeds to benefit the World Wide Fund for Nature and Fauna & Flora International. For as little as $1.00, you can get Ariel, by Steven R. Boyett (full disclosure: that’s me); Unicorn Mountain, by Michael Bishop; Homeward Bound, by Bruce Coville; and Unicorn Triangle, […]
With less than a week to go until the debut of Walkaway, my next novel for adults, Portland’s Powell’s Bookstore has run a long Q&A with me about the book, my writing habits, my favorite reads, and many other subjects.
Even the most expensive pair of hi-fi headphones can’t match the feeling of bass rumbling through your body at a live show. That’s why music aficionados designed The Basslet, an accessory that reproduces that sensation from your wrist. Does it make your whole body shake with deep subs? Not really, because that would be terrifying, but […]
They probably just sleep a lot. But still, you can remotely keep an eye on them when you’re at work and missing them deeply with this HD monitor from Kodak.If you have a new puppy that destroys everything in sight, or you just want to be a little more security-conscious, this WiFi camera is a […]
Thinking of a business idea is the easy part. Doesn’t even have to be a “good” idea, you can still get people to throw money at a non-existent venture, but to do that you need to at least have something even resembling a viable business plan. Why doesn’t anyone do it then? Because building that semi-viable […]