By Monty, 14th May 2015

**Alan Turing** published a ground-breaking paper in 1936, *On computable numbers, with an application to the Entscheidungsproblem* (PDF). It was about an esoteric problem in mathematics, for which he needed a theoretical model of how a mathematician computes with pencil & paper. He called this model an *automatic machine*; we now call it a **Turing Machine**, which we now recognise as containing the minimal elements of computers. In a sense, he invented computers as a by-product of his mathematical research! That paper is also generally acknowledged to have founded the modern discipline of theoretical computer science.

The Turing Machine is very simple. It consists of:

- an infinite
**tape**divided into cells along its length. Each cell contains a symbol, such as a letter or a number, taken from a specified set such as ‘0’ and ‘1’. - a
**head**which can read or write symbols on the tape, and move 1 cell one way or the other. - a
**register**that stores the current state of the machine. This machine can be in one of a finite number of states, each of which determine what happens next when a given symbol is read. - a
**table of instructions**that specify what the machine does, such as replace the current symbol with a new one, move along the tape, and what will be the next state. This table is a kind of program indexed by the state and current symbol.

Here’s a simple program to add 2 unary numbers (numbers in base 1, e.g. 5 = 11111).

state/symbol | 0 | 1 |
---|---|---|

0 | 1, +1, 1 | 1, +1, 0 |

1 | 0, -1, 2 | 1, +1, 1 |

2 | 0, +1, 2 | 0, +1, 9 |

The machine starts in state 0. If it reads a 1 from the tape, it gets the ‘instruction’ 1, +1, 0. The first element is the symbol to write back to the tape (replacing the current symbol). The 2nd is the direction to move the head: -1 = left, +1 = right. The 3rd is the new state. This is effectively a primitive programming language. You wouldn’t want to use this instead of Python! However, it is, *in principle*, as powerful as Python, in that it can compute anything that Python can!

The point of such a primitive language is that it allows us to reason clearly about the possibilities and limitations of computers. In his 1936 paper On Computable Numbers, Dr. Turing showed that there are programs which no other program can analyse and determine if they will ever halt!

This simple example implements the instruction table as a list of lists of tuples. The outermost list is states, the innermost is symbols ─ and the tuples are (**symbol** to write, **direction** to move tape head, next **state**)

**Visualise execution step-by-step**

The example above only solves one problem, namely adding 2 numbers in unary notation. The numbers themselves are provided on the ‘tape’ and so at least we can use the machine to solve an infinite number of additions. But the *program* is specific to this machine! Suppose I want the machine to compute something other adding unary numbers. All I need to do is change *prog* – so it must be universal! **No**. This is a simulation of an (imaginary) mechanical device, changing *prog* would effectively require repatching cables or whatever, which is a different machine. The Universal Turing Machine however is a fixed machine, which accepts the program of another TM on the tape – followed by any data. Changing *prog* is tantamount to using the underlying compiler or interpreter (plus hardware) as the UTM.

- Turing Machines, on Tuxar.uk
- Picture of a fanciful mechanical TM from Wikipedia user WVBailey
- The Annotated Turing, by Charles Petzold. Probably my favourite book.
- On computable numbers, with an application to the Entscheidungsproblem (PDF, Journal website)
- ON COMPUTABLE NUMBERS, WITH AN APPLICATION TO THE ENTSCHEIDUNGSPROBLEM By A. M. TURING (text)
- Extract, ‘On computable numbers, with an application to the Entscheidungsproblem’ fromProceedings of the London Mathematical Society, (Ser. 2, Vol. 42, 1937); and extract ‘On Computable Numbers, with an Application to the Entscheidungsproblem. A correction.’ FromProceedings of the London Mathematical Society, (Ser. 2, Vol. 43, 1937). Turing Digital Archive
- Information the measure of all things Part 1: Communication codes and- computation “The problem with a Turing machine is that a new one needs to be built whenever a new computation is to be performed. But Turing proved that a modified version of this deceptively simple theoretical machine — now known as the Universal Turing machine — could perform all possible computations. The way he established this was to show that you could encode the instruction table, the input, and the output of any other Turing machine onto the Universal Turing machine’s tape. Turing proved that the Universal Turing machine could perform all possible computations.

A **Turing machine** is a mathematical model of computation that defines an abstract machine, which manipulates symbols on a strip of tape according to a table of rules. Despite the model's simplicity, given any computer algorithm, a Turing machine capable of simulating that algorithm's logic can be constructed.

The machine operates on an infinite memory tape divided into discrete *cells*. The machine positions its *head* over a cell and "reads" (scans) the symbol there. Then, as per the symbol and its present place in a *finite table* of user-specified instructions, the machine (i) writes a symbol (e.g., a digit or a letter from a finite alphabet) in the cell (some models allowing symbol erasure or no writing), then (ii) either moves the tape one cell left or right (some models allow no motion, some models move the head), then (iii) (as determined by the observed symbol and the machine's place in the table) either proceeds to a subsequent instruction or halts the computation.

The Turing machine was invented in 1936 by Alan Turing, who called it an *a-machine* (automatic machine). With this model, Turing was able to answer two questions in the negative: (1) Does a machine exist that can determine whether any arbitrary machine on its tape is "circular" (e.g., freezes, or fails to continue its computational task); similarly, (2) does a machine exist that can determine whether any arbitrary machine on its tape ever prints a given symbol. Thus by providing a mathematical description of a very simple device capable of arbitrary computations, he was able to prove properties of computation in general—and in particular, the uncomputability of the Entscheidungsproblem ("decision problem").

Thus, Turing machines prove fundamental limitations on the power of mechanical computation. While they can express arbitrary computations, their minimalistic design makes them unsuitable for computation in practice: real-world computers are based on different designs that, unlike Turing machines, use random-access memory.

Turing completeness is the ability for a system of instructions to simulate a Turing machine. A programming language that is Turing complete is theoretically capable of expressing all tasks accomplishable by computers; nearly all programming languages are Turing complete if the limitations of finite memory are ignored.

AI assignment bit operations boolean chr color colorsys complex conditionals cos data types def dict eval events float for fractal function graphics HSV import input libraries list loop math matplotlib modulo not numpy pillow print pyaudio pygame random range recursion RGB search simulation sin tuple turtle while