I should note that the content of this post is largely stolen from answers to a question I asked on the StackExchange (SE) cstheory site, where I sought to gather a compendium of Turing's less known results. The answers made a collection of impressive contributions, some of which I wasn't familiar with. Some of his contributions turned out to be surprisingly modern. They also introduced us to viewing the world through an algorithmic lens.
Without further ado, here they are:
1. Defining Turing Machines and Showing the Existence of UTMs (1936): A Turing machine is a universal computing device that forms the basis of how we think about computing. A Universal Turing machine is a fixed machine that can simulate any other Turing machine -- most relevant to our current computers. (SE link)
a Lego Turing Machine, photo from wikipedia
2. The Church-Turing Thesis (1939): The idea that the Turing Machine (and Lambda calculus) captures all of computation, and is therefore worth studying. This hypothesis cannot be proven, but everyone believes it nonetheless. (wiki link)
3. Solving the Entscheidungsproblem (1936): Turing solved Hilbert's "decision problem" by showing that deciding whether a program will halt is not possible in general. (wiki link)
4. The Turing Test and Introducing AI (1950): Turing gave an objective test that decides whether a computer exhibits intelligence. The idea is to say that a computer is intelligent if it can fool humans into thinking it is also human. Accepting this idea is a way to avoid many philosophical arguments about the nature of intelligence. (wiki link)
5. Introducing Oracles and Relativization into Computability Theory (1939): Oracles are incredibly useful for all sorts of analysis -- for example the famous Baker-Gill-Solovay result that says P vs NP cannot be separated any technique that relativizes (holds for relative to any oracle), eg diagnolization. It was part of the paper "Computing machinery and intelligence" that launched AI. (SE link)
6. The Bombe (1950): Also called the Turing-Welchman Bombe, for breaking the German enigma machine in WW2 and introducing tools to cryptanalysis. (SE link)
the Bombe, from http://www.uh.edu/engines/epi2666.htm
7. Randomized Algorithms (1950): Turing observed the potential advantage an algorithm can gain from having access to randomness. (SE link)
8. The First Artificial Neural Network (1948): This idea is an important one in AI and machine learning. Turing's design predated Rosenblatt's preceptron. (SE link)
9. The Chemical Basis of Morphogenisis (1952): In his most cited paper, he began to tackle the question of how a symmetric embryo develops into an assymetric organism using symmetry perserving chemical reactions. This started to introduce algorithmic thinking into biology. (SE link)
10. Good-Turing Estimator (1953): For estimating an unseen fraction on a population when given past data. (SE link)
11. One of the First Chess Algorithms (1952): Before we had computers, we had paper chess algorithms. (SE link)
Deep Blue, photo form wikipedia
12. Checking a Large Routine (1949): The idea of using invariants to prove properties of programs and "well-foundedness" to prove termination. (SE link)
13. LU-Decomposition (1947): A method for factorizing a matrix as the product of a lower triangular matrix and an upper triangular matrix. Now commonly studied in Linear Algebra. (SE link)
14. Turing's Method for Computational Analysis of a Function (1943): Invented for studying the of the Riemann zeta-function but is more widely applied. (SE link)
I'm sure there are more. Any one of these is an impressive achievement for a scientist -- the first couple are revolutionary. That Turing did all of these and more shows his remarkable contributions to our field.
Update (12/31/12): Alan Richmond points out another important work of Turing's, which I added as # 14. Also, my wording for the Turing test proved a bit controversial, so I've changed it to better reflect reality.
Turing’s Zeta Machine & the Riemann Hypothesis (http://turingos.org/turing-timeline/turings-zeta-machine-the-riemann-hypothesis/)
ReplyDeleteIn June 1950 he used the prototype Manchester University Electronic Computer to do some calculations concerned with the distribution of the zeros of the Riemann zeta-function, specifically whether there are any zeros not on the critical line in certain intervals. The pre-war record for the number of zeros located on the line was held by Ted Titchmarsh, confirming that the first 1041 points were OK. Turing extended this to the first 1104 zeros but then, unfortunately, the computer broke down. He devised what is now called “Turing’s method” for easier computational analysis of the function, detailed in his papers “A method for the calculation of the zeta-function” and “Some calculations of the Riemann zeta-function,” which are both widely referenced in modern mathematical publications.
Thanks -- I was aware of his work on the Riemann Hypothesis but didn't think it important enough to include on the list. However, I hadn't realized the method was more widely used, so I'll add it as # 14.
ReplyDeleteRH is solved and done .
ReplyDeleteOne needs to be cautious in taking a piecemeal approach to Turing's work, there is an overarching vision and mathematical agenda giving a cohesive form to Turing's career, which is still alive for us now.
ReplyDeleteA comment on Baker-Gill-Solovay: Many mathematicians and computer scientists have become aware over the years that not all computability and complexity theoretic arguments are relativizable. What Baker-Gill-Solovay point to is the fact that certain simple diagonalising techniques do relativize, so pointing to the necessity for something more subtle from the theorist's tool bag.