Hilbert had
identified the so-called decision problem for defining a closed mathematical universe:
Is there a decision procedure that, given any statement expressed in the given
language, will always produce either a finite proof of that statement, or else
a definite finite construction that refutes it, but never both? In other words,
can a precise mechanical procedure
distinguish between provable and disprovable statements within a given system?
The answer to
this question required a way to define 'mechanical procedure'. Alan Turing (1936) provided an answer. He proved, among other
things, that the notions of 'mechanical procedure', 'effectively calculable',
and 'recursive functions' are actually one and the same thing.
I make a
digression here to describe recursive functions (see, e.g., Kurzweil 1998). These are
functions that can be defined by the accumulation of elementary component
parts; they can be deconstructed into a finite number of elemental steps. A
recursive procedure is one that calls
on itself. Recursion is a process of defining or expressing a function or
procedure in terms of itself. Each iteration of the recursive procedure is
designed to produce a simpler version of the problem. This process continues
until the algorithm reaches a subproblem for which the answer is already known
or simple to work out in a nonrecursive manner.
As an
illustration, consider the computation of the factorial function n!. The
recursive rule here is: n! = n.(n-1)!. The procedure calls
on itself again and again, till it reaches the subproblem 1!, for which the
answer is a given: 1! = 1.
Recursion is used
extensively in game-playing algorithms. For example, for a chess-playing
program (first envisaged by Turing), Kurzweil (1998) defines the
following recursive formula:
PICK MY BEST
MOVE: Pick my best move, assuming my opponent will do the same. If I've won,
I'm done.
At each step
of the recursion, consequences of each possible move are worked out. It is
assumed that the opponent is equally intelligent, and will do the same. Since
the number of possibilities to consider may blow up exponentially, the
so-called minimax procedure is adopted to arrive at a strategy in
reasonable time. An expanding 'tree' of possible moves and countermoves is
constructed (for a preassigned time), and an assessment of the freshest
'leaves' (extremities) of the tree that minimizes the chances of the opponent
to win, and maximizes the chances of the game-playing program to win, is
carried out. This information is then fed back down the branches of the tree
for determining the best move of the program.
Returning to
the work of Turing, his most important simplifying and concretizing departure
from the approach of Gödel was to bring in the idea of a (conceptual) computer
for number crunching. He interpreted Hilbert’s philosophy to mean that there
should be a computer and a computer program for implementing Hilbert’s idea of
a mechanical procedure for deciding whether a given proof is correct or not.
The most
famous notion Turing introduced was that of the universal computer. He demonstrated that all digital computers
are fundamentally equivalent, regardless of what is there in their innards. It
is all 1s and 0s underneath. He used this approach to prove that unsolvable mathematical problems do exist:
He proved the so-called halting problem:
There
can be no general procedure to
decide in advance whether a self-contained computer program will eventually
halt (i.e., solve a posed problem and then halt). Often the only way to answer this question is by actually running the
program to see if it halts or not.
In other words, there is no computer program that can take another
computer program and determine with certainty whether the first program halts
or not. Thus there is no mechanical procedure that can decide in advance
whether a program will eventually halt or not. And this means that there is no
set of Hilbertian mathematical axioms that can enable us to prove whether a
program will halt or not.
Turing
invented an imaginary device now called the Turing machine. It consisted
of a black box (it could be a computer or a human being) able to read and write
a finite alphabet of symbols to and from an unbounded length of paper tape, and
capable of changing its own 'm-configuration' or 'state of mind'. In the
context of computational science, Turing introduced the all-important notions
of discrete time and discrete state of mind.
This
made logic a sequence of cause-and-effect steps, and mathematical proof a
sequence of discrete logical steps.
The Turing
machine embodies a relationship between a sequence of symbols in space and a
sequence of events in time. Each step in the relationship between the tape and
the Turing machine is governed by what we call a program. The program provides
instructions to the machine for every conceivable situation.
Turing argued
that all symbols, all information, all meaning and all intelligence that can be
described in words or numbers can be encoded (and transmitted) as binary
sequences of finite length. In contrast to this, Gödel’s work on undecidability in mathematics states
that in all but the simplest mathematical systems there may be propositions
that cannot be proved or disproved by any finite mathematical or logical
process; the proof of a given proposition may possibly call for an infinitely
large number of logical steps.
However, Turing did prove, like Gödel, that there are self-referential questions a universal Turing machine
cannot answer.
But perhaps outsiders can.
Turing's proof that the halting problem in unsolvable is as follows (Chaitin 2006):
Suppose a general procedure H does exist that can decide whether
any given computer program will halt. Knowing H, we can construct a
program P that uses H as a subroutine. Suppose the size of
program P is N bits, and P knows its own size. Clearly, P
is large enough to contain the number N. Using the procedure H,
the program P can take a look at all programs which are up to, say, 100N
bits in size, and find out which of them halt and which do not. After this, P
runs all the programs which had halted to see what outputs they had generated.
Naturally, this will be a set of all digital objects with a degree of
complexity (i.e. the number of bits required for their description) up to 100N.
At the end, P outputs the smallest integer not in this set, and then
halts.
This means that we have shown that P has halted and it has given
an output integer that cannot be produced by a program of size ≤100N.
This is logically inconsistent because the size of P in only N.
Therefore H does not exist and thence P cannot be constructed;
i.e. a general procedure H does not exist that can decide whether or not
any given computer program will halt. QED.
Turing’s halting problem is unsolvable.
No comments:
Post a Comment