This weekend, I went on a get away with some fellow developers of Devnology. We do this every year, drinking beer, talking about programming, and often also, programming.

This year I had even more fun than usual, as Daan van Berkel proposed we build a Turing machine in Excel. In this blog post I’ll talk about how we built it, but of course you can also skip all that and just download it and play with it. Please note that automatic calculations are turned off, so if you want to run the machine, you’ll have to do it manually.

First of all, what is a Turing machine?

According to Wikipedia, a Turing machine is a ‘hypothetical device that manipulates symbols on a strip of tape’.

The strip of tape is infinite and the Turing machine can read and write it, but also maintains an internal state. Based on the current symbol of the tape, the Turing machine can change its current state. An example of a very simple Turing program is this:

This program, with 3 states and 4 transitions, changes the first block of 1’s into blanks and than halts. For example, it changes the tape

1 1 1 _ _ 1 _ _ 1
^

into

_ _ _ _ _ 1 _ _ 1
______^
This seems a very simple mechanism, but it can be used to simulate every possible calculation a computer can do. Not very efficient, you’ll see later that we need 1832 steps to calculate 3 to the power 3, but still. Every possible calculation! It was first described by Alan Turing in 1936, so before there even were actual computers.

Our goal was to built the Turing machine using formulas only. We started with creating a separate worksheet to represent the state table, as shown below.

This is simply the encoding of the state machine with current and next state, what to read and write and in what direction to move the head. The first column is a formula, namely the concatenation of columns B and C, state and symbol to read. For instance, the formula in A2 reads =B2&”-“&C2. The value is used as a key to determine what transition to use, given a state and symbol. With the example above, we calculate the successor for unary numbers, we read a list of 1’s (possibly preceded by blanks) and add one 1 at the end.

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:

Quite a complex formula, so let’s format it a bit:

=IF(COLUMN(C5)=A4,
IFERROR(VLOOKUP(B4&”-“&C4,StateTable,4,FALSE),C4)
,C4)

Starting with the final line: If the column of this cell is not equal to A4, in other words, if the head is currently not this cell, the value will not change, i.e. we can use the value in the previous row.

That leaves us with the following for the case where the head is exactly on this column:
IFERROR(
VLOOKUP(B4&”-“&C4, StateTable, 4, FALSE),
C4)

In the first argument of the VLOOKUP, we concatenate the state and the symbol at the head, to find it in the StateTable (second argument is the range to search in, we have given the state table the name StateTable) We grab the 4th column, which is the Write column and we want to have an exact match (4th argument)

If the value is found, this will be the new state of this square on the tape. Otherwise, again, we take the previous value. This is meant for when we reach the halting state, as, when we reach that, we will never find a transition and we don’t want the tape filled with #N/A’s after the halting state.

In column B we too use a VLOOKUP to determine the new state.

The formula is shown below ($ removed for clarity)

=IFERROR
(VLOOKUP(B4&”-“&INDEX(A4:FM4,A4), StateTable, 6,  FALSE),
B4)

Here the lookup key is a bit more complex, we are concatenating the previous state in B4, with the value at the head that we find with the INDEX function, which returns the value of the A4th cell in the range A4:FM4. This time, we want to get the sixth column, the new state.

Column A, to calculate the new head, contains a similar formula, namely the third line of this, which looks up the direction.

=IFERROR
(VLOOKUP
(VLOOKUP(B4&”-“&INDEX(A4:FM4,A4),StateTable,5,FALSE),   <– returns R or L
DirectionTable,2,FALSE),0)+$A4

Once we have found the direction, we look in a second table, the DirectionTable, to know how the head needs to move. L corresponds with -1 and R with 1. This is added to the current head.

That’s it, those are all the formulas needed to build a Turing Machine. Not even that much. I guess it took us about an hour to built this. The final awesome thing we added is conditional formatting for the head. We had to fiddle a bit, but it turns out the syntax for conditional formatting allows you to highlight formulas is COLUMN(C5)=$A5. Using that on the whole tape results in this.

You actually see the head moving! We found this very useful for debugging state machine definitions, as you can very easily see where your head does crazy things. The head of the state machine that is 🙂 We reckon that this visualization makes our implementation really useful for educational purposes as it is so clear what is going on.

After this, Daan and me were dared to implement the power operation. That took us another 4 hours, but we did it (download here). The input was given again in unary notation, so 2 to the power of 4 would be

1 1 _ 1 1 1 1 (let’s call them A and B)

I not going into the detail of the state machine, as it has 39 stated and 81 transitions, but our basic idea was to multiply A with itself B times. Therefore we first put one 1 at the end of the tape, and then place a copy of A at the end of the tape. Then, we multiply the two numbers at the end of the tape (initially 1 and A). For this we made a sub state machine. In the Excelsheet, there are the states starting with S. We repeat this B times, by crossing off one 1 in B for every time we do this. Easy right?

The tape (at zoom 10%) is shown below. The cool thing is you can see the two different parts of the algorithm we use, the long sweeps are the copying of A and the smaller moves are the multiplication.

We had lots of fun building it, but it was also a really useful experience, as building the complex state machine requires you to be very precise, just trying stuff and hitting ‘calculate now’ will not do the trick. Also, as always, divide and conquer is a good approach; we first built and tested the state machine for multiplication and later embedded that into the final solution.

Bonus pic, here’s us working on it:

Update: If you like this post, please upvote it on HN: https://news.ycombinator.com/item?id=6416631