In the computer science subfield of algorithmic information theory the Chaitin constant or halting probability is a construction by Gregory Chaitin which describes the probability that a randomly generated program for a given model of computation or programming language will halt. It is usually denoted . Computer science is the study of information and computation. ... In computer science, algorithmic information theory is a field of study which attempts to define the complexity (aka descriptive complexity, Kolmogorov complexity, Kolmogorov-Chaitin complexity, or algorithmic entropy) of a string as the length of the shortest binary program which outputs that string. ... Gregory J. Chaitin (born 1947) is an American contemporary mathematician and computer scientist. ... The word probability derives from the Latin probare (to prove, or to test). ... In ordinary language, the word random is used to express apparent lack of purpose or cause. ... Computer code (HTML with JavaScript) in a tool that uses syntax highlighting (colors) to help the developer see the function of each piece of code. ...

It is a normal and transcendental number which can be defined but cannot be computed. This means one can prove that there is no algorithm which produces the digits of . In mathematics, a normal number is, roughly speaking, a real number whose digits show a random distribution with all digits being equally likely. ... In mathematics, a transcendental number is any real number that is not algebraic, that is, not the solution of a non-zero polynomial equation with integer (or, equivalently, rational) coefficients. ... A real number a is first-order definable in the language of set theory, without parameters, if there is a formula φ in the language of set theory, with one free variable, such that a is the unique real number such that φ(a) holds (in the von Neumann universe V). ... In mathematics, theoretical computer science and mathematical logic, the computable numbers, also known as the recursive numbers, are the subset of the real numbers consisting of the numbers which can be computed by a finite, terminating algorithm. ... Flowcharts are often used to represent algorithms. ...

The proof of 's uncomputability relies on an algorithm, which, given the first digits of , solves Turing's halting problem for programs of length up to . Since the halting problem is undecidable, can not be computed. In computability theory the halting problem is a decision problem which can be informally stated as follows: Given a description of a program and its initial input, determine whether the program, when executed on this input, ever halts (completes). ... In logic, a decision problem is determining whether or not there exists a decision procedure or algorithm for a class S of questions requiring a Boolean value (i. ...

As depends on the program encoding used, it should be called Chaitin's construction instead of Chaitin's constant when not referring to any specific encoding.

Definition

To define formally, we first need to fix a (Turing-complete) model of computation, for instance Turing machines or Lisp or Pascal programs. (Here, program means the concatenation of executable code and input.) We then need to specify an instantaneous encoding of programs as bit strings. This encoding has the property that if w encodes a syntactically correct program, then no proper prefix of w encodes a syntactically correct program. Given an arbitrary Turing machine M, this can always be achieved by using the following algorithm: An artistic representation of a Turing Machine . ... Lisp is a family of computer programming languages with a long history and a distinctive fully-parenthesized syntax. ... Pascal is an imperative computer programming language, developed in 1970 by Niklaus Wirth as a language particularly suitable for structured programming. ... This article needs to be cleaned up to conform to a higher standard of quality. ... This article is about the unit of information. ...

1. Read a bit of the input z.
2. Before reading any more, simulate M on all possible extensions y (including the empty one) of z simultaneously until some extension halts, if ever.
3. If y = z, then halt and output M(y); otherwise go to step 1.

Let P be the set of all programs which halt. is then defined as:

This is an infinite sum which has one summand for every syntactically correct program which halts. |p| stands for the length of the bit string of p. The above requirement that programs be prefix-free ensures that this sum converges to a real number between 0 and 1. In mathematics, a series is often represented as the sum of a sequence of terms. ... In mathematics, the real numbers are intuitively defined as numbers that are in one-to-one correspondence with the points on an infinite line—the number line. ...

Notes

It can then be shown that represents the probability that a randomly produced bit string will encode a halting program. This means that if you start flipping coins, always recording a head as a one and a tail as a zero, the probability is that you will eventually reach the encoding of a syntactically correct halting program.

If you fix, in addition to the computation model and encoding mentioned above, a specific consistent axiomatic system for the natural numbers, say Peano's axioms, then there exists a constant N such that no bit of after the N-th can be proven to be one or zero within that system. (The constant N heavily depends on the encoding choices and does not reflect the complexity of the axiomatic system in any way.) This is an incompleteness result akin to Gödel's incompleteness theorem and Chaitin's own result mentioned under algorithmic information theory. In mathematics, an axiomatic system is any set of axioms from which some or all axioms can be used in conjunction to logically derive theorems. ... Natural number can mean either a positive integer (1, 2, 3, 4, ...) or a non-negative integer (0, 1, 2, 3, 4, ...). Natural numbers have two main purposes: they can be used for counting (there are 3 apples on the table), or they can be used for ordering (this is... In mathematics, the Peano axioms (or Peano postulates) are a set of second-order axioms proposed by Giuseppe Peano which determine the theory of arithmetic. ... In mathematical logic, Gödels incompleteness theorems are two celebrated theorems proven by Kurt Gödel in 1931. ... In computer science, algorithmic information theory is a field of study which attempts to define the complexity (aka descriptive complexity, Kolmogorov complexity, Kolmogorov-Chaitin complexity, or algorithmic entropy) of a string as the length of the shortest binary program which outputs that string. ...

is uncompressible (also known as irreducible or algorithmically random). This means that in a particular programming language, a program which will write the first n bits of for that language must be at least n bits itself (including any input data). In computer science, data compression or source coding is the process of encoding information using fewer bits (or other information-bearing units) than a more obvious representation would use, through use of specific encoding schemes. ...

Calculation of the start of a Chaitin

Cristian S. Calude, Michael J. Dinneen, and Chi-Kou Shu [1] have calculated the first 64 bits of a Chaitin _U for a particular machine: they in fact calculated 84 bits, but only the first 64 are reliable. These are (in binary) This article is about the unit of information. ... The binary numeral system (base 2 numerals) represents numeric values using two symbols, typically 0 and 1. ...

0.0000001000000100000110001000011010001111110010111011101000010000...

Translating this to decimal gives a number which starts The decimal (base ten or occasionally denary) numeral system has ten as its base. ...

0.0078749969978123844...

However, they also confirm the more important strong result in the opposite direction mentioned above, that in general only a finite number of digits of may be calculated or, equivalently, that from some point in the binary expansion onwards none of the digits of may be calculated.

External links

• Omega and why maths has no TOEs article based on one written by Gregory Chaitin which appeared in the August 2004 edition of Mathematics Today, on the occasion of the 50th anniversary of Alan Turing's death.
• Chaitin's construction and Mortality Burton MacKenzie speculates if Omega has implications for mortality, deterministic universes, and free will.