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)
Five years ago, we won an unprecedented victory: spurred on by blackouts of more than 50,000 sites, more than 8 million Americans called Congress to object to the Stop Online Piracy Act (SOPA), a brutal internet censorship bill that would have been a stake through the heart of the open net. SOPA, which had been […]
The next installment in the extraordinary lecture/reading series features Hugo-winning environmentalist author Kim Stanley Robinson and prolific historical novelist Cecelia Holland: $10 donation at the door, no one turned away for lack of funds. (Images: AllyUnion, CC-BY-SA; Other Change of Hobbit)
Sean Bonner’s posted his share of viral images over the years, but the most recent time was a little different: he tweeted a picture of an anti-Trump political sticker he spotted in Tokyo, created by street artist 281_Anti nuke.
One of the best ways to progress a career in project management is through earning recognized certifications. These certifications carry significant clout and don’t require expensive tuition or student loans. This Ultimate Project Management Certification Bundle is a great example of an affordable way to get ahead. It includes training for 9 certifications including PMP, […]
There’s nothing quite like the rush of playing against a real human opponent. But from a developer standpoint, creating fun multiplayer experiences is incredibly complex. Fortunately, the Unity3D game engine has made all aspects of game creation, including multiplayer functionality, as accessible as ever.This Unity Course Bundle introduces all of the necessary elements of creating […]
The 2016 World Series game 7 will undoubtedly go down in history as one of the greatest baseball games of all time. With endless suspense, a nefariously-timed rain delay, and extra innings, it reminded over 40 million viewers why they love America’s pastime – and why all bets were truly off in 2016. Savor the […]