Talk:Kolmogorov randomness

From Wikipedia, the free encyclopedia

Contents 1 Rename 2 False sentence 3 in the limit 4 Confusing and accuracy tags 5 Page Merge

[edit] Rename

Why Chaitin? This is Kolmogorov.

Agreed. How many say "Chaitin-Kolmogorov randomness" in the literature? - Gauge 07:45, 30 November 2006 (UTC)

Moved. --Trovatore 06:54, 16 December 2006 (UTC)

[edit] False sentence

I moved this from the main page.

In fact Chaitin's incompleteness theorem shows that though we know that 
most strings are random in the above sense, the fact that a specific string is 
random can never be proven, if the string's length is above a certain threshold. 

Provability depends on which axiom system you consider. In a system which includes as an axiom that a particular number is random, it is trivial to prove that the number is random. Thus the word never is wrong. There is something that could be said, but I don't see how to phrase it correctly. CMummert 05:00, 16 June 2006 (UTC)

That's kind of like saying you can't prove 2+2=4 because we could redefine 4 as 7. Absent any indication to the contrary, a statement like the one you removed assumes the standard axioms of arithmetic (ZF or whatever). And Chaitin has a specific definition of random that he uses. If you have a better criticism, make it, otherwise I think the sentence should go back.--agr 11:20, 16 June 2006 (UTC)

Chaitin does has a specific definition of random. However, there is not an accepted, final axiom system that he can point to and say that if anything will ever be provable then it can be proven in that axiom system. Just because a statement is not provable in ZFC does not mean that the statement is not provable, or that it will never be provable. In other words, there is a nontrivial chance that people in the future might adopt axioms that have not yet become widely accepted, and thus a nontrivial chance that extra statements about Kolmogorov complexity will become provable. If you replaced the phrase can never be proven with can never be proven in ZFC then the sentence would be correct, and I have no objection to that modified sentence. CMummert 14:13, 16 June 2006 (UTC)

The various incompleteness theorems generally cover any axiom system that includes ordinary arithmetic. See Gödel's incompleteness theorems. They all use pretty much the same tricks, so I presume this applies to Chaitin's results as well. --agr 19:37, 16 June 2006 (UTC)

Yes, just like Godel's theorem, Chaitin's theorem applies to any sufficiently strong system. Both Godel and Chaitin show that for each system there is some sentence that is not provable. Neither Godel nor Chaitin show that there is a sentence which is not provable in any system, because that is not true. For a more concrete example: Suppose that N is some fixed random number that ZFC does not prove to be random. Let ZFC' be ZFC plus the axiom that N is random. Then ZFC' proves N is random, so it is not literally true that N can never be shown to be random. That is my objection to the wording of the sentence that is quoted above; there is no one specific threshold that applies to all theories. CMummert 20:03, 16 June 2006 (UTC)

You would effectively be changing Chaitin's definition of random. Chaitin would still be able to say that there is no way to prove sufficiently large numbers are random except for the one listed in the axiom set. And how do you know the number you selected is random in the first place?--agr 20:38, 16 June 2006 (UTC)

Look at the sentence quoted in my first message. It claims that there is one fixed threshold. This is not true; the threshold depends on the particular axiomatic theory under consideration. That is why the quoted sentence is incorrect. I have no objection to a sentence that accurately states what Chaitin has proved. CMummert 01:23, 17 June 2006 (UTC)

I object to having to read through trivial qualifiers to find out something that's true under any sensible set of assumptions. Put the sentence back, and put the qualifiers in a footnote! --Brilliand 04:37, 19 April 2007 (UTC)

[edit] in the limit

Chaitin-Kolmogorov randomness distinguishes, at least in principle,
between numbers that are generated by [[pseudo-random number generator]]s
and true [[random number]]s.

Obvious, I think.

However pseudo-random number generators and true random numbers are
only distinguished in the limit.  Any finite sequence of numbers no matter
how apparently random can be generated by a large enough computer program
while conversely a truly random sequence of numbers can have an arbitrarily
long apparently non-random initial segment.

What does "in the limit" mean here?

Yes, any finite sequence of numbers can be generated by a large enough computer program, but so what? C-K randomness requires the program to be shorter than the sequence. So it is not true that every sequence turns out to be C-K random.

Yes, a truly random sequence of numbers can have an arbitrarily long non-random initial segment, but so what? The latter refers presumably to randomness in another sense of the word.

--Jdthood 14:16, 27 July 2006 (UTC)

[edit] Confusing and accuracy tags

I just added the 'confusing' and 'accuracy' tags because the definition currently listed can't be correct. And examples are needed to clarify. Tempshill 22:22, 19 September 2006 (UTC)

So far as I know, the definition currently listed is correct, though definitely left unelaborated. Why do you say it's not? I might remove the accuracy tag at some point. J.S. Nelson 01:18, 20 September 2006 (UTC)

This is a bit outside my field, but the provided definition meets my level of "good enough" for an initial English-language treatment. It would be worth going into greater depth later on. As I recall (I don't have a reference on-hand) the full definition is closer to:

"A string s is Chaitin-Komogorov random if there does not exist a computer program
of length n + k which will output it. (Where n is the length of the string
and k is a constant overhead dependent on the language).  This property is
unprovable in the general case."

I've also added a link to Kolmogorov complexity which should help address the definition and questions. Or perhaps we could simply build off of that article and simplify the definition to "A string s is Chaitin-Komogorov random if the Kolmogorov complexity of that string is greater than the length of s." GulDan 00:50, 16 October 2006 (UTC)

I recommend that this article be merged into Kolmogorov complexity. The definition can be much shorter and well-motivated in that context than it is here. - Gauge 07:45, 30 November 2006 (UTC)

[edit] Page Merge

I definitely think this page should be merged with something, as it contributes little and people may end up here instead of other more useful articles. But there are several possible candidates: Kolmogorov complexity, algorithmic information theory, algorithmically random sequence, and possibly others. Also, the page naming conventions don't seem to follow the conventions I'm used to - perhaps this is a math vs. computer science thing? Althai (talk) 22:22, 8 June 2007 (UTC)

I Agree; I would also suggest merging it with Kolmogorov complexity. -- Kuteni 13:17, 13 August 2007 (UTC)