Saturday, February 9, 2013

66. Turing's Halting Problem

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.