472 | 42 TURING’S lEGACy
In 2011 an e-petition on a UK government website requested an official pardon. Justice
Secretary Lord McNally rejected this request the following year, saying that Turing was ‘prop-
erly convicted’ (which he undoubtedly was).^36 Nevertheless Queen Elizabeth II issued a post-
humous Royal Pardon 18 months later:^37
NOW KNOW YE that we, in consideration of circumstances humbly represented to us, are
graciously pleased to grant our grace and mercy unto the said Alan Mathison Turing and grant
him our free pardon posthumously in respect of the said convictions; AND to pardon and remit
unto him the sentence imposed upon him as aforesaid; AND for so doing this shall be a sufficient
Warrant.
The pardon was granted under the ‘Royal Prerogative of Mercy’, following a request from the
then Justice Minister Chris Grayling. Grayling stated:^38
Turing deserves to be remembered and recognised for his fantastic contribution to the war
effort and his legacy to science. A pardon from the Queen is a fitting tribute to an exceptional
man.
But why only Turing? Are only exceptional men worthy of being pardoned for the ‘crime’
of being gay? What about the 75,000 others who were convicted under the same wicked
legislation?
linguistic legacy
Turing’s name features in numerous technical terms. Many of these are notable enough to have
individual Wikipedia entries. Best known are ‘Turing machine’ and ‘Turing test’. There are also
more specialized examples, such as ‘symmetric Turing machine’, ‘reverse Turing test’ (where
a human pretends to be a computer) and ‘visual Turing test’ (a Turing-style test for computer
vision systems). The term ‘Alan Turing law’ entered Wikipedia in 2016, following headlines
such as this one in The Independent newspaper:^39
‘Alan Turing law’ unveiled by government will posthumously pardon thousands of gay men con-
victed of historic offences.
Turing computability is the basic type of computability studied in mathematical recursion
theory. The Church–Turing thesis (also known as Turing’s thesis) is a famous thesis about
computability, as explained in Chapter 41. David Deutsch published a different claim about
computability and this is sometimes called the ‘physical’ Church–Turing thesis, or the Church–
Turing–Deutsch thesis (again see Chapter 41).
A Turing reduction is a special kind of algorithm that transforms—or ‘reduces’—one prob-
lem to another. The algorithm is special in that it makes use of what Turing called an ‘ora-
cle’, a hypothetical device that is able to solve the printing problem or carry out some other
mathematical job that cannot be done by a Turing machine (see Chapters 7 and 37). ‘Turing
equivalence’ means that this reduction can be done in both directions: the first problem can be
transformed into the second and also the second can be transformed into the first.
A Turing degree, or degree of unsolvability, is a measure of a set’s resistance to being gener-
ated by an algorithm—or in other words, a measure of the set’s algorithmic intractability.
(Typically the set in question consists of infinitely many integers.) The higher the Turing