-1
$\begingroup$

What is the importance of Alan Turing? What were his inventions or innovations and why are they so influential?

$\endgroup$
2
  • 2
    $\begingroup$ What research have you done? Did you read the Wikipedia article? If your question is already answered by Wikipedia, your question is not a good fit for this site. Also, this site is for technical questions about computer science. $\endgroup$
    – D.W.
    Jun 26, 2014 at 3:07
  • 1
    $\begingroup$ lol you didnt ask in the magic right way, this other similar question Alan Turing's Contributions to Computer Science got 31v on Theoretical Computer Science. drop by Computer Science Chat for more discussion $\endgroup$
    – vzn
    May 19, 2015 at 18:10

1 Answer 1

8
$\begingroup$

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.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.