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)
Microsoft has announced an Xbox Onesie that looks like a cuddly spacesuit, and comes with pockets sized to fit game-controllers, forearm grips to prevent slippage at key moments, and roomy hoods that can accommodate enclosed gamer headsets.
Leonard Richardson isn’t just the author of Constellation Games, one of the best debut novels I ever read and certainly one of the best books I read in 2013; he’s also an extremely talented free/open source server-software developer who has been working for the New York Public Library on a software project that liberates every […]
Dann and Greg May’s Polyhero dice are kickstarting a new set of odd-shaped polyhedral random-number generators: the Wizard Set complements last year’s Warrior Set with seven dice shaped like potions, fireballs, bolts, wands and orbs.
To be a Pokémon master, you’ll need a phone that won’t constantly die on you. Because nothing is worse than seeing the screen go black right as you’ve finally found the Charizard of your dreams.That’s why we’re so excited about the LinearFlux PokeCharger Portable Battery ($39.99). With its 3.0 Amp HyperCharging technology, this slim battery will […]
The tech industry is constantly innovating, and in order to stay competitive, you’ll need to keep up. The Programming Into the Future Bundle was created to teach you the skills employers are looking for at this very moment, including in-demand coding languages like Google Go.The bundle of courses includes instruction on a range of innovative tools that advanced coders […]
If you’re running low on MacBook storage, your options are pretty limited. External hard drives mean toting around another piece of bulky equipment, and you probably don’t want a USB stick constantly protruding from your laptop.That’s why the Nifty MiniDrive for MacBooks is such a desirable alternative, and one of our top tech finds this year. You can add […]