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 |
Template:Ency person demonstrated by his Template:Ency term that there is no effective mechanical procedure for deciding whether an arbitrary Template:Ency term will ever finish its computation and halt.
Template:Ency person thus parallels Template:Ency person'S work with Template:Ency person Template:Ency term: \term“{Kurt}Template:Ency person \term,{ the Austrian logician and Alan}Template:Ency person \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)}.
Template:Ency person himself connected both aspects of this intrinsic limit to logical systems Template:Ency term through his concept of Template:Ency term.
According to Template:Ency person: “… since the two problems are logically equivalent, the fact that the Halting Problem has no solution implies that the Template:Ency term 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 Template:Ency term” (1990, p.137).
Of course, more or less provisionally and satisfactory solutions of any practical Template:Ency term still remain possible. But we should always be aware of their Template:Ency term.