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)

**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.***computer*
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, 100*N*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 100*N*. 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 ≤100*N*. 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