ALGORITHMIC INCOMPRESSIBILITY
| Collection | International Encyclopedia of Systems and Cybernetics |
|---|---|
| Year | 2004 |
| Vol. (num.) | 2(1) |
| ID | ◀ 80 ▶ |
| Object type | Discipline oriented, Epistemology, ontology or semantics |
The impossibility to reduce a string of data to a simpler algorithm that would permit to retrieve them.
G. CHAITIN demonstrated that: “A completely random string of digits cannot be reduced to a shorter program at all”. On the contrary: “… a regular string of 1s and 0s describing some data such as 0101010101… which continues for 1000 digits can be encapsulated in a shorter instruction ”repeat 01 500 times“ (1990, p.45-46)
Chaitin related this finding to TURING's uncomputability theorem and showed that: “the halting probability is arithmetically random” (Ibid)
According to CHAITIN, TURING's “… result that the halting probability is random corresponds to TURING's assertion that the halting problem is undecidable”
From another viewpoint, St. KAUFFMAN states: “One measure of the complexity of an algorithm is the minimal program length which yields the desired output. The more minimal an algorithm is, the less redundancy it contains. Consequently, minor modification of minimal programs grossly alter the output of the algorithm. In contrast, minor alterations of highly redundant algorithms modify output only slightly” (1993, p.231). Thus, algorithmic compression may make an algorithm's behavior more uncertain.