<p>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 <strong>viewing science through the algorithmic lens</strong> and not just computation for the sake of computation.</p>
<p>During WW2 Turing used the idea of computation and electro-mechanical (as opposed to human) computers to help create the <a href="http://en.wikipedia.org/wiki/Bombe" rel="noreferrer">Turing–Welchman bombe</a> 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. <strong>Alan Turing viewed cryptology through algorithmic lenses.</strong></p>
<p>In 1948, Turing followed his interested in the brain, to create the <a href="https://cogsci.stackexchange.com/q/1263/29">first learning artificial neural network</a>. 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. <strong>Alan Turing viewed the brain through algorithmic lenses.</strong></p>
<p>In 1950, Turing published his famous <em>Computing machinery and intelligence</em> and launched AI. This had a transformative effect on Psychology and Cognitive Science which continue to view the cognition as computation on internal representations. <strong>Alan Turing viewed the mind through algorithmic lenses.</strong></p>
<p>Finally in 1952 (as @vzn mentioned) Turing published <em>The Chemical Basis of Morphogenesis</em>. 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 <a href="http://egtheory.wordpress.com/2012/06/23/turing-biolog/" rel="noreferrer">I speculate on how he would develop biology</a> if he had more time. <strong>Alan Turing started to view biology through algorithmic lenses.</strong></p>
<p>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.</p>
<hr />
<h3>Related questions</h3>
<ul>
<li><p><a href="https://cstheory.stackexchange.com/q/6387/1037">Algorithmic lens in the social sciences</a></p>
</li>
<li><p><a href="https://cogsci.stackexchange.com/q/1263/29">Modern treatments of Alan Turing's B-type neural networks</a></p>
</li>
<li><p><a href="https://biology.stackexchange.com/q/2739/500">Impact of Alan Turing's approach to morphogenesis</a></p>
</li>
</ul>

CC BY-SA 3.0
2012-06-24T17:56:45.220Z
2012-06-24T18:02:19.613Z
2020-06-17T09:38:08.363Z
Artem Kaznatcheev
<p>I did not know of these until recently.</p>

<p>1) The <a href="http://qjmam.oxfordjournals.org/content/1/1/287.full.pdf">LU decomposition</a> 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).</p>

<p>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). </p>

<p>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.)</p>

CC BY-SA 3.0
2012-06-25T02:59:06.407Z
I didn't know about the LU decomposition result. That's cool ! Is there a reference ?
Suresh Venkat
CC BY-SA 3.0
2012-06-25T09:21:37.020Z
Suresh, I have added the reference to LU decomposition.
V Vinay
CC BY-SA 3.0
2012-06-25T11:15:37.070Z
It is not true that Turing wrote the first chess program, this honor seems to go to [Konrad Zuse](http://en.wikipedia.org/wiki/Konrad_Zuse), the inventor of the first computer. He wrote a simple chess program 'on paper' as a benchmark for his [Plankalkuel](http://en.wikipedia.org/wiki/Plankalk%C3%BCl), the first high-level programming language. See [here](http://www.zib.de/zuse/Inhalt/Programme/Plankalkuel/Chess/chess.htm) and [here](http://de.wikipedia.org/wiki/Schachprogramm). Sorry, no good english language descriptions of this work seem to exist.
Martin Berger
CC BY-SA 3.0
2012-06-24T18:19:59.290Z
2012-06-25T09:19:37.100Z
2012-06-25T09:19:37.100Z
V Vinay
<p>One lesser-known contribution is the <a href="http://johncarlosbaez.wordpress.com/2012/06/21/the-mathematics-of-biodiversity-part-1/">Good-Turing estimator</a> for estimating the fraction of a population "not yet seen" when taking samples. This is used in biodiversity. </p>

CC BY-SA 3.0
2012-06-24T04:39:09.520Z
2012-06-24T04:39:09.520Z
Suresh Venkat
<p>Turing's paper on <a href="http://www.turingarchive.org/browse.php/B/8" rel="noreferrer">Checking a large routine</a> 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.</p>
<blockquote>
<p>How can one check a routine in the sense of making sure it is right?</p>
<p>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.</p>
</blockquote>

CC BY-SA 3.0
2012-06-26T23:53:11.733Z
So Turing invented unit testing :)
Lev Reyzin
CC BY-SA 3.0
2012-06-27T18:50:07.807Z
Not in that paper. He is presenting a static method to prove functional correctness and termination.
Vijay D
CC BY-SA 3.0
2012-06-26T21:35:44.763Z
2012-06-26T21:35:44.763Z
2020-06-17T09:38:08.363Z
Vijay D
<p>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]</p>

<p>[1] <a href="http://asterion.rockefeller.edu/marcelo/Reprints/16chemturing.pdf">chemical kinetics is Turing universal</a> by Magnasco in PRL 97</p>

<p>[2] <a href="http://pubs.acs.org/doi/abs/10.1021/ar00029a002">Turing structures in simple chemical reactions</a></p>

<p>[3] <a href="https://www.uleth.ca/dspace/handle/10133/659">Turing patterns in linear chemical reaction systems with nonlinear cross diffusion</a> by Franz</p>

<p>[4] <a href="http://en.wikipedia.org/wiki/The_Chemical_Basis_of_Morphogenesis">chemical basis of morphogenesis, wikipedia</a></p>

CC BY-SA 3.0
2012-06-24T14:41:52.513Z
2012-06-24T14:41:52.513Z
vzn
<p>Here's another one I found on <a href="http://www.scottaaronson.com/blog/?p=697">Scott Aaronson's blog</a> (and the Q+A is taken from there):</p>

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

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

<p>Turing proved:</p>

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

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

CC BY-SA 3.0
2012-12-26T17:24:32.617Z
2012-12-26T17:24:32.617Z
Lev Reyzin
<p>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, <a href="http://www.ams.org/notices/201206/rtx120600776p.pdf" rel="nofollow">Incomputability after
Alan Turing</a>. some other contributions mentioned in this survey:</p>

<ul>
<li><p><em>Rounding-off errors in matrix processes</em> paper, 1948. influential in numerical
analysis and scientific computation in the theory of computation</p></li>
<li><p>unpublished 1948 National Physical Laboratory report
<em>Intelligent Machinery</em> describes an early <a href="http://en.wikipedia.org/wiki/Connectionism" rel="nofollow">connectionist</a> model, similar and contemporaneous with the famous <a href="http://en.wikipedia.org/wiki/McCulloch%E2%80%93Pitts_neuron" rel="nofollow">McCulloch and Pitts neural nets</a>. </p></li>
<li><p>points out Turing's analysis and theory of <a href="http://en.wikipedia.org/wiki/Morphogenesis" rel="nofollow">morphogenesis</a> can be regarded as the early intellectual foundation of massive (and still ongoing/active) later theory in <a href="http://en.wikipedia.org/wiki/Self-organization" rel="nofollow">self-organization</a> and <a href="http://en.wikipedia.org/wiki/Emergence" rel="nofollow">emergent phenomena</a>. </p></li>
</ul>

<p>(etc)</p>

CC BY-SA 3.0
2013-05-02T22:20:40.777Z
just noticed Cooper & Leeuwen have a comprehensive new book: [_Alan Turing: His Work and Impact_](http://www.amazon.com/Alan-Turing-His-Work-Impact/dp/0123869803)
vzn
CC BY-SA 3.0
2013-03-05T22:54:46.980Z
2013-03-05T22:54:46.980Z
vzn
<p>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 <i>don't</i> 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.)</p>

<p>A few examples I like (besides the ones mentioned earlier):</p>

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

<ul>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.</ul>

<p>Turing was also apparently the first person to use a digital computer to search for counterexamples to the Riemann Hypothesis -- <a href="http://www.ams.org/notices/200610/fea-booker.pdf">see here</a>.</p>

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

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

CC BY-SA 3.0
2012-12-26T17:56:57.610Z
2012-12-26T17:56:57.610Z
Scott Aaronson
<p><a href="http://en.wikipedia.org/wiki/Alan_Turing">Alan Turing</a>, 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.</p>

<p>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.</p>

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

CC BY-SA 3.0
2012-06-24T14:29:26.133Z
would like some Q like this but this forum, seems appropos on one level but is ironically not the best place. the problem is that, inevitably, research level CS has vastly expanded/moved anywhere beyond what Turing studied in the decades since he contributed. therefore a Turing history related Q would have to be phrased very carefully to fit in here. already you have listed his major contributions in the question, so what is left to answer with? contributions not in the list? they would be somewhat obscure and not as important...
vzn
CC BY-SA 3.0
2012-06-24T14:53:17.413Z
see also this related q/a about [whether Turing machines influenced creation of later automata models in CS](http://cstheory.stackexchange.com/questions/10104/is-the-concept-of-the-turing-machine-derived-from-automata). the current highest rated answer by jeffe remarkably asserts that there was _not_ a historical connection, ie [later researchers who invented key CS automata models were verifiably _not_ directly inspired by Turing!](http://cstheory.stackexchange.com/a/10121/7884)
vzn
CC BY-SA 3.0
2012-06-24T15:00:15.080Z
related, [historical reasons for preeminence of TM model over alternatives](http://cstheory.stackexchange.com/questions/3650/historical-reasons-for-adoption-of-turing-machine-as-primary-model-of-computatio?rq=1)
vzn
CC BY-SA 3.0
2012-06-24T15:09:30.170Z
Thanks for the pointers.  Btw, I thought we had agreed that history of TCS is on topic for this site, hence the tag.  As for Turing's other contributions, perhaps some are still important, just not world-changing.
Lev Reyzin
<soft-question><ho.history-overview>
Alan Turing's Contributions to Computer Science
Lev Reyzin
# Alan Turing's Contributions to Computer Science

(Asked by: username_0 on 2012-06-24)

[Alan Turing](http://en.wikipedia.org/wiki/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?**

**Tags:** soft-question, ho.history-overview

> **Comments:**
> **username_1**: would like some Q like this but this forum, seems appropos on one level but is ironically not the best place. the problem is that, inevitably, research level CS has vastly expanded/moved anywhere beyond what Turing studied in the decades since he contributed. therefore a Turing history related Q would have to be phrased very carefully to fit in here. already you have listed his major contributions in the question, so what is left to answer with? contributions not in the list? they would be somewhat obscure and not as important...  
> **username_1**: see also this related q/a about [whether Turing machines influenced creation of later automata models in CS](http://cstheory.stackexchange.com/questions/10104/is-the-concept-of-the-turing-machine-derived-from-automata). the current highest rated answer by jeffe remarkably asserts that there was _not_ a historical connection, ie [later researchers who invented key CS automata models were verifiably _not_ directly inspired by Turing!](http://cstheory.stackexchange.com/a/10121/7884)  
> **username_1**: related, [historical reasons for preeminence of TM model over alternatives](http://cstheory.stackexchange.com/questions/3650/historical-reasons-for-adoption-of-turing-machine-as-primary-model-of-computatio?rq=1)  
> **username_0**: Thanks for the pointers.  Btw, I thought we had agreed that history of TCS is on topic for this site, hence the tag.  As for Turing's other contributions, perhaps some are still important, just not world-changing.  

---

## 8 answers

### Answer by username_7 on 2012-12-26. Score: 17 | Accepted answer

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](http://www.ams.org/notices/200610/fea-booker.pdf).

Besides the technical results from Turing's 1939 PhD thesis (mentioned by username_0), 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 by username_3 on 2012-06-24. Score: 27

I did not know of these until recently.

1) The [LU decomposition](http://qjmam.oxfordjournals.org/content/1/1/287.full.pdf) 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.)

> **Comments:**
> **username_4**: I didn't know about the LU decomposition result. That's cool ! Is there a reference ?  
> **username_3**: Suresh, I have added the reference to LU decomposition.  
> **username_5**: It is not true that Turing wrote the first chess program, this honor seems to go to [Konrad Zuse](http://en.wikipedia.org/wiki/Konrad_Zuse), the inventor of the first computer. He wrote a simple chess program 'on paper' as a benchmark for his [Plankalkuel](http://en.wikipedia.org/wiki/Plankalk%C3%BCl), the first high-level programming language. See [here](http://www.zib.de/zuse/Inhalt/Programme/Plankalkuel/Chess/chess.htm) and [here](http://de.wikipedia.org/wiki/Schachprogramm). Sorry, no good english language descriptions of this work seem to exist.  

---

### Answer by username_2 on 2012-06-24. Score: 22

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](http://en.wikipedia.org/wiki/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](https://cogsci.stackexchange.com/q/1263/29). 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 @username_1 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](http://egtheory.wordpress.com/2012/06/23/turing-biolog/) 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](https://cstheory.stackexchange.com/q/6387/1037)
* [Modern treatments of Alan Turing's B-type neural networks](https://cogsci.stackexchange.com/q/1263/29)
* [Impact of Alan Turing's approach to morphogenesis](https://biology.stackexchange.com/q/2739/500)


---

### Answer by username_4 on 2012-06-24. Score: 13

One lesser-known contribution is the [Good-Turing estimator](http://johncarlosbaez.wordpress.com/2012/06/21/the-mathematics-of-biodiversity-part-1/) for estimating the fraction of a population "not yet seen" when taking samples. This is used in biodiversity.


---

### Answer by username_6 on 2012-06-26. Score: 12

Turing's paper on [Checking a large routine](http://www.turingarchive.org/browse.php/B/8) 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.

> **Comments:**
> **username_0**: So Turing invented unit testing :)  
> **username_6**: Not in that paper. He is presenting a static method to prove functional correctness and termination.  

---

### Answer by username_1 on 2012-06-24. Score: 7

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](http://asterion.rockefeller.edu/marcelo/Reprints/16chemturing.pdf) by Magnasco in PRL 97

[2] [Turing structures in simple chemical reactions](http://pubs.acs.org/doi/abs/10.1021/ar00029a002)

[3] [Turing patterns in linear chemical reaction systems with nonlinear cross diffusion](https://www.uleth.ca/dspace/handle/10133/659) by Franz

[4] [chemical basis of morphogenesis, wikipedia](http://en.wikipedia.org/wiki/The_Chemical_Basis_of_Morphogenesis)


---

### Answer by username_0 on 2012-12-26. Score: 5

Here's another one I found on [username_7's blog](http://www.scottaaronson.com/blog/?p=697) (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 by username_1 on 2013-03-05. Score: 1

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](http://www.ams.org/notices/201206/rtx120600776p.pdf). 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](http://en.wikipedia.org/wiki/Connectionism) model, similar and contemporaneous with the famous [McCulloch and Pitts neural nets](http://en.wikipedia.org/wiki/McCulloch%E2%80%93Pitts_neuron).
* points out Turing's analysis and theory of [morphogenesis](http://en.wikipedia.org/wiki/Morphogenesis) can be regarded as the early intellectual foundation of massive (and still ongoing/active) later theory in [self-organization](http://en.wikipedia.org/wiki/Self-organization) and [emergent phenomena](http://en.wikipedia.org/wiki/Emergence).

(etc)

> **Comments:**
> **username_1**: just noticed Cooper & Leeuwen have a comprehensive new book: [_Alan Turing: His Work and Impact_](http://www.amazon.com/Alan-Turing-His-Work-Impact/dp/0123869803)  

---

