[This article covers the origins of Alan Turing and his concepts and mathematical contributions to the field of Computer Science. It should be noted that I’ve tried as well as I can to put Turing’s concepts in the most basic and straightforward way possible. This was difficult, at best. So, I would like to say that, for further clarifications of Turing’s concepts, the reader is encouraged to do continued research as needed.]
Can a mathematical problem be proven as true or false? That is, if a statement can be represented in mathematical terms, can it be proven as true or false through a series of mathematical problems?
This was the problem that Alan Turing puzzled over. To understand why he puzzled over something like this, it may help to understand where he was from and what he was like.
Alan had been born in 1912 in London. Alan’s genius level intellect was noted at a very early age. He was said to have taught himself to read in a matter of weeks. Dedicated to his studies, at one point he was also said to have ridden many miles on his bicycle just to be able to attend school. Even though he was a true mathematical genius, he was not always accepted, even within intellectual circles.
For example, the predominate public schooling during his time focused on the classics and literature. Having very little interest in said classics, Turing preferred to focus on mathematics. This put him at odds with his professors at the time.
Despite his lack of love for literature, Alan Turing’s love of math kept him as being one of the more promising mathematicians of the time. For example, at age 16 Turing read and devoured Einstein’s work. Not only that, but he was able to expand upon some of Einstein’s concepts.
In the early 1930’s Alan Turing began to tackle Entscheidungsproblem, the German term for “decision problem.” Can a problem be proven as true or false? To be able to answer this question, the “problem” had to be presented in mathematical terms. Also, the procedure for processing the problem had to be presented in a mathematical format, or algorithm.
An algorithm is basically a series of steps used to solve something that has a distinct beginning and a distinct end solution.
It can be said that algorithms, many times, are quite tedious for humans to compute. Alan came up with the concept of a “Turing Machine” that could aid in the processing of algorithms.
In other words, to solve whether or not a problem can be proven as true or false, Turing came up with the idea of a “Turing Machine” that, given the correct procedure, could work through a series of steps (algorithms) to come up with mathematical conclusions.
Alan Turing further expanded his concept of a problem solving “device” with the “Universal Turing Machine.” The idea was that a Universal Turing Machine would be able to take the processes of other Turing machines and compute them, given the correct set of algorithms.
Turing never actually fully built a Turing machine, but was clearly integral in its creation. He laid out detailed plans that led later to the machine’s creation. Turing machines, in their essentially original form, are still used today for problem solving computations.
In 1936, Alan Turing published his paper, “On Computable Numbers, with an Application to the Entscheidungsproblem.” In this paper he proved that a given problem could not be proven true or false through algorithmic means.
But in this case, the procedure for solving problems is significant. Turing’s ideas of how to solve problems are what lead to the creation of the modern day computer.
Even after his work with cryptography during World War II, Alan Turing continued his work in the soon-to-be-labeled field of Computer Science. From 1945 to 1947 Turing worked at the National Physical Laboratory where he worked on the design of the Automatic Computing Engine (ACE). And in February of 1946, he came up with the first complete design of the stored-program computer. Even further, in 1949 Alan Turing worked on software for one of the earliest true computers: the Manchester Mark I.
Even after his death in 1954, Alan Turing’s legacy lives on. Remember Alan Turing every time you turn your computer on or, in other words, your advanced-Universal-Turing-machine.
Labels: Alan Turing and the Origin of Computers