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.
