Chaitin's Constant

Chaitin's Constant

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 which is not computable, which means that there is no algorithm that enumerates its digits.

Read more about Chaitin's Constant:  Background, Definition, Relationship To The Halting Problem, Interpretation As A Probability, Properties, Uncomputability, Incompleteness Theorem For Halting Probabilities, Super Omega

Famous quotes containing the word constant:

    I should say that the most prominent scientific men of our country, and perhaps of this age, are either serving the arts and not pure science, or are performing faithful but quite subordinate labors in particular departments. They make no steady and systematic approaches to the central fact.... There is wanting constant and accurate observation with enough of theory to direct and discipline it. But, above all, there is wanting genius.
    Henry David Thoreau (1817–1862)