Editing Chaitin's constant (section)

{{Short description|Halting probability of  a random computer program}}
{{Redirect|Omega number||Omega (disambiguation)#Mathematics}}
{{Use dmy dates|date=December 2020}}
In the [[computer science]] subfield of [[algorithmic information theory]], a '''Chaitin constant''' ('''Chaitin omega number''')<ref>{{Cite web |last=Weisstein |first=Eric W. |author-link=Eric W. Weisstein |title=Chaitin's Constant |url=https://mathworld.wolfram.com/ChaitinsConstant.html |access-date=2024-09-03 |website=Wolfram MathWorld |language=en}}</ref> or '''halting probability''' is a [[real number]] that, informally speaking, 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, one for each (universal, see below) method of encoding programs, it is common to use the letter {{math|&Omega;}} to refer to them as if there were only one.  Because {{math|&Omega;}} depends on the program encoding used, it is sometimes called '''Chaitin's construction''' when not referring to any specific encoding.

Each halting probability is a [[normal number|normal]] and [[transcendental number|transcendental]] real number that is not [[computable number|computable]], which means that there is no [[algorithm]] to compute its digits. Each halting probability is [[Algorithmically random sequence|Martin-Löf random]], meaning there is not even any algorithm which can reliably guess its digits.