906 - From the spirit of Chaitin’s letter to the proper Kolakoski word

N. Lygeros

  • Post Category:Articles

According to the mentation developed by K. Gödel, A. Turing and Y. Matiajevic, which has lead to G. Chaitin’s discovery i.e. the number Ω through the notions of incompleteness and undecidability, we are in possession of an immense freedom in the axiomatic field. Nevertheless the drawback of this approach is that it is essentially based on constructions of artificial examples. This situation somewhat resembles that of the transcendantal numbers which are omnipresent in the real numbers according to G. Cantor’s famous theorem, and are so difficult to find. It is true that Liouville has quickly found examples of transcendantal numbers such as the so-called Liouville number (). Still, the true contribution of Cantor’s ideas was only perceived with the demonstration of the transcendance of the numbers π and e i.e. no artificial numbers which belong to the mathematical tradition.

Thus, on the footsteps of the ideas of K. Gödel who had suggested Riemann’s hypothesis as an unprovable entity, G. Chaitin proposes to consider Möbius’ function to be a possible attack. In addition, from da Calvo and Dovia’s works who have shown that if ZFC is consistent then P=NP is consistent with ZFC, G. Chaitin proposes also PNP as another unprovable candidate. In this spirit we propose an example which comes from the combinatorial world and especially from the theory of words. To define Kolakoski’s word we need only very few things : an alphabet with only two letters 1 and 2, the notion of block which is a concatenation of the identical letters and the definition of the word: the value of the nth letter is the length of the nth block. If we call wK the word beginning with the letter 2, it is trivial to see that the one which begins with the letter 1 is written 1 wK. Moreover, there obviously exists an algorithm which enables to decide whether the nth value of wK is a 1 or a 2. On the other hand if we look for the mean length of the nth block we enter a much more complex domain. Indeed the computation shows with arbitrarily high yet finite precision the value to be 3/2 yet without any available proof. It is true that this fact is explained by the equiprobability of the apparition of the letters 1 and 2. Nevertheless a curious result is hidden in the repartition of these letters. On one hand we do not know how to prove that the ratio of the number of 1s by the total number has a limit. On the other hand Chvátal has only managed to prove the following result: if the limit exists then it is very close to 1/2.

For now we do not know the complexity of the Kolakoski word. Thus, the data suggests that it could be possible to consider the equality of the possible limit to 1/2 as a candidate for a natural unprovable proposition, since the autoreferent structure of the Kolakoski word evokes K. Gödel’s approach to open the way to axiomatic freedom.