Open main menu
Home
Random
Recent changes
Special pages
Community portal
Preferences
About Wikipedia
Disclaimers
Incubator escapee wiki
Search
User menu
Talk
Dark mode
Contributions
Create account
Log in
Editing
Chaitin's constant
(section)
Warning:
You are not logged in. Your IP address will be publicly visible if you make any edits. If you
log in
or
create an account
, your edits will be attributed to your username, along with other benefits.
Anti-spam check. Do
not
fill this in!
== Interpretation as a probability == The [[Cantor space]] is the collection of all infinite sequences of 0s and 1s. A halting probability can be interpreted as the [[measure theory|measure]] of a certain subset of Cantor space under the usual [[probability measure]] on Cantor space. It is from this interpretation that halting probabilities take their name. The probability measure on Cantor space, sometimes called the fair-coin measure, is defined so that for any binary string {{mvar|x}} the set of sequences that begin with {{mvar|x}} has measure {{math|2{{sup|β{{abs|''x''}}}}}}. This implies that for each natural number {{mvar|n}}, the set of sequences {{mvar|f}} in Cantor space such that {{math|1=''f''(''n'')}} = 1 has measure {{sfrac|1|2}}, and the set of sequences whose {{mvar|n}}th element is 0 also has measure {{sfrac|1|2}}. Let {{mvar|F}} be a prefix-free universal computable function. The domain {{mvar|P}} of {{mvar|F}} consists of an infinite set of binary strings <math display="block">P = \{p_1,p_2,\ldots\}.</math> Each of these strings {{math|''p''{{sub|''i''}}}} determines a subset {{math|''S''{{sub|''i''}}}} of Cantor space; the set {{math|''S''{{sub|''i''}}}} contains all sequences in cantor space that begin with {{math|''p''{{sub|''i''}}}}. These sets are disjoint because {{mvar|P}} is a prefix-free set. The sum <math display="block">\sum_{p \in P} 2^{-|p|}</math> represents the measure of the set <math display="block">\bigcup_{i \in \mathbb{N}} S_i.</math> In this way, {{math|Ω{{sub|''F''}}}} represents the probability that a randomly selected infinite sequence of 0s and 1s begins with a bit string (of some finite length) that is in the domain of {{mvar|F}}. It is for this reason that {{math|Ω{{sub|''F''}}}} is called a halting probability.
Edit summary
(Briefly describe your changes)
By publishing changes, you agree to the
Terms of Use
, and you irrevocably agree to release your contribution under the
CC BY-SA 4.0 License
and the
GFDL
. You agree that a hyperlink or URL is sufficient attribution under the Creative Commons license.
Cancel
Editing help
(opens in new window)