Talk:Chaitin's constant
|
|
(The constant N heavily depends on the encoding choices and does not reflect the complexity of the axiomatic system in any way.)
Where did you get this terrible idea?.... Do you know the invariance theorem? Do you know Theorem C in AIT that shows the relation between the axiomatic complexity of a FAS to the number of digits that can be proven? exa 16 Sep, 2004
- ... then there exists a constant N such that no digit of Ω after the N-th can be proven to be one or zero within that system.
Is this true? It seems like this states that there are at most a finite number of Turing machines that can be proven to either halt or not halt (given some system of enumeration, etc.). Chas zzz brown 02:06 Feb 5, 2003 (UTC)
Ooops! In the words of emily latella, "never mind". I misread that the nth digit of Ω was 1 iff Turing machine n halts. Chas zzz brown 09:00 Feb 5, 2003 (UTC)b
I have rewritten the introduction to this article and added some headings to divide it into sections. I am not sure if this belongs to algorithmic information theory so perhaps someone can put it in the right category. MathMartin 17:44, 20 Jul 2004 (UTC)
What does the statement "Ω is uncompressible" mean? Is compressible number defined anywhere in the Wikipedia? - Mike Rosoft 16:55, 8 Dec 2004 (UTC)
Oops! I thought the link I had supplied to Data compression would clear it up. It means that it is impossible to supply a program + infinite "compressed" sequence such that for any <math>n<math>, the program can return the first <math>n<math> bits of Ω using the first <math>f(n)<math> bits of the compressed sequence, and for any <math>k<math> there exists <math>n_0<math> such that for <math>n>n_0<math>, <math>f(n)
I have included a summary of the definition for incompressible number. Rattle 09:00, 1 Jun 2005 (UTC)