Alan Turing

The father of computer science

by Christopher Neal

Christopher Neal is a PhD candidate at Polytechnique School of Montreal in Computer Science.

Christopher Neal is a PhD candidate at Polytechnique School of Montreal in Computer Science.

Imagine if you had a strip of tape that was infinitely long. What could you do with that?

Alan Turing was able to take this simple mechanism and mathematically prove one the most fundamental concepts of computer science.

Alan Turing was born in London, England in 1912 and from an early age he showed great promise in Mathematics and Sciences.  He finished undergraduate studies at King’s College, Cambrige in 1934 and in 1935 was elected as a fellow to the university based on the strength of his dissertation.

Alan Turing

Alan Turing

In 1936 at the age of 24 Alan Turing published a paper entitled “On Computable Numbers, with an Application to the Entscheidungsproblem” (or the decision problem), in which he shows that any mathematical computation conceivable can be performed if it is represented as an algorithm. Informally we can think of an algorithm as “a set of rules that precisely defines a sequence of operations.” Turing’s breakthrough was important in that it not only showed what was computable but also what was not computable. It showed that the Entscheidungsproblem which was an important open question posed in 1928 by David Hilbert was impossible.

He did this by constructing an imaginary device which is now known as a Turing Machine. Its main characteristic is that it has a tape that can be infinitely long and is divided into cells. Each cell in the tape “has a symbol from a finite alphabet” or a blank symbol.

Its other components include a head which can travel along the tape and can read and write symbols onto the tape. There is state register which keeps track of the current state of the machine, from a finite number of states. And lastly there is a finite table which hold a list of instructions for the machine. Given the current state of the machine and the current symbol being read by the head the machine can do one of the following; Erase a symbol, write a symbol, move the head, or assume a new state.

For example: In state 5, if the symbol is 0 write 1; In state 1 if the symbol is a star, move to the right; In state 0 if the symbol is 1 go into state 1; and so on…

So, there is a single Universal Turing Machine that can solve any problem as long that it is given the proper instructions. This is the principle of a ‘stored program’ which is fundamental to how current computers operate. A computer can perform the tasks that are provided by a program.

This achievement gained Alan Turing notoriety in the mathematics community and when World War Two broke he was hired to work at Britain’s codebreaking centre know as Bletchley Park. He was a member of a team which was tasked of breaking German codes through cryptanalysis. These events of this time has been described in popular motion picture entitled “The Imitation Game” (2014). He played a critical role in constructing a device, which can be considered as one of the first computers, which helped decipher German messages which were used to coordinate attacks against Allied shipping vessels. One source estimates that Turing’s work shortened the war in Europe by 2 years, saving over 14 million lives.

After World War Two he worked on creating electronic stored program computers, he taught university, and continued to develop scientific papers in many diverse fields. He envisioned computers being more than machines to solely compute tasks that humans provided. He saw them as entities that could switch between performing numerical work, playing chess, handling files, and writing music. He started designing a machine that he called ‘The Brain’ and proposed the idea of the Turing Test to measure the effectiveness of Artificial Intelligence.

These later advancements he proposed to computational theory seemed like fantasy at the time,  however improved computational methods are bringing us closer to this reality everyday. The future of computation, including the computational power we keep in our pocket as a smartphone can all be attributed to Alan Turing’s simple idea which was the construction of an imaginary machine using a roll of tape. Showing that anything can be accomplished if we using our imagination.