UNCOMPUTABILITY THEOREM
Charles François (2004). UNCOMPUTABILITY THEOREM, International Encyclopedia of Systems and Cybernetics, 2(2): 3675.
| Collection | International Encyclopedia of Systems and Cybernetics |
|---|---|
| Year | 2004 |
| Vol. (num.) | 2(2) |
| ID | ◀ 3675 ▶ |
| Object type | Methodology or model |
- “Given a program P and an input data set I there is no way in general to say if P will ever finish processing the data I”.
This theorem was enounced in 1936 by A. TURING' and is closely related to the incompleteness theorem of'GÖDEL .
It relates also to what is known as the halting problem, thus formulated by J. CASTI: “Is there a general algorithm for determining if a program will halt ?” (1990, p.346).
While the problem has some partial and specific solutions, TURING demonstrated that no general one does exist.
As observed by A. CHURCH, uncomputability reflects undecidability and non-recursivity.