Algorithmic information theory and undecidability (Q5926254): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Latest revision as of 00:40, 5 March 2024
scientific article; zbMATH DE number 1570837
Language | Label | Description | Also known as |
---|---|---|---|
English | Algorithmic information theory and undecidability |
scientific article; zbMATH DE number 1570837 |
Statements
Algorithmic information theory and undecidability (English)
0 references
23 October 2001
0 references
Chaitin has proven that the halting probability \(\Omega=\sum\{2^{-|p|}\mid p\text{\;halts}\}\) of a universal Turing machine is not computable, and, moreover, that any recursively axiomatizable theory enables us to determine only finitely many digits of \(\Omega\). These interesting results have led to a lot of mathematical-sounding philosophical statements. The author shows that some of these statements, if interpreted literally, are actually false. For example, it is sometimes claimed that the non-computability of \(\Omega\) is stronger than the known result about the undecidability of a halting problem. In reality, these problems are reducible to each other: if we can solve the halting problem, then we can easily compute \(\Omega\) and vice versa. It is also sometimes claimed that the number of digits of \(\Omega\) determined by a theory can be used as a measure of this theory's complexity. The author gives a counterexample: an intuitively simple theory that determines many digits of \(\Omega\).
0 references
algorithmic information theory
0 references
undecidability
0 references
Chaitin's theorem
0 references