On 17th July 2019, I wrote a short blog post elsewhere about the then recently published new design for the £50 note. In an enormously nerdy manner, my blog explained the set of configurations, symbols and operations on the design, with reference to the Turing paper that they were derived from. The next day, a scientist involved with the design of that note, asked on Twitter if anyone had figured out how the details within his design should be interpreted. It seems I was the first geek to have done this, so I wrote a short follow-up blog post to explain the formal notation that Turing had developed in his paper. Both blog posts are reproduced below, as some context that might help explain the domain name of this web site.
There has been a lot of publicity recently about the new £50 note in the UK, carrying an image of AM Turing. Predictably, a lot of the attention around Turing has focussed on his role in cracking the Enigma code during World War II. This achievement was certainly consequential. There is a consensus among historians that it shortened the war by several years, saving millions of lives. Indeed, on the new design for the £50 note you can see a nod to the British “Bombe“, which was designed by Turing and used to break Enigma.
Also prominently displayed on the design though, is a table of configurations, symbols and operations. While it doesn’t look like much, this is taken from Turing’s 1936 paper, “On Computable Numbers, With An Application To The Entscheidungsproblem”. That paper essentially invented the concept of a programmable computer. The specific table reproduced on the £50 note, relates to an intellectual leap in the paper that actually proposes the very idea of what we call software today.
To illustrate this, we can start with the most basic computing machine that was imagined in the paper. Consider a tape divided into squares, whereby each square may have a symbol printed on it. On the new design for the £50 note above, you can see a section of such a tape at the bottom of the image, with a series of 0 and 1 symbols printed on it (this is Turing’s birthday expressed as a binary number). Since we are treating the machine that will process the tape as a mathematical construct rather than an actual physical device, we can allow the tape to be infinitely long.
Now consider a computing machine that can look at one square of the tape at a time, and follow some fixed instructions. In the most simple example used by Turing in his 1936 paper, the machine need only print a sequence of 1s and 0s on the tape, with a blank square between each symbol. That is, the output of this machine will be an infinite tape that looks like this …
Turing’s paper describes a machine (m) that would compute a tape like this, as illustrated in the extract from his paper below. In this extract, P0 is an instruction to Print a 0 in the current square, P1 is an instruction to Print a 1 in the current square, and R is an instruction to move one square to the Right. The machine can be in one of four possible states or m-configurations.
We can follow through the steps of Turing’s example above, by starting with a blank tape and reading each line of the table in turn. In the first line of Turing’s table, the machine Begins in m-configuration b. Reading this line we can see that if there is no symbol in the current square of the tape, the behaviour required is that the machine must Print a 0 and move one square to the Right, then change the m-configuration of the machine to c. This should leave us with a tape that looks like this …
Looking at the next line of the table, we can see what the machine must do next, since it is in m-configuration c. The second line of the table states that if there is no symbol in the current square of the tape (which there is not, as we can see highlighted above in red) then the behaviour required is that the machine must move one square to the Right, then change the m-configuration of the machine to e.
At this point, it is worth noting the conditional nature of the operations and behaviours, which follow from the configurations and symbols. In this very simple example, we always move to the Right along a blank tape, and so each new square we consider will always have no symbol on it. However, more complex machines can have many symbols on the initial tape as inputs to the machine, they can move to the Left to revisit previously processed squares, and they can behave differently depending on the current m-configuration or the current symbol. For example, while in any given m-configuration, the machine may behave differently depending on the symbol in the current square. Similarly, when encountering any given symbol in the current square, the machine may behave differently depending on what m-configuration it is in.
A computing machine controlling an elevator might be used as an approximate analogy. Such a computer might represent the floor that it is currently located on, as the current configuration of the machine. The computer might then interpret an input from a button pressed by the occupant, like an input from the symbol on the current square of the tape. For example, the configuration of the machine may indicate that the elevator is currently at floor 5, but computation may result in a move that is either up or down, depending on which button the occupant presses. Similarly, the occupant may press the button for floor 5 at any given time, but the machine may then compute a move that is either up or down depending on whether its current configuration is higher or lower than 5.
Returning to Turing’s paper, the next line of the table describes what the machine must do in m-configuration e. Since there will be no symbol in the current square, the behaviours required are that the machine must Print a 1 and move one square to the Right, then change the m-configuration of the machine to f (Turing actually uses the gothic k from the German alphabet, but it looks very like f). This should leave us with a tape that looks like this …
The final line of Turing’s table moves the current square to the Right and then brings the machine back to the m-configuration it began in, so that the pattern of 1s and 0s can repeat infinitely (according to the required output for the computation). Of course Turing doesn’t use this term himself, but we now call this a Turing Machine. While Turing’s initial example machine is incredibly simple, vastly more complex machines are possible. For example, the very simple machine defined above is actually computing the binary digits after the decimal point of the rational number 1/3, but Turing goes on to specify machines that can perform much more complex computations.
By analogy with the computers of today, this kind of Turing Machine could be compared to a hardware device, which can only execute one fixed set of operations. That is, this Turing Machine can only compute the binary digits of the number 1/3 after the decimal point, and it can’t do anything else. However, Turing now goes on to make an intellectual leap that by analogy, can be considered to arrive at the concept of software, or programmable computers in general. In the extract below, Turing specifies how his tables of configurations, symbols, behaviours and operations, can be written as a ‘standard description’ using various characters. From there he outlines how these standard descriptions of Turing Machines, can each be expressed as a ‘description number’. That is, every Turing Machine can be written as an integer, even those performing quite complex calculations. For example, an entire Turing Machine can be written as a single large integer, even where the machine implements a complex algorithm to compute the digits of an irrational number like say π or √2.
The extract below includes the full context for the table that is now reproduced on the new £50 note. Turing is describing how even the most detailed instructions, for computing even the most complex algorithms, can be expressed as a single integer.
As an aside, the final sentence of this extract is related to Hilbert’s Entscheidungsproblem, which was after all the original point of Turing’s paper. However, Turing then goes on after this extract to specify what we now call a Universal Turing Machine. That is, once any given Turing Machine can be written as a ‘description number’, that integer can then be printed on a tape and processed by a separate Universal Turing Machine. Consequently, instead of creating a hardware device to perform just one specific computation, the instructions for how to carry out the computation can be stored (on a tape or otherwise) and then processed by a separate computer.
Contemporary computer programmers will recognise this as the concept of software itself. Today, a developer may compose an algorithm in a specific programming language, and then compile that algorithm into machine code. That machine code can be considered to be a representation of a set of instructions, but it can also be considered to be an integer (for a complex algorithm it will typically be a very large integer). Once the developer has created this executable machine code, she can run it as software on a separate physical computer. In effect she has defined a Turing Machine, in order that it can be computed separately by a Universal Turing Machine.
The first formal descriptions of devices that we would recognise today as computers, were defined using the Von Neumann Architecture. John von Neumann and those who constructed the earliest programmable computers (such as the ENIAC) were providing practical implementations of Turing’s ideas about computation, and this extends to contemporary computing devices too. Your smart phone is a Universal Turing Machine and each App on it is an individual Turing Machine. Whereas Turing’s 1936 paper used various definitions of slightly different machines for different purposes, Computer Science text books today typically formalise a Turing Machine (M) using the septuple M = ⟨Q, Γ, b, Σ, δ, q0, F⟩ where:
- Q is the set of configurations the machine may be in
- Γ is the alphabet of symbols that the machine must process
- b is the blank symbol
- Σ is the set of input symbols that may be on the initial tape
- δ is the transition function of operations performed as the machine moves between configurations
- q0 is the initial configuration of the machine
- F is the final configuration that the machine may halt in
This septuple doesn’t seem like much, but as the new £50 note illustrates, the work of AM Turing represents the invention of the programmable computer and the concept of software. That’s certainly a sufficiently consequential achievement to take its place alongside the Bombe that broke Enigma. In fact, some people even have a tattoo of this septuple.
I recently posted a short blog that tried to explain the meaning and significance of the table on the new £50 note. The table includes some rows and columns of configurations, symbols and operations. Afterwards, I posted a separate question about the additional line of terms separated by semi-colons, which is printed beneath the table on the AM Turing £50 note.
For completeness, I’d like to briefly set out what the answer to this question is, and what the extra line of terms means. However, I should start by noting that it seems I wasn’t the only person asking this question. Dr Arthur Turrell is a scientist at Imperial College and King’s College, London. He’s also a researcher at the Bank of England and he was part of the team that was responsible for the design of the new £50 note.
The single line of terms being discussed, appears underneath the table of configurations, symbols and operations. If you’re struggling to find the specific line that Dr Turrell is asking about on the £50 note, it’s the sequence of white characters that ends beside Turing’s chin.
If the text is difficult to make out in this image, here are the same terms in plain black and white …
Understanding what this means requires a degree of working backwards through Turing’s seminal 1936 paper. Let’s begin at Section 5 of the paper.
The final few sentences of the extract above explain that Turing’s notation involves listing table rows, which are to be separated by semi colons. So immediately we can interpret the single line of terms from the £50 note as follows …
Looking further back through the extract from the Section 5 of Turing’s paper above, we can see that each row should be interpreted as listing in turn the m-configuration, Symbol, Operations and the Final m-configuration. As such, we can now write the singe line of terms from the £50 note like this …
Still working backwards through Section 5 of Turing’s paper, we can now interpret as m-configurations, the terms that are enumerated as subscripts of q. We can also interpret the Symbols that are enumerated as subscripts of S, in the following manner …
Still working backwards through Turing’s paper, we can now move to Section 3, where he defines the very first ever Turing Machine. We can see that whereas the m-configurations are organised into enumerated subscripts of q within Turing’s more formal notation, they were originally given four specific characters by Turing. We can refer to these characters as b, c, f and e (although the character that looks like f in the extract from Section 3 of the paper below, is actually the gothic k in the German alphabet). We can also see that before Symbols were organised into enumerated subscripts of S within the more formal notation, Turing simply stated the specific digit that was to be printed, such as a 0 or a 1.
If we continue to work backwards therefore, we can replace all the q and S terms with their various enumerated subscripts, and instead use the specific terms that Turing had originally listed in Section 3 of his paper.
Those who read the original blog post (or the Twitter thread above with Dr Turrell) will have already realised where this is headed. The single line of terms as it appears on the £50 note, describes the very first Turing Machine that was ever specified. That is, this line of terms uses Turing’s own notation as he formalised it in Section 5 of his paper, in order to provide a representation of the machine that he used as an example in Section 3 of his paper. The initial example that was chosen by Turing himself to illustrate his concept, computes the binary digits of the rational number 1/3, which appear after the decimal point.
The first Turing Machine that was ever specified, is described by the extract from Turing’s paper illustrated above. The single line of terms that appears on the £50 note, uses the more formal notation that Turing later defines, in order to provide a more concise representation of the original Turing Machine. Kudos to Dr Turrell and his colleagues. This is a really elegant touch, on a beautifully designed bank note.
AM Turing lived at 43 Adlington Road and the gothic characters he used to represent the state of the first machine in his original 1936 paper also appear in this image.