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)
When game critic Jim Sterling uses video clips of the games he reviews on YouTube, the game companies claim copyright ownership of the video and run ads on Sterling’s reviews. He doesn’t like that because his videos are funded by Patreon and he doesn’t think his audience should have to see ads. So what he […]
Dyson Logos’s G+ account is an endlessly scrolling inventory of hand-drawn D&D maps, each one cooler than the last.
Campaigners from Liberty, a civil liberties group, took to the streets of London (and the lobby of the Home Office!) and grabbed peoples’ phones, browsing them while explaining that they just wanted to build a detailed dossier of their lives by looking at their communications, browsing history and location data — mirroring the way that […]
Isn’t it about time to stretch what your Mac can do? I mean, you’ve got plenty of great programs now…but don’t you think you could use some new tools to get your creative, analytical and organizational juices really flowing? It’s spring, so we cleaned up a whole bunch of super-cool apps lying around and packaged […]
In the world of app development, there’s no greater arena to find success than with Android users. About 80% of the smartphones in use today worldwide operate on the Android operating system, so if you build a great app that Android users love, you’re an international rock star. You’ll be able to make sure your […]
Unless you’re a programmer or webmaster, the term SQL probably doesn’t mean much to you. But for those looking to understand more about how and why the web works the way that it does, know this – SQL and its process of managing and presenting large data sets is everywhere…and it’s the most in-demand programming […]