Alan Turing's Contributions to Computer Science

Question

Alan Turing, one of the pioneers of (theoretical) computer science, made many seminal scientific contributions to our field, including defining Turing machines, the Church-Turing thesis, undecidability, and the Turing test. However, his important discoveries are not limited to the ones I listed.

In honor of his 100th Birthday, I thought it would be nice to ask for a more complete list of his important contributions to computer science, in order to have a better appreciation of his work.

So, what are Alan Turing's important/influential contributions to computer science?

Answer 1

This question is a lot like asking for Newton's contributions to physics, or Darwin's to biology! However, there's an interesting aspect to the question that many commenters have already seized on: namely that, besides the enormous contributions that everyone knows, there are plenty of smaller contributions that most people don't know about --- as well as many insights that we think of as more "modern," but that Turing demonstrated in various remarks that he understood perfectly well. (Incidentally, the same is true of Newton and Darwin.)

A few examples I like (besides the ones mentioned earlier):

In "Computing Machinery and Intelligence," Turing includes a quite-modern discussion of the benefits of randomized algorithms:

It is probably wise to include a random element in a learning machine. A random element is rather useful when we are searching for a solution of some problem. Suppose for instance we wanted to find a number between 50 and 200 which was equal to the square of the sum of its digits, we might start at 51 then try 52 and go on until we got a number that worked. Alternatively we might choose numbers at random until we got a good one. This method has the advantage that it is unnecessary to keep track of the values that have been tried, but the disadvantage that one may try the same one twice, but this is not very important if there are several solutions. The systematic method has the disadvantage that there may be an enormous block without any solutions in the region which has to be investigated first, Now the learning process may be regarded as a search for a form of behaviour which will satisfy the teacher (or some other criterion). Since there is probably a very large number of satisfactory solutions the random method seems to be better than the systematic. It should be noticed that it is used in the analogous process of evolution.

Turing was also apparently the first person to use a digital computer to search for counterexamples to the Riemann Hypothesis -- see here.

Besides the technical results from Turing's 1939 PhD thesis (mentioned by Lev Reyzin), that thesis is extremely notable for introducing the concepts of oracles and relativization into computability theory. (Some people might wish Turing had never done that, but I'm not one of them! :-D )

Finally, while this is basic, it seems no one has yet mentioned the proof of the existence of universal Turing machines --- that's a distinct contribution from defining the Turing machine model, formulating the Church-Turing Thesis, or proving the unsolvability of the Entscheidungsproblem, yet arguably the most "directly" relevant of any of them to the course of the computer revolution.

Answer 2

I did not know of these until recently.

1) The LU decomposition of a matrix is due to Turing! Considering how fundamental LU decomposition is, this is one contribution that deserves to be highlighted and known more widely (1948).

2) Turing was the first to come up with a "paper algorithm" for chess. At that point, the first digital computers were still being built (1952).

Chess programming has had an illustrious set of people associated with it, with Shannon, Turing, Herb Simon, Ken Thompson, etc. The last two won the Turing Award. And Simom, of course, won the Nobel as well. (Shannon came up with a way to evaluate a chess position in 1948.)

Answer 3

As mentioned in the question, Turing was central to defining algorithms and computability, thus he was one of the people that helped assemble the algorithmic lens. However, I think his biggest contribution was viewing science through the algorithmic lens and not just computation for the sake of computation.

During WW2 Turing used the idea of computation and electro-mechanical (as opposed to human) computers to help create the Turing–Welchman bombe and other tools and formal techniques for doing crypto-analysis. He started the transformation of cryptology, the art-form, to cryptography, the science, that Claude Shannon completed. Alan Turing viewed cryptology through algorithmic lenses.

In 1948, Turing followed his interested in the brain, to create the first learning artificial neural network. Unfortunately his manuscript was rejected by the director of the NPL and not published (until 1967). However, it predated both Hebbian learning (1949) and Rosenblatt's perceptrons (1957) that we typically associated with being the first neural networks. Turing foresaw the foundation of connectionism (still a huge paradigm in cognitive science) and computational neuroscience. Alan Turing viewed the brain through algorithmic lenses.

In 1950, Turing published his famous Computing machinery and intelligence and launched AI. This had a transformative effect on Psychology and Cognitive Science which continue to view the cognition as computation on internal representations. Alan Turing viewed the mind through algorithmic lenses.

Finally in 1952 (as @vzn mentioned) Turing published The Chemical Basis of Morphogenesis. This has become his most cited work. In it, he asked (and started to answer) the question: how does a spherically symmetric embryo develop into a non-spherically symmetric organism under the action of symmetry-preserving chemical diffusion of morphogens? His approach in this paper was very physics-y, but some of the approach did have an air of TCS; His paper made rigorous qualitative statements (valid for various constants and parameters) instead of quantitative statements based on specific (in some fields: potentially impossible to measure) constants and parameters. Shortly before his death, he was continuing this study by working on the basic ideas of what was to become artificial life simulations, and a more discrete and non-differential-equation treatment of biology. In a blog post I speculate on how he would develop biology if he had more time. Alan Turing started to view biology through algorithmic lenses.

I think Turing's greatest (and often ignored) contribution to computer science was showing that we can glean great insight by viewing science through the algorithmic lens. I can only hope that we honour his genious by continuing his work.

---

Related questions

• Algorithmic lens in the social sciences

• Modern treatments of Alan Turing's B-type neural networks

• Impact of Alan Turing's approach to morphogenesis

Answer 4

One lesser-known contribution is the Good-Turing estimator for estimating the fraction of a population "not yet seen" when taking samples. This is used in biodiversity.

Answer 5

Turing's paper on Checking a large routine which was presented at a conference in Cambridge in 1949 antedates formal reasoning about programs as developed by Floyd and Hoare by nearly two decades. The paper is only three pages long and contains the idea of using invariants to prove properties of programs and well-foundedness to prove termination.

How can one check a routine in the sense of making sure it is right?

In order that the man who checks should not have too difficult a task, the programmer should make a number of definite assertions which can be checked individually, and from which the correctness of the whole program easily follows.

Answer 6

Turing was interested in and did some seminal work in chemical reaction-diffusion patterns. this area of research has expanded substantially since he started investigating it. it has been shown to have ties to computability eg is in a sense "Turing complete" [1]. the chemical reactions can be modeled with complex nonlinear differential equations so in a sense it has been shown that nonlinear differential equations with enough complexity can simulate Turing machines. stemming from his 1951 paper "chemical basis of morphogenesis" [4]

[1] chemical kinetics is Turing universal by Magnasco in PRL 97

[2] Turing structures in simple chemical reactions

[3] Turing patterns in linear chemical reaction systems with nonlinear cross diffusion by Franz

[4] chemical basis of morphogenesis, wikipedia

Answer 7

Here's another one I found on Scott Aaronson's blog (and the Q+A is taken from there):

In his Ph.D. thesis, Turing studied the question ($F_α$ is a theory):

Given a Turing machine $M$ that runs forever, is there always an ordinal α such that $F_α$ proves that $M$ runs forever?

Turing proved:

Given any Turing machine $M$ that runs forever, there is an encoding of its axioms ($F_{\omega+1}$) that proves that $M$ runs forever.

Unfortunately, the definitions & technical details are harder to summarize, but the linked-to blog post does a good job of explaining them.

Answer 8

here is a broad, highly researched/detailed 9p online survey/retrospective of Turing's specific and more general/longrange contributions in the Notices of the American Mathematical Society by SB Cooper for the 100th anniversary, Incomputability after Alan Turing. some other contributions mentioned in this survey:

• Rounding-off errors in matrix processes paper, 1948. influential in numerical analysis and scientific computation in the theory of computation

• unpublished 1948 National Physical Laboratory report Intelligent Machinery describes an early connectionist model, similar and contemporaneous with the famous McCulloch and Pitts neural nets.

• points out Turing's analysis and theory of morphogenesis can be regarded as the early intellectual foundation of massive (and still ongoing/active) later theory in self-organization and emergent phenomena.

(etc)