Note: one might think of sequence guessing as task of minimizing Kolmogorov complexity. That’s not quite so, sequences are too short, shorter than the generators. Consider sequence 2,3,5,7,11,? . Obviously the answer on IQ test would be 13 (primes). Good luck writing primes generating program that is simpler than this sequence itself, though. (and of course the length of program will be very dependent on the machine being used)
I’m having trouble understanding this part. I thought that “predicting the next number by minimizing Kolmogorov complexity” meant “finding the shortest program that would generate that sequence and the next bit”, not “finding a program shorter than that sequence.” Can you explain?
Also, to clarify. Kolmogorov’s complexity of printing out primes vs printing this exact sequence followed by ones, is a matter of language. One could imagine a language where there’s 1-symbol command that prints primes. Or a language that is like actual programming languages, where you have to implement printing of primes.
I’m having trouble understanding this part. I thought that “predicting the next number by minimizing Kolmogorov complexity” meant “finding the shortest program that would generate that sequence and the next bit”, not “finding a program shorter than that sequence.” Can you explain?
It is generally assumed that the program that returns a predefined sequence and then always “1” is negligibly longer than that sequence.
Precisely.
Also, to clarify. Kolmogorov’s complexity of printing out primes vs printing this exact sequence followed by ones, is a matter of language. One could imagine a language where there’s 1-symbol command that prints primes. Or a language that is like actual programming languages, where you have to implement printing of primes.