CPSC521: Foundations of Functional Programming
Author: Robin Cockett
Date: 14th Oct. 2008
ON THE
HISTORY OF COMPUTABILITY
The theory of the computability has many roots, however, it began to
take significant shape at the very beginning of the 20th
century. Logicians and philosophers prior to that time
had been busy trying to sort out a secure foundation for
mathematics. This development underwent a series of
embarassing revisions in order to patch up "paradoxes" (or
antinomes) which kept on being discovered in the systems being
proposed. A famous example is Russell's paradox which
indicated that one had to be very careful about how one defined
sets. Nonetheless Mathematicians and logicians built several
sophisticated logical systems which codified reasoning. By the
turn of the 20th century these foundational developments had matured
into the development of set theory and the use of logical systems
had become the norm.
At the beginning of the 20th century German mathematics dominated
the intellectual world. At the international Congress of
Mathematicians in 1900 the German mathematician Hilbert presented an
address
which not only posed a series of open mathematical problems which
have stood the test of time but also exposed his philosophy of
mathematics. He believed that mathematics could -- and indeed
should -- be supported by a detailed and precise notion of
proof. Furthermore, he proposed that every problem in
mathematics by its nature is solvable in the sense that,
once one has set up a proof system, and the problem has been
precisely stated with diligence one can either find a
counter-example or a proof of the statement.
These remarks spurred a number of researchers to further develop the
precise methodology of mathematical proofs: the subject is now
called proof theory and it is a rich and fascinating area with much
yet to be understood. What no one at that time even imagined
was that the philosophical position put forward by Hilbert would
prove to be completely wrong! Furthermore, that it would be
provably wrong using the very methods Hilbert was advocating!
However, it took some thirty years before this was realized by
the Czech-born mathematician Godel. Godel's
incompleteness theorem showed that things were not simply
either true or false: there must necessarily also be unprovable
things. Even more amazing was that some of the specific
problems that Hilbert had discussed in his address (e.g. Hilbert's 10th problem
) were of this very nature!
Although it was understood that the flaw in Hilbert's philosophy was
directly linked to the nature of computation, it took some time for
this aspect to be made explicit. The reason for this was
simply that, while the notion of proof
had now received considerable attention, the notion of computation still remained
rather murky and mysterious. However, technology was fast
catching up with mathematics and practical computing devices were
already being produced and exciting the minds of the new generation
of thinkers. The first world war had underlined German
Mathematical, Scientific, and Engineering supremacy: the rest
of the western world was busy digesting German advances and moving
forward themselves. This was particularly so in Europe (outside
Germany), in Scandinavia, in England, and in the rapidly
industrializing America.
Alonso Church, who was based at Princeton, had been greatly
influenced by the German model of formalizing mathematics, and had
invented the lambda calculus as a foundational language.
Unfortunately, it had turned out to suffer from a number
paradoxes. Church had, in a very pragmatic move, simplified
the system down to something which, even if it was a good deal less
expressive than he had originally intended, was provably consistent.
He and his students (Kleene and Rosser) subsequently realized
that this system allowed the expression of all computable functions
and they showed that this embodiment of computable functions
produced some undecidable problems (1932-34). The Princeton
group, through these results, became the focus of work on
computability.
Alan Turing was one of the most brilliant product of this
intellectual soup. Even as a schoolboy, Turing was reading
German mathematics. By the time he was an undergraduate at
Cambridge his mind was buzzing with the most current ideas of his
time. At Cambridge he invented an incredibly simple
mathematical device, we now know as the Turing machine, to exemplify
the notion of computation (1936). He demonstrated the sense in
which it could perform all computations and showed that its halting
problem was undecidable.
Not surprisingly, Alan Turing was invited to Princeton to work with
Alonso Church. Together they showed that all notions of
computation, which were being considered at that time, were
equivalent. After Princeton Turing returned to Cambridge,
there his academic career was overtaken by the second world
war. His contribution to the allied war effort, at Blechley
Park, by breaking German codes, was a closely held secret but
pivotal in the war which consumed every corner of Europe -- and
ultimately most of the developed world.
It may surprise you how mathematical those roots are ... in a sense
Computer Science, as it is so often taught in North America, is a
travesty of where the subject started and of the deep philosophical
and technical problems with which founding computer scientists, like
Church, Post, Turing, Curry, and even that somewhat ambitious and
contraversial figure von Neumann were preoccupied. Much of
modern computer science, as it is presented, is more reminiscent of
the comfortable commercial image promoted by IBM: computers are
number crunching, vote counting, mass storage, word processing,
clever communication machines. Graphics, web pages, GUI's, and
networks are where it is all at!
We tend to forget about the great philosophical debates which at the
turn of last century rocked the foundations of mathematics leading
to a new view of mathematics and to the search for better
foundations for mathematics. Furthermore we tend to
forget, amidst all the things that computing technology brings, that
this search is by no means over! These foundational issues,
which now seem so remote and abstract, continue to have a direct
impact now. Our view of computation and how it should be
organized is directly influenced by our understanding and approach
to these foundational issues.