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${^{th}}$ 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:

${\bullet }$ 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.

${\bullet }$ Turing Reduction: This is a relationship between computational problems. A problem ${A}$ is Turing reducible to ${B}$ provided there is an algorithm that can solve ${A}$ given ${B}$ as a subroutine. Emil Post first named the notion “Turing reducibility.”

${\bullet }$ 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: ${0}$ is used to denote those problems that can be computed and ${0'}$ is those problems that are equivalent to the Halting Problem. Post, that’s Emil again, raised the beautiful question of was there anything between ${0}$ and ${0'}$? 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 ${\mathsf{P}}$ and ${\mathsf{NP}}$ is way below this theory. Almost always we are interested in problems that lie in the lowest degree ${0}$. 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.

${\bullet }$ 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.

${\bullet }$ 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?

${\bullet }$ 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.

${\bullet }$ 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:

${\bullet }$ 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:

${\bullet }$ 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 $\dots$ 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 ${\pi}$ 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!:-]

May 28, 2011 1:35 am

turing kernels in parameterized complexity

May 28, 2011 6:11 am

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)

May 28, 2011 10:04 am

There is a programming language with the name Turing. See http://en.wikipedia.org/wiki/Turing_(programming_language) for more info.

May 28, 2011 10:09 am

Alan Turing does not use oracles, as he finds them too slow.

May 28, 2011 2:17 pm

Turing bifurcations in reaction-diffusion systems.

6. May 28, 2011 3:02 pm

Alan Turing knew how the Halting Problem could be solved. He showed it to Chuck Norris

May 28, 2011 6:45 pm

Does “Turing’s Theory of Morphogenesis” count?

May 28, 2011 11:27 pm

Alan Turing solved the P=NP problem however the margin in his notebook was too small to write it out.

May 29, 2011 12:03 am

Turing can fail the Turing Test.

10. May 29, 2011 12:12 am

Well, there are security related “facts” – search for bruce schneier facts

May 29, 2011 2:57 am

A machine halts when Turing says so.

Turing approximates the busy beaver problem by doing push-ups.

May 29, 2011 5:25 am

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

May 29, 2011 7:15 am

We could call this; Turing-Morphogenesis !!!

• June 1, 2011 9:20 am

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.

13. May 29, 2011 4:32 pm

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.

May 29, 2011 9:06 pm

Turing was also a pioneer in numerical analysis (condition numbers).

15. May 30, 2011 2:12 am

Turing could break Axis cryptography in his head, but helped build computers at Bletchley to hide the fact.

16. May 30, 2011 7:43 am

Novels: “The Turing Option” by Harry Harrison and Marvin Minsky (1992), “Enigma” by Robert Harris (1995).

• May 30, 2011 10:59 am

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.

May 30, 2011 1:52 pm

Alan Turing Has Godel’s Number

• June 1, 2011 9:42 am

Also a novel by a eminent computer scientist:

• June 1, 2011 10:53 am

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!

• June 1, 2011 11:05 am

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.

May 30, 2011 2:01 pm

Turing instability

18. May 30, 2011 5:48 pm

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.

19. May 31, 2011 7:53 am

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.

Why does the world need mathematicians?

Mathematics exists today—flourishes today—not because of what we know we are, or what we know we can do, but because of what the world believes we are and believes we can do.

Essentially, because of the unblemished achievements of mathematics over centuries, the world believes three things about mathematicians.

First, they believe that when trouble comes to the world, there will be mathematicians—somewhere—who through hard work have made themselves ready to do something about it, and do it at once. They picture mathematicians as mature individuals—dedicated members of a serious professional community.

Second, they believe that when mathematicians bend their minds to a task, they invariably turn in a performance that is dramatically and decisively successful—not most of the time, but always. The world’s faith and convictions in this regard are almost mystical. The mere association of the word “mathematics” to a challenge is an automatic source of encouragement and confidence everywhere.

The third thing that they believe is that training in mathematics is downright good for young people; that mathematicians are the masters of an unfailing alchemy that helps convert unoriented youths into proud, self-reliant stable citizens—citizens into whose hands the planet’s affairs may safely be entrusted.

The people believe these three things. They believe them deeply and honestly, so much that they are willing to pay for mathematicians to solve problems, and to teach young people.

Therefore, for reasons that completely transcend cold logic, the world wants mathematicians. These reasons are strong, they are honest, they are deep-rooted, and they are above question or criticism. So long as they exist—so long as people are convinced that mathematicians can really do the three things I have mentioned—we are going to have a mathematical profession.

And likewise, should people ever lose that conviction—as the result of the mathematics community’s failure to meet their high—almost spiritual—standards, the profession of mathematics will swiftly disappear.

Is there a chance that such a thing might happen? I think there is. I think that we ourselves can shake these convictions and the accompanying faith which really sustain us. By a lack of attention we can lose the inspirational personal relation that is shared between our senior members and our rank-and-file. Also, by carelessness or inordinate attention to less important things, we can lose the attributes of professional dedication and unfailing preparedness which, in centuries past, has deservedly made mathematics one of humanity’s treasures.

How serious it is, I don’t profess to estimate to you, but it certainly worries me. It does, because if the world wanted to try, she could get along without a profession of mathematics.

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?

• June 2, 2011 9:42 am

Great comment John!
In particular, I really liked the answer given by Bill Thurston to the question you mentioned.

• June 2, 2011 10:04 am

Thank you, Akash! Yet another graceful preface by Bill Thurston is in Daina Taimina’s Crocheting Adventures with Hyperbolic Plains (2009).

Our brains are complicated devices, with many specialized modules working behind the scenes to give us an integrated understanding of the world. Mathematical concepts are abstract, so it ends up that there are many different ways that they can sit in our brains …

A given mathematical concept might be primarily a symbolic equation, a picture, a rhythmic pattern, a short movie—or best of all, an integrated combination of several different representations. These non-symbolic mental models for mathematical concepts are extremely important, but unfortunately, many of them are hard to share …

Mathematics sings when we feel it in our whole brain. People are generally inhibited about even trying to share their personal mental models. People like music, but they are afraid to sing. You only learn to sing by singing.

Does anyone know of other Thurston prefaces?

20. May 31, 2011 12:00 pm

Although Turing might compute numbers with an infinite number of digits, he can’t do a roundhouse kick…

May 31, 2011 1:06 pm

Alan Turing’s Scotch dispenser never runs out of tape.

May 31, 2011 1:09 pm

Alan Turing was actually a robot from the future. We just couldn’t tell.

June 1, 2011 7:04 am

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.

24. June 1, 2011 9:37 am

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.

25. June 2, 2011 9:25 am

Turing can do an infinite loop in 5 seconds

June 4, 2011 11:10 am

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.

June 4, 2011 11:30 am

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.

28. June 6, 2011 3:38 am

Somewhat off-topic, but can we have some von Neumann facts someday?

29. November 21, 2011 5:32 pm

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.