Chaitin's constant

The Chaitin constant (or Chaitin omega number or stopping probability) is the probability that a randomly chosen program will stop correctly a given Turing machine. Being a probability, it must be a number between 0 and 1.

Let P be the set of all programs that stop, and |p| be the bit size of a program p, Ω is defined as follows:

Ω Ω =␡ ␡ p한 한 P2− − 日本語p日本語{displaystyle Omega =sum _{pin P}2^{-associatedp}

History

Gregory Chaitin, in the 1960s and almost at the same time as Andrei Kolmogorov, established the following definition of an algorithmically random object: that which cannot be generated by a program shorter than itself. He also showed that any algorithmically random number was normal (regardless of the chosen base, all digits appear with the same frequency, as if they had been generated by successive rolls of a die).

Remember that a Turing machine is a simple computer, but that all computable tasks can be computed with it.

Properties

• This constant is not computable. It is possible to know or get the first digits, but from a certain decimal (which depends on the chosen encoding) it is not possible to know or get more.
• It is a real b-normal and algorithmically incompressible number, or in an equivalent terminology is a somewhat rhythmic random number. This is to say much more than it seems to be in plain sight. He assumes that he cannot compress in a shorter program than himself. An irrational number such as π or e, despite having infinity non-recurrent decimals, can be correctly generated until the decimal enesimo by a program of very few lines that, executed on a computer, will write the successive decimals. Therefore it is compressible, and it is not algorithmically random.

Not only can this number not be calculated, but you can never know what its bits are, because that information, as Chaitin said, "is mathematically incompressible and incomprehensible, the words are very similar. To obtain the first n bits of Ω, a theory of n bits is needed, of equal complexity to the phenomenon to be studied. That means that nothing is gained by reasoning".

There are very short programs that generate π π {displaystyle pi } with its infinite decimals, then the intrinsic complexity (inherent and characteristic of the element) of π is small; it is not algorithmically random. Mandelbrot's set, with its infinite collections and beautiful volutes, is also generated by very short programs, therefore has very little complexity in the sense of Kolmogórov.

Our Ω has no structure: it is pure chance despite being perfectly defined.

Kolmogorov has devised the concept of complexity (amount of information) of an object as the number of bits of the most concise program capable of generating it.