Turing believes machines think. Turing lies with men. Therefore machines do not think.

— Alan Turing, letter to Norman Routledge (1952)

The bitter syllogism Turing wrote to a friend, just after his conviction, sums up his life: a man who thought with logic and was judged by people who did not understand him. The work he left behind, however, is everywhere.

In computer science

The Turing machine is still the official definition of what it means to calculate. When a computer scientist says a problem “has no algorithm”, they mean no Turing machine solves it; when they say a problem is “hard”, they count the steps a Turing machine needs.

From that counting came the most famous question in the field, P versus NP: is every problem whose solution is easy to check also easy to find? Putting a jigsaw puzzle together is hard; checking an assembled puzzle is easy. Nobody knows whether that difference is real or just a lack of ingenuity. The Clay Institute offers a million dollars to whoever answers it.

Since 1966 the Association for Computing Machinery has awarded the annual Turing Award, considered the Nobel Prize of computing.

In cryptography and statistics

The war against the Enigma showed that the security of a cipher lies not in the number of keys, but in the absence of flaws that allow most of them to be eliminated at once. Modern cryptography was born from that lesson. And the deciban, through I. J. Good, helped bring Bayesian statistics back to the centre of science.

In biology and artificial intelligence

The equations of morphogenesis underlie a whole field, the mathematical biology of patterns. And the imitation game is still the reference point for any discussion of whether a machine thinks, now that machines converse.

The statue of Turing in Sackville Park, Manchester, unveiled in 2001. He is sitting on a bench, holding an apple.
The statue of Turing in Sackville Park, Manchester, unveiled in 2001. He is sitting on a bench, holding an apple.David Dixon · Wikimedia Commons · CC BY-SA 2.0

Making amends

For decades Turing’s war work was a state secret, and his conviction a cause for silence. The story began to change in 1983, with the biography written by the mathematician Andrew Hodges. Then came:

  • the Manchester statue, in 2001, in a park next to the university;
  • the British government’s apology, in 2009;
  • the royal pardon, in 2013, and the 2017 law that pardoned the others convicted;
  • the 50-pound note bearing his face, issued on 23 June 2021, his birthday.

To remember

Exercise: checking is easy

Someone claims that $8{,}633=89\cdot97$. How much work is it to check? And how much would it take to find the factors without the hint?

Checking is one multiplication: $89\cdot97=89\cdot100-89\cdot3=8{,}900-267=8{,}633$. Finding them requires testing divisors up to $\sqrt{8633}\approx93$: that is 24 primes, from 2 to 89, and only the last one works. With numbers hundreds of digits long, checking is still instant and finding becomes impractical. Internet cryptography rests on this asymmetry.

Exercise: Turing's syllogism

Is the syllogism in the epigraph valid? Where is the mistake?

It is not valid. The premises are about Turing, and the conclusion is about machines. That someone has an opinion and a private life that others disapprove of says nothing about the truth of the opinion. Turing wrote the syllogism precisely to mock that kind of reasoning.

Sources: Andrew Hodges, Alan Turing: The Enigma (1983) · Turing Award, ACM · P vs NP, Clay Mathematics Institute · Bank of England, 50-pound note.

All topics on Alan Turing · ← Morphogenesis: the leopard’s spots in equations · Image credits →

Image credits.