The anniversary of one of the greatest papers of all time
Alan Turing is Alan M. Turing is Alan Mathison Turing, OBE, FRS.
Today I wish to acknowledge that Turing’s famous paper is having its seventy-fifth anniversary.
The paper, “On Computable Numbers, with an Application to the Entscheidungsproblem,” was submitted to the Proceedings of the London Mathematical Society on May 28
1936, exactly seventy-five years ago. Like the sixtieth anniversary, the seventy-fifth is traditionally marked with diamonds.
Since 1917 congratulatory messages from the Monarch have been sent to those celebrating their 60th, 65th, and 70th wedding anniversaries, and every year after the 70th. Apparently the cards come with a special personal note from the Queen. They should also send cards to classic papers—perhaps this paper will get a card.
Turing had many other wonderful results, and I thought that on this great anniversary we might list some of the things named for Turing. See this for a discussion why so many things seem to be named “Gauss-X.” The following list proves that some were indeed named for others. Many of the things named for Turing are extremely important—the discovery of even one of these would have been enough to make one famous. Turing did them all.
Turing X
Here is a partial list of things named for Turing:
Turing Machine: This is the model of computation that is the best model of computation among all models of computation. That is pretty repetitive, but I wanted to make the point: Turing Machines are the model of computation. There are many alternative models: some based on string operations, some on registers, some based on various functional systems, and some on various types of logic. None seems as simple and natural as Turing’s model.
Turing Reduction: This is a relationship between computational problems. A problem 
is Turing reducible to 
provided there is an algorithm that can solve given as a subroutine. Emil Post first named the notion “Turing reducibility.”
Turing Degree: The notion of Turing reduction defines, in a natural way, an equivalence relation on sets of integers: two are equivalent if they are reducible to each other. This then defines what are called Turing Degrees. This also was named after Turing by Post.
The theory of degrees is one of the great areas of research in mathematics. The area has some amazing results, at least partially because the notion of what is computable relative to something else is very subtle. Turing proved, in terms of degrees, that there were two degrees: 
is used to denote those problems that can be computed and 
is those problems that are equivalent to the Halting Problem. Post, that’s Emil again, raised the beautiful question of was there anything between and ? The answer is yes, and the method of proof is called the priority method. This method has far-reaching consequences, and has been used in complexity theory by such experts as Harry Buhrman, Stephen Fenner, Lance Fortnow, and Leen Torenvliet in their paper.
The theory of degrees is still not completely understood, even though great progress has been made since Turing. In a sense our work on 
and 
is way below this theory. Almost always we are interested in problems that lie in the lowest degree . It reminds me of a quote by Stanislaw Ulam about combinatorics:
The infinite we shall do right away. The finite may take a little longer.
Turing Test: This is based on another famous idea of Turing. He defined his famous test, a test that could tell if a machine could fool a human. Today this idea is flipped around and used to detect machines or robots—this is the notion called CAPTCHA of Luis von Ahn, Manuel Blum, Nicholas Hopper, and John Langford.
Church-Turing Thesis: This states that all computable functions are computable by Turing machines. In modern complexity this has evolved in two directions. The major change is to try to define what is feasibly computable? Does polynomial time capture feasibility? or does one need to add randomness? or even add quantum operations? One of the major open problems in all of complexity theory is: Does quantum really add computational power?
Turing Switch: This is a type of boolean function that was invented by Jon Crowcroft, who named it after Turing. It acts as a kind of router—see the diagram below.
Good-Turing Estimation: This is a statistical method named after Turing and Irving Good. It concerns the estimation of the colors of balls in urns after sampling. Good was an assistant of Turing who went on to publish a paper that detailed the analysis of the method. Apparently it was used to help decode German ciphers during the war.
Among non-conceptual things, we have:
Alan Turing Way: This is a major road in Manchester, England, where he lived and worked in his last years. Information for a statue of Turing near the University of Manchester notes that a bridge on that road has also been named for him.
And finally:
Turing Award: This is, as we all know, the top award in Computer Science, and is often called the “Nobel Prize of Computer Science.” This years winner is Leslie Valiant, who is one of our own—a theorist. Of course Turing did not invent or discover this, but he no doubt would have won it had it been available when he was alive. Would have made a cool press headline: Alan Turing Wins Turing Award.
“Alan Turing Facts”?
There is an Internet phenomenon called Chuck Norris Facts. Norris is a martial arts specialist and tough-guy actor, and the “facts” imbue him with super-human powers for comic effect. For instance: “Chuck Norris can slam a revolving door.” “Chuck Norris eats nails as his breakfast cereal 
without any milk.” “There is no theory of evolution—just a list of critters Chuck Norris has allowed to live.”
There is now a similar site for Gauss Facts. These have a mathematical flavor: “Gauss can recite all the digits of 
backwards.” “The Monster Group is scared of Gauss.” `Gauss didn’t discover the normal distribution—instead Nature conformed to his will.” Relevant to our earlier column on Gauss is, “A mathematical discovery is just an unpublished contribution of Gauss.”
Can you come up with computer science-specific humorous hyperbole as “Alan Turing Facts”? Here are just a few to start; you can probably do better:
- Alan Turing would have vetoed Moore’s Law.
- Alan Turing could break any pseudo-random generator—with just a pencil, a single sheet of paper, and an hour or two.
- Garry Kasparov didn’t lose to Deep Blue. It was Alan Turing inside the box running a Turing Machine.
- Alan Turing had a secret way to solve the Halting Problem.
Open Problems
Did I miss some other mathematical things named for Turing? I know that there are countless other things named for him: buildings, labs, fellowships, seminars, and many other things.
[fixed typo “Chuch” before “Norris”—glad he didn’t discover that!:-]
Like this:
Like Loading...
Related
turing kernels in parameterized complexity
Turing-Completeness for programming languages and others.
“A collection of data-manipulation rules (an instruction set, programming language, or cellular automaton) is said to be Turing complete if and only if such system can simulate any single-taped Turing machine.” (Wikipedia)
(Maybe this is not really a “addition” to your list, since this classification is a natural consequence of the Church-Turing Thesis)
There is a programming language with the name Turing. See http://en.wikipedia.org/wiki/Turing_(programming_language) for more info.
Alan Turing does not use oracles, as he finds them too slow.
Turing bifurcations in reaction-diffusion systems.
Alan Turing knew how the Halting Problem could be solved. He showed it to Chuck Norris
Does “Turing’s Theory of Morphogenesis” count?
Alan Turing solved the P=NP problem however the margin in his notebook was too small to write it out.
Turing can fail the Turing Test.
Well, there are security related “facts” – search for bruce schneier facts
A machine halts when Turing says so.
Turing approximates the busy beaver problem by doing push-ups.
A later publication (two years before his death) is also very important in the study of morphogenesis a well as theory of complex dynamical systems, the equations have found many practical applications in computer graphics as procedural texture generation technique, see:
* ‘The chemical basis of morphogenesis’ from Philosophical Transactions of the Royal Society of London, (Series B, No.641, Vol. 237, 14 August 1952).
We could call this; Turing-Morphogenesis !!!
It is in fact called the “Turing Model” in developmental biology, see e.g.
Maini, P., Baker, R., Chuong, C-M. The Turing Model Comes of Molecular Age. Science. 1 December 2006: 1397-1398.
Searching the archives of the AAAS journal Science turns up quite a few other hits. Interesting there doesn’t seem to have evolved a fixed noun phrase in chemistry for the reaction-diffusion patterns: one sees “Turing patterns”, “Turing-type patterns”, “Turing structures”,and “Turing bifurcation” just in the first 10 hits.
Some really good “Turing Facts” here, keep ’em coming! And thanks for adding the Turing programming language and Turing bifurcations in morphogenesis—on the latter here is a SpringerLink article.
Turing was also a pioneer in numerical analysis (condition numbers).
Turing could break Axis cryptography in his head, but helped build computers at Bletchley to hide the fact.
Novels: “The Turing Option” by Harry Harrison and Marvin Minsky (1992), “Enigma” by Robert Harris (1995).
More “impossible” Turing facts:
• Alan Turing can verify program correctness.
• Alan Turing can predict runtimes.
• Alan Turing can find proofs in polynomial time.
Hmmm … why aren’t these claims funny?
Perhaps it is because in our hearts, we mostly believe we can do the same.
Alan Turing Has Godel’s Number
Also a novel by a eminent computer scientist:
Papadimitriou, Christos. Turing: A Novel About Computation. MIT Press, Cambridge, 2003.
A “turmite” is a punning name for robot-like two-dimensional Turing machine.
Turmites were conceived by Greg Turk, popularized in Scientific American by A. K. Dewdney … then fictionalized in numerous stories and novels by the ineffable Rudy Rucker!
And I almost forgot the “Turing Police” in one of William Gibson’s cyberpunk novels (either Mona Lisa Overdrive, or Count Zero). They monitor AI software to make sure it doesn’t get too smart. I wish we had *that* problem.
Turing instability
Worth mentioning is the fact that not only is the paper incredibly important, but that the definition of U Turing gives is riddled with bugs and omissions. Some of the errors are misprints, but there are also errors in the logic/explication. I discovered this for myself when I implemented it in Scheme. One of the most ironic bugs is that U itself never halts!
The paper Understanding Turing’s Universal Machine — Personal Style in Program Description gives details and a corrected version.
Dick’s essay led me to wonder: Why do we find it natural to associate a (real-world) mathematician like Alan Turing to a (mythic) hero-figure like Chuck Norris?
That question is answered by the following famous essay, in which I have substituted the word “mathematician” for the name of a different profession … a profession that shall be revealed at the end of this post.
The above essay provides a concrete answer to the question: Why is Alan Turing beloved, by the public and by mathematicians alike?
The answer is that Alan Turing is beloved because his life embodies all three heroic virtues. First, through his hard work at Bletchley, Turing saved the world from serious trouble. Second, Turing’s performance was dramatically and decisively successful. Third, Turing’s ideas have provided the essential foundations for training entire generations of young mathematicians and computer scientists.
Thus by all three measures, Turing is the precisely kind of hero, that Chuck Norris plays on the film screen.
Who is the author of the above essay? And what is the profession for which “mathematician” was substituted? The author is Gen. Victor Krulak, the profession is “US Marine,” and the full text of the above essay appears in the preface of Krulak’s book First to Fight.
So are mathematicians like Turning “heroes” in that word’s fullest sense? The answer given is, yes they are heroes.
I will mention also, that parallel sentiments can be found in a recent MathOverflow comment by Bill Thurston, as the highest-rated answer to the question “What’s a mathematician to do?”
Great comment John!
In particular, I really liked the answer given by Bill Thurston to the question you mentioned.
Thank you, Akash! Yet another graceful preface by Bill Thurston is in Daina Taimina’s Crocheting Adventures with Hyperbolic Plains (2009).
Does anyone know of other Thurston prefaces?
Although Turing might compute numbers with an infinite number of digits, he can’t do a roundhouse kick…
Alan Turing’s Scotch dispenser never runs out of tape.
Alan Turing was actually a robot from the future. We just couldn’t tell.
The Turing machines help a lot in proving ZFC inconsistent, whithout it you have to resort to the continuum hypothesis and the axiom of choice instead. A mechnical device becomes a part of mathematics leads toa flood of contradictions within mathematics, see: http://kamouna.wordpress.com
Thanks Alan Turing for putting an end to mathematics!
Best,
Rafee Kamouna.
It would be amiss not to mention that he accomplished all this while being persecuted socially, legally, and medically for his sexuality, to the extent that he was driven to suicide at the age of 41. Fine athlete that he was (he came close to placing on the British marathon team for the 1948 Olympics), in a better world he might still be with us, celebrating his 100th birthday next year.
A British software developer, John Graham-Cumming, led a successful effort in 2009 to obtain a formal apology from the British government for its treatment of Turing. At least as of last year, he was leading an effort to have Turing recognized at the 2012 Olympic Games in London.
Then there is Turing Relay race starting and ending at Ely (near Cambridge, England)
http://ramseyroadrunners.org.uk/Result_Turing_Trail_Relay.htm
Turing can do an infinite loop in 5 seconds
Machines halt when Alan Turing tells them to (yes I know someone did that one already but I also thought of it 🙂
Alan Turing can describe the smallest number describable in fewer than nine words in eight words.
Oops I think I mean ‘not describable’.
Undecidabality can be defined as the set of problems Alan Turing hasn’t tried solving yet.
Garbage collectors in runtime environments don’t delete objects created in programmes written by Alan Turing.
Not even humans can pass the Turing Test if Alan Turing is the one giving the test.
Somewhat off-topic, but can we have some von Neumann facts someday?
Things named for Alan Turing: Turing Elves.
Named by: me
Definition: Individuals with no official standing who create works or do deeds to honour and remember Turing, especially in the context of his 100th birthday next year (June 23, 2012). There is an official committee dealing with the centenary, and they’re great, but then there are people who just do stuff on their own and they are the elves.
You can find a bunch of them (along with official stuff, Turing in fiction, Turing goes to Hollywood, and other miscellaneous Turing manifestations) at my blog (The Turing Centenary) here on our very own WordPress if you’re so inclined, or you can just start using the word and help get it into general circulation.