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. This had taught mathematicians that one had to
be very careful and led to the development of 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 turn of the 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 philisophy of mathematics.
He believed that mathematics could and indeed should be supported by
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 is
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
precise methodologies for mathematical proofs: the subject is now
called proof theory. However, what no one had even imagined was
that the philosophical position put forward
by Hilbert would prove to be completely wrong, and provably so using
the very methods he 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 a new generation of thinkers.
The first world war had undermined German Mathematical, Scientific,
and Engineering supremacy; the rest of the western world was busy
digesting its advances. This was particularly so in Europe (outside
Germany), in Scandinavia, in England, and in the rapidly
industrializing America.
Alan Turing was perhaps 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. He demonstrated the sense in which it could perform
all computations and showed that its halting problem was
undecidable.
Meanwhile, Alonso Church, very much influenced by the German model of
formalizing mathematics, 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 originally intended, was provably
consistent. He and his students (Kleene and Rosser) subsequently
realized that this system allowed the expression of computable
functions. In fact, prior to Turing's remarkable feat, they had
already shown that this embodiment of computable functions produced
some undecidable problems.
Not surprisingly, Alan Turing was invited to Princeton to do his PhD.
under 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 war effort of the allies, at Blechley Park, by
breaking German codes, was a closely held secret but
pivotal.
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 crunchering, 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 as our view of
computation and how it should be organized is influenced by our
understanding and approach to these foundational issues.