Chaitin's constant

related topics
{math, number, function}

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 randomly-chosen 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 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.

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 ▸

related documents
Breadth-first search
Goldbach's conjecture
Homology (mathematics)
Probability density function
Natural number
Euclidean space
Linear independence
Factorization
Type theory
Glossary of topology
Euclidean algorithm
Heine–Borel theorem
Axiom schema of replacement
Wiener process
Pushdown automaton
Presentation of a group
MATLAB
Binary relation
Abstract interpretation
L'Hôpital's rule
Insertion sort
Random variable
Analysis of algorithms
E (mathematical constant)
Context-free grammar
PL/SQL
Dijkstra's algorithm
Complete metric space
Preprocessor
Algebraic structure