HALTING PROBLEM
| Collection | International Encyclopedia of Systems and Cybernetics |
|---|---|
| Year | 2004 |
| Vol. (num.) | 2(1) |
| ID | ◀ 1505 ▶ |
| Object type | Epistemology, ontology or semantics, Methodology or model |
TURING demonstrated by his uncomputability theorem that there is no effective mechanical procedure for deciding whether an arbitrary program will ever finish its computation and halt.
G. CHAITIN thus parallels TURING'S work with GÖDEL }'s\term{incompleteness theorem: \term“{Kurt}GÖDEL \term,{ the Austrian logician and Alan}TURING \term,{ the father of the computer, showed that it is impossible to obtain both a consistent and complete axiomatic theory of mathematics and a mechanical procedure for deciding whether an arbitrary mathematical assertion is true or false, or is provable or not” (1990, p.44)}.
CHAITIN himself connected both aspects of this intrinsic limit to logical systems validation through his concept of algorithmic incompressibility.
According to J. CASTI: “… since the two problems are logically equivalent, the fact that the Halting Problem has no solution implies that the Decision Problem is also unsolvable. So we run up against a brick wall in trying to get to the heart of things by following a set of rules” (1990, p.137).
Of course, more or less provisionally and satisfactory solutions of any practical decision problem still remain possible. But we should always be aware of their limits.