Yesterday (June 23), would have been the 100th birthday of Alan Turing, the mathematician who was one of the founders of modern computer science – indeed he is often considered to be the “father of computer science.”

In the 1920s and 1930s, much attention in the mathematics was on the subject of “computable numbers” and finding automatic systems for proving mathematical statements.   Based on a series of problems stated by David Hilbert, the mathematician Kurt Gödel ultimately proved that this not possible.  Essentially, there is no formal mathematical system that can decide the truth or falsehood of all mathematical statements.   This is quite profound and simple to state, but Gödel’s mathematics is cryptic and at some times impenetrable.   By contrast, Alan Turing’s formulation of the mathematics as a simple device is quite accessible and laid the groundwork for the positive use of Gödel’s results.  Sure, we cannot solve all mathematical problems computationally, but we can do quite a lot with the right tools.  The Turing Machine is one of the simpler of such tools.

A Turing Machine consists of a tape, or an infinite sequence of cells, each of which contains a symbol that can be read or written.  There is a head, which (much like the head on a tape recorder) moves along the tape and is always positioned at one cell.  The state register contains one or more states of the machine.  Finally, the transition table contains a series of instructions of the form q_ia_j→q_i1a_j1d_k where q is a state, a is a symbol, and d is a number of cells to move the head left or right along the tape (including not moving it at all).  So, if the machine is at a given state q_i and the head is over a symbol a_j, switch to state q_i1, write the symbol a_j1 at the head, and move the head d_k positions to the left or right.

The description of the Turing Machine is very mechanical, which makes it a bit easier to understand.  But it is nonetheless a formal mathematical model.  It was used to demonstrate that the “halting problem”, the ability of such a machine to determine if any set of states and transitions will stop or repeat forever, is not solvable.  This remains today, one of the great unsolvable problems in computer science.

About the same time as Turing published his results, American mathematician Alonzo Church published an equivalent result using lambda calculus, a system I personally find more intuitive and elegant because of its basis in functions and algebraic-like expressions (it will be the subject of a future article).  But Turing’s work has been more prominent both in mainstream computer science and in the culture at large, with computer designs and languages being described as “Turing complete”.  And then there is the “Turing Test” for evaluating artificial intelligence systems.  So far, no system has ever passed the test.

During this centennial, especially coming as it does during Pride Weekend in much of the United States, there has been much written about Turing’s homosexuality and his being convicted for homosexual activity that was then illegal in the UK and stripped of his security clearance.  This is a very sad statement on the time in which he lived, that someone who was both one of the most influential mathematicians in a growing field of computation and a hero of World War II for is code-breaking exploits was treated in such a mean and undignified way.  There was also much written about the mysterious circumstances of his death – long considered a suicide, a recent BBC article on the centennial suggests otherwise.  You can read for yourself here.  As for us at CatSynth, we prefer to focus on his achievements.

Google honored Turing yesterday with one of their trademark “Google Doodles” in which they implemented a functioning Turing Machine.