Chaitin’s Constant Error

Chaitin’s ‘constant’, often referred to as Chaitin’s Omega ‘number’, is a notion described by Gregory Chaitin, who works tirelessly at self-promotion (see the list of books and articles below). According to Chaitin, his Omega definition defines an irrational number in terms of an infinite sequence of the digits 0 and 1, where the digits are determined on the basis of whether a theoretical computer will stop or not stop when set to run programs of a given computer language (The Halting problem is the problem of determining if, given any computer program, whether a theoretical computer with unlimited memory will terminate, or never terminate when it runs the program, see also The Halting Problem).

The details of the Omega definition are not important here. It is sufficient to know that the definition is such that there is no method (even in principle) that can continue to determine, on the basis of the Omega definition, the digits of the binary expansion of the ‘number’ that is claimed to be given by the Omega definition (note that different computer languages will result in different sequences of 0s and 1s, but this does not affect the overall argument). Chaitin claims that his Omega number is “algorithmically irreducible”, (Footnote: Definition of Algorithmically Irreducible as given in the book Information, Randomness & Incompleteness: Papers on Algorithmic Information by Gregory Chaitin, Vol. 8. World Scientific, 1990:
The main concept of algorithmic information theory is that of the program-size complexity or algorithmic information content of an object (usually just called its “complexity”). This is defined to be the size in bits of the shortest computer program that calculates the object, i.e: the size of its minimal algorithmic description. Note that we consider computer programs to be bit strings and we measure their size in bits. If the object being calculated is itself a finite string of bits, and its minimal description is no smaller than the string itself, then the bit string is said to be algorithmically incompressible, algorithmically irreducible, or algorithmically random. Such strings have the statistical properties that one would expect. For example, 0’s and l’s must occur with nearly equal relative frequency; otherwise the bit string could be compressed. An infinite bit string is said to be algorithmically incompressible, algorithmically irreducible, or algorithmically random if all its initial segments are algorithmically random finite bit strings.) and that because of that, this Omega is a tremendously important concept. He has continued to proclaim the importance and significance of this notion over the past 40 years (besides proclaiming his own importance for discovering this Omega number).

But, amazingly, despite his banging on and on relentlessly about this Omega number, (Footnote: Chaitin has published at least 20 articles and 5 books based on this Omega number (see the lists on this page) and has given numerous talks on it, many of them now on YouTube. He has also published many other articles, and given talks, that refer to the importance of his Omega number.) Chaitin has never actually produced a valid proof that this Omega number is, in fact, algorithmically irreducible - as will be demonstrated below.

We can note that Chaitin’s claim is little more than a rehashing of an idea conceived many years previously by Alan Turing, who claimed to have proved that he had defined a number that must “exist” but which cannot be computed by any computer. But it is easy to show that both Turing and Chaitin make the same logical error in their claim that they have defined a number that is uncomputable, see Turing’s “Uncomputable” numbers for an analysis of Turing’s claim.

We can analyze Chaitin’s Omega number in two ways:

1. We can assert that for any given computer program, there is a truth value for the proposition “A theoretical computer with limitless memory will either stop or not stop when set to run the specified program”, even if we can never determine it. This is the Platonist stance, and this is the stance that Chaitin adopts.
2. We do not assume that there is necessarily a truth value for the proposition “A theoretical computer with limitless memory will either stop or not stop when set to run the specified program”. This is the non-Platonist stance.

As will be shown below, it is actually immaterial which stance one takes when considering the question as to whether Chaitin has actually provided a valid proof that his Omega number is algorithmically irreducible. To show this, we will consider both stances, taking Chaitin’s Platonist stance first.

Case 1: The Platonist stance (Chaitin’s stance)

Case 2: The non-Platonist stance

Summary

In summary, regardless of whether one applies the Platonist or non-Platonist interpretation of the Omega ‘number’, nothing that Chaitin has written in 40 years of relentless promotion of his Omega concept has provided a proof that he has actually defined an infinite sequence of digits for which there can be no finite algorithm that can generate that sequence.

For an analysis of the similar claim by Turing that he had defined a number that must “exist” but which cannot be computed by any computer, see Turing’s “Uncomputable” numbers.

Notes

Panu Raatikainen writes in a review of two of Chaitin’s books, Exploring Randomness and The Unknowable:

“Chaitin’s claims are nearly megalomaniacal. What else can one think of statements such as the following? ‘AIT will lead to the major breakthrough of 21st century mathematics, which will be information-theoretic and complexity based characterizations and analyses of what is life, what is mind, what is intelligence, what is consciousness, of why life has to appear spontaneously and then to evolve.’ (Exploring Randomness, p. 163).”

He also says in the same review:

“It has been shown conclusively (see [the references below]) that Chaitin’s philosophical interpretations of his work are unfounded and false; they are based on various fatal confusions.”

There are a number of published papers that are critical of Chaitin’s papers on incompleteness proofs that are based on information-theoretic complexity (see also the paper PDF A Fundamental Flaw in Incompleteness Proofs by Gregory Chaitin, which shows that Chaitin’s proof depends on an unproven assumption):

• Germano D’Abramo. “PDF On the information-theoretic approach to Gödel’s incompleteness theorem”. 2002, Arxiv 0211078
• Torkel Franzen. Gödel’s Theorem: An Incomplete Guide to its Use and Abuse. A K Peters, 2005. ISBN: 1568812388.
• Michiel Van Lambalgen, “PDF Algorithmic information theory”, Journal of Symbolic Logic 54 (1989), pp. 1389–1400.
• Panu Raatikainen, “PDF On interpreting Chaitin’s incompleteness theorem”, Journal of Philosophical Logic 27 (1998), pp. 269–586.
• Panu Raatikainen, “PDF Algorithmic information theory and undecidability”, Synthese 123 (2000), pp. 217–225.

Some books by Chaitin based on his Omega number

Note: much of the content of these books is rehashed from previously published articles

Some articles by Chaitin based on his Omega number