In the computer science subfield of algorithmic information theory a Chaitin constant or halting probability is a real number that informally represents the probability that a randomlychosen 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 halting algorithm that enumerates its digits.
Contents
Background
The definition of a halting probability relies on the existence of prefixfree 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.
Suppose that F is a partial function that takes one argument, a finite binary string, and possibly returns a single binary string as output. The function F is called computable if there is a Turing machine that computes it.
The function F is called universal if the following property holds: for every computable function f of a single variable there is a string w such that for all x, F(w x) = f(x); here w x represents the concatenation of the two strings w and x. This means that F can be used to simulate any computable function of one variable. Informally, w represents a "script" for the computable function f, and F represents an "interpreter" that parses the script as a prefix of its input and then executes it on the remainder of input. Note that for any fixed w the function f(x) = F(w x) is computable; thus the universality property states that all computable functions of one variable can be obtained in this fashion.
Full article ▸
