Chaitin's constant

The Chaitin's constant indicates the likelihood of a universal Turing machine for any input stops.

${\ displaystyle \ Omega}$ is an example of an incalculable number . It is defined as , according to Gregory Chaitin

{\ displaystyle \ Omega = \ sum _ {p \ \ mathrm {h {\ ddot {a}} lt}} 2 ^ {- \ left | p \ right |}}

where the sum of all holding programs is meant (all programs that hold after a finite run time without input) and denotes the length of the program in bits . This means that every holding program with a length of m bits increases the m-th bit of the binary representation of by 1. ${\ displaystyle p}$ ${\ displaystyle | p |}$ ${\ displaystyle \ Omega}$

Note: Since there is certain freedom to define universal Turing machines, the exact value of the constant depends on the machine definition chosen.

By knowing the first n bits of the constant this can be halting problem for up to n-bit programs decide, so that by accurate knowledge of the first few thousand bits of the constant could solve many interesting problems in mathematics.

However, since the holding problem cannot be solved, it can not be calculated and is therefore a transcendent real number . ${\ displaystyle \ Omega}$

In 2002 a research group led by Cristian Calude from the University of Auckland determined the first 64 bits of the number by checking all Turing programs of up to 80 bits in length.

literature

Cristian S. Calude : Information and Randomness - An Algorithmic Perspective . 2nd Edition. Springer-Verlag, Berlin 2002, ISBN 3-540-43466-6 .
Gregory Chaitin : A theory of program size formally identical to information theory . (PDF; 249 kB; April / December 1974) In: Journal of the ACM , July 22, 1975, pp. 329–340 (English)

Web links

Eric W. Weisstein : Chaitin's constant . In: MathWorld (English).
Cristian S. Calude's website . (the first 64 bits of a Chaitin's constant)
Jörg Resag: The limits of predictability . joerg-resag.de, 2008, chapter 3.4