So, any string can be made by some programs, each program has a mathematical complexity of K, we say each string has a K of the program with the smallest K that makes that string. If knowing a string gives us a precise value for K, knowing a precise value for K lets us generate some strings that are more complex than K but no more complex than any other strings higher than K. Some strings are random, and have Ks that are strings more complex than the strings they describe. For some string the shortest program that makes it will be “The shortest string with K greater than K1”, and “The shortest string with K greater than K1″ is a program with a low K. Yet that string was chosen by the program because it had a higher K than “the shortest string with complexity greater than K” does, so the string thus delineated “really” has a very small K, not a high one, so it must be unselected, and thus unselected it “really” has a high K again, falsifying that program’s selection of anything else.
The problem is that programs can be made out of self referencing words that select their components and targets based on what other programs are doing.
Can’t we still calculate K in a mathematical universe forbidding self referencing sentences? In our world we are comfortable saying K1 is greater than K2 if and only if we know it is orders of magnitude greater. What would be wrong with saying K1 is greater than K2 because K1=100 and K2=10, where K is complexity in the mathematical world with the extra axiom?
″...the Kolmogorov complexity of a pattern is the size of the program code of the shortest Turing machine that produces the pattern as an output, given unlimited tape as working memory.”
I am confused. If each pattern gets its own shortest program to describe it, why can’t complexity numbers be computed (wikipedia says they can’t be)?
I had thought that the reason they could not be was that each string has its own best program as a prefix that minimizes the number of bits needed to express the prefix plus the string, and there was no neutral way to compare between similarly complex strings since each might be shorter under its personal program than the other under that same program.
Thanks for the site!