Algorithmic information theory and undecidability (Q5926254)
From MaRDI portal
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