TURING GETS HIS WAY

Dick Pountain - 07/01/95 22:28 - IDEALOG 5


Just before Christmas a paragraph on the Home News page of
the Guardian caught my eye, announcing that on the 40th
anniversary of his suicide, an inner-city ring road in
Manchester has been named Alan Turing Way. The short
article described Turing as "computer pioneer, wartime
code-breaker, and gay martyr" - all of which he certainly
was - and also as a "real local genius" which he was not,
having being born in London, raised in Kent and educated
in Cambridge.

It would be churlish in the extreme to criticise this long
overdue honour, but I just can't help wondering how long
it's going to take for Britain to appreciate Alan Turing's
achievements in their full depth. It's good that Turing
should be honoured as an engineer who designed the first
electronic computers and used them to crack the German
navy's Enigma codes, an achievement that Whitehall now
admits was crucial to winning the 2nd World War. This
country has always treated its engineers shamefully,
preferring to celebrate the most minor novelist or
comedian over someone who merely makes things. However
Turing was not first and foremost an engineer but a
mathematician, and he deserves a place among the great
intellectual revolutionaries of the 20th century.

In the 1930 the Austrian logician Kurt Gödel rocked
mathematics to its foundations by showing that it is
incomplete; that there are true mathematical statements
that can never be proved. Building on Gödel's work, in
1936 Alan Turing working alone in Cambridge showed that
there are problems that no algorithm could ever solve, a
result discovered in the same year in a slightly different
form by the Americans Alonzo Church, Emil Post and Stephen
Kleene. These men at a stroke founded a new discipline
that came to be called Computer Science. Alan Turing made
his discovery by performing thought experiments on an
imaginary device called the Turing Machine, which is the
archetype of all possible computers (remember that in 1936
no real computers existed). He invented the modern
computer while at the same time demonstrating both what it
COULD and COULD NOT do.

Most educated people nowadays have some inkling of what
Einstein, or Heisenberg, or Crick and Watson discovered
but very few indeed could tell you anything at all about
Gödel's Theorem or the Church/Turing thesis. Yet the
philosophical ramifications of this work, though still
barely explored, are perhaps already of more relevance to
our daily lives than are those of quantum theory or
relativity.

Turing's paper of 1936 explored the notion of
computability, showing that some functions cannot be
computed because the program that would compute them will
never halt, ie. it will run for ever. He further showed
that it's impossible to write a 'super-program' that would
predict whether or not any particular computer program
will halt. In essence Turing proved that any finite
logical system (which includes, like it or not, we humans)
is subject to the theorems of Gödel and Church. Gödel's
theorem tells us that no programmatic method can generate
all truths, and Church's theorem tells us that we cannot
predict the consequences of even those programs we do
devise by any better means than running them. So much for
all those totalitarian and fundamentalist thought systems
that claim to explain the whole of life from a few a
priori principles. Life and the universe are inherently
messy, knowable only in parts.

A 1952 paper by John Myhill called "Some Philosophical
Implications of Mathematical Logic: Three Classes of
Ideas" explains this all rather nicely (and is well
summarized in Rudy Rucker's excellent book "Mind Tools" -
Penguin 1988). Myhill suggests that the properties of the
world, including human culture as well as nature, can be
analysed at three increasing levels of complexity which he
calls the computable, the listable and the prospective.

Consider the page of PC Pro you're reading now. Deciding
whether this article is formed from grammatical English is
a computable matter. You can look up each word in a
dictionary, and compare the parts of speech and sentence
structures with rules from a grammar textbook to arrive at
a yes/no answer.

However even supposing my article is grammatical it may
not MEAN anything to you. That may be because the article
is just gibberish, or because you are unfamiliar with the
concepts it contains. Maybe you'll read it again in a year
and it will mean something in the light of other stuff
you've read. The longer you live the more articles you
will understand, but it's impossible to say in advance
which articles those will be. Meaning is not a computable
property, but it is listable.

Whether or not this article is any good is neither a
computable nor a listable property. There's no simple
mechanical rule that distinguishes good articles from bad
(ie. goodness is not computable) and equally no program or
attitude that would allow you to generate all the possible
good articles (ie. goodness is not listable). This highest
kind of property, which Myhill calls prospective, applies
to those 'subjective' aspects of human culture like
intuition, inspiration, creativity, beauty, virtue.

In a parallel universe where Gödel's theorem did not hold,
all properties would be listable; anyone could become a
composer or a comedian or a painter by just memorising a
few rules, and deja vu would be the prevailing experience.
In a universe without Gödel OR Church/Turing all
properties would be computable and so Art Enforcers could
march through the galleries scanning each painting with a
hand-held computer that read out GOOD or BAD.

Many people deeply distrust computers and fear that they
are inevitably leading the world into Orwellian dystopias
of this sort. Gödel, Church and Turing, if they were more
widely understood, could reassure these people that it
just can't happen. Equally they might debunk some of the
more preposterous claims of the cyber-maniacs who imagine
we will all be living in a virtual world by the end of
next year.

I can't sum it up any better than Rudy Rucker does: "Our
world is endlessly more complicated than any finite
program or finite set of rules. You're free, and you're
really alive and there's no telling what you'll think of
next". Alan Turing might manage an ironic smile at that,
from beyond his early grave.