What is the importance of Alan Turing? What were his inventions or innovations and why are they so influential?
closed as off-topic by D.W.♦, Kyle Jones, FrankW, David Richerby, Wandering Logic Jun 26 '14 at 12:03
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question does not appear to be about computer science, within the scope defined in the help center." – D.W., Kyle Jones, FrankW
He laid down the foundations to understanding "computing" from a mathematical perspective. His paper about what is today called the Turing Machine shows his reflections on a model, in mathematical terms, of how the human_brain/thought_process works.
Based on that, he develop a theory of computation (with the aim of automating math thinking; kind of similar to previous work done until his days based on formal methods, i.e. logic) and found very interesting "phenomena":
He described what is now called a Universal Turing Machine, i.e. that it is possible to develop a machine where the workings of any other machine could be simulated. In today's terms, he discovered computers were possible (i.e. a universal programmable machine).
Then he solved, in the negative, the halting problem: the impossibility of writing an algorithm (in Turing Machine language) to determine whether a given program is going to stop or not.
This later result, if you think about it, is kind of similar to Gödel's incompleteness result in logic: say you have a machine that given a first-order logic formula $P(x)$ for natural numbers, starts from 0 and stops where it finds a number $n$ where $P(n)=0$, i.e. false. If we had a halting machine, then it is possible to determine the truth of $\forall n P(n)$ for all formulas $P$ by simply running our halting machine with that iterating machine with input $P$; this contradicts Gödel's result.
The interesting part is that Turing's proof is actually quite simple. So, if you think that Turing truly captured the nature of the human thought, then this result is even more fundamental!
Also, his theory laid the foundation to explore a related problem, measuring/modelling computing time and memory consumption; nowadays called complexity theory.
You also want to know that there were similar theories around his time: von Neumann's register machines and Church's lambda calculus (all of them later proved to be equivalent). Interestingly enough, although modern computers are based on von Neumann's model, Turing's theory was the preferred (as far as I remember) method to study algorithms and complexity, and is still used today as reference model for the still open Millenium's P vs NP problem, which has an unclaimed prize tag of one million dollars!
Hope the above complements good enough what you can already find in wikipedia.