- published: 18 Apr 2014
- views: 2610
In the computer science subfield of algorithmic information theory, a Chaitin constant (Chaitin omega number) or halting probability is a real number that informally represents the probability that a randomly constructed program will halt. These numbers are formed from a construction due to Gregory Chaitin.
Although there are infinitely many halting probabilities, it is common to use the letter Ω to refer to them as if there were only one. Because Ω depends on the program encoding used, it is sometimes called Chaitin's construction instead of Chaitin's constant when not referring to any specific encoding.
Each halting probability is a normal and transcendental real number that is not computable, which means that there is no algorithm to compute its digits. Indeed, each halting probability is Martin-Löf random, meaning there is not even any algorithm which can reliably guess its digits.
The definition of a halting probability relies on the existence of prefix-free universal computable functions. Such a function, intuitively, represents a programming language with the property that no valid program can be obtained as a proper extension of another valid program.
[Ciência] Gregory Chaitin - What causes complexity
Euler-Mascheroni Constant: Really cool thing found!
Apery's Constant HAS NO CLOSED FORM!
Gregory Chaitin Lecture Carnegie-Mellon University 2000 Pt 1
Gregory Chaitin Lecture Carnegie-Mellon University 2000 Pt 2
Gregory Chaitin Lecture Carnegie-Mellon University 2000 Pt 3
Gregory Chaitin Lecture Carnegie-Mellon University 2000 Pt 5
Gregory Chaitin Lecture Carnegie-Mellon University 2000 Pt 6
Gregory Chaitin Lecture Carnegie-Mellon University 2000 Pt 7
Gregory Chaitin Lecture Carnegie-Mellon University 2000 Pt 8