BOwEN & COPElAND | 473
degree, the harder the problem that the set characterizes. For example, the set of numbers
of Turing machines that halt (i.e. the set that characterizes the halting problem) is of degree
1, meaning that the halting problem is at the easier end of the spectrum of uncomputable
problems.
The Bletchley Park term ‘Turingery’ is still in use in the modern literature and refers to a
codebreaking method invented by Turing in July 1942 (see Chapter 14). Turingery was used
against the German Tunny cipher.
The first winner of the A. M. Turing Award, American computer scientist Alan Perlis (who
won the award in 1966) coined the term ‘Turing tar-pit’ (sometimes written ‘Turing tarpit’) in
- A Turing tar-pit is any computer programming language (or computer interface) that
shares two of the most distinctive features of the universal Turing machine: it is highly flexible,
yet hard to work with, because the user is provided with only very minimal facilities. The uni-
versal Turing machine, the ultimate Turing tar-pit, is as flexible as it is possible for a computing
device to be (i.e. universal), but every commonplace job—addition, multiplication, counting,
sorting into alphabetical order, and so on—has to be done by means of utterly minimal facilities
(move left one square, erase a single bit, etc.). A completely different sense of the term ‘Turing
tar-pit’ refers to the fact that every account of computation ever offered has turned out to be
equivalent to Turing’s: there is no escaping from the Turing tar-pit.
A computer programming language called Turing was developed in 1982 at the University of
Toronto. Related languages include Turing+, introduced in 1987 for programming concurrent
systems, and Object-Oriented Turing, developed in 1991 as a replacement for Turing+ (and, as
the name implies, providing object-oriented programming features).
figure 42.5 The Alan Turing Building at the University of Manchester, housing the School of Mathematics.
Posted to Wikimedia Commons by Mike Pee, https://commons.wikimedia.org/wiki/File:Alan_Turing_Building_1.jpg. Creative
Commons Licence.
