 |
| Kurt Gödel |
In the last decades of the nineteenth century, Friedrich Ludwig Gottlob Frege, a professor in the university of Vienna, undertook an ambitious goal: formalizing the arithmetic in a set of axioms and deduction rules, in such a way that every true theorem would be deductible from the axioms by a finite number of applications of the deduction rules. The result was a monumental book, Grundgesetze der Arithmetike (1893-1903), which introduced, among other things, a basic formalization of set theory and a cumbersome notation, quickly replaced by Peano’s, which we are using now.
Unfortunately for Frege, when the second volume of his book was about to be published, he received a letter from Bertrand Russell, proving that his formulation of set theory entails an inconsistency. In Frege’s set theory, some sets are not member of themselves (as the set of all integers, which is not an integer), while other sets are members of themselves (as the set of all infinite sets, which is an infinite set). Russell then defined this set: the set of all sets that are not members of themselves. It is easy to see that this set leads to a paradox: if it is a member of itself, it cannot be a member of itself, and vice versa. Russell’s paradox wreaked havoc with Frege’s work, who had to add a hasty appendix to his book and then abandoned his research on the fundamentals of mathematics.
Bertrand
Russell, together with Alfred North Whitehead, attempted to complete Frege’s
work in his monumental book Principia mathematica (1910-13), which was fated
to the same final defeat as Frege’s. In 1931, Kurt Gödel proved his famous first
incompleteness theorem (Über formal unentscheidbare
Sätze der "Principia Mathematica" und verwandter Systeme),
which can be summarized thus: every consistent formal system with a power similar to
arithmetic is not complete (it contains undecidable true propositions). In other words, starting from a set of
axioms and a number of deduction rules, either we will end up with an
inconsistent result (as in Russell’s paradox) or we will end up with true
theorems that cannot be proved.
Gödel’s
theorem is proved by enunciating mathematically a theorem G that, informally,
can be stated thus: this theorem cannot be proved starting from the axioms and
rules of system S. If theorem G is false (if it can be proved)
it follows that system S is inconsistent (it proves a false theorem).
Therefore, if S is consistent, the theorem must be true, which means that it
cannot be proved in S (this is precisely what the theorem states).
 |
| Alan Turing |
Gödel’s
theorem was only the first of a family of incompleteness theorems, proved in
the following decades. The second was Alan Turing’s theorem about the halting problem, which applies to a family
of abstract computing devices he had designed, called in his honor Turing
machines. These are universal computing devices, meaning that every
problem which can be solved by a digital computer can also be solved by a
Turing machine. In fact, Turing machines are more powerful than digital
computers, for they are supposed to have unlimited memory, which the latter do
not have, although with current memory sizes this restriction can be ignored
most of the time.
The halting problem can be enunciated thus: given a Turing machine (or any analogous mechanism) with a set of input data, will the machine stop, or will it keep on computing forever? For a given case, finding the answer may be simple, but can this problem be solved for all possible machines, together with their input data? Alan Turing proved that the problem cannot always be solved: the question is undecidable. In fact, assuming that the problem can always be solved leads to a contradiction, which means that it can not. Turing’s theorem was proved to be equivalent to Gödel’s theorem.
The
fact that there are incomputable problems
was a shock for computer scientists. This is a theoretical limitation for
computing technology, very different from the practical limitation that makes intrinsically
difficult problems impossible to solve. These problems are
theoretically solvable, but to do it we would need a computer as large as the
universe, working longer than the universe’s life. For all practical purposes,
therefore, intrinsically difficult problems are unsolvable. One of the problems
in this family is computing the perfect solution of a chess match. The program
could in theory be written, but it would be impossibly slow.
 |
| Roger Penrose |
During
the nineteen sixties, the US mathematician Gregory Chaitin proved another
incompleteness theorem which can be stated thus: the randomness of a set of integers is
undecidable. This can be illustrated by the digits of π,
which fulfill all the tests of randomness currently devised by statisticians,
but clearly do not make a random series.
In
1989, Roger Penrose (in The emperor’s new mind)
proposed the following question, inspired by Gödel’s theorem: how can we know
that a theorem is true, even though it is undecidable, i.e. it cannot be proved
by mathematics starting from a reasonable set of axioms? This
seems to point, in his opinion, to the consequence that human intelligence is
qualitatively different from that of computational machines.
No comments:
Post a Comment