- #1
Fooality
- 196
- 42
Hey, has anyone here done Kolmogorov complexity? I hadn't, and I was just reading the Wikipedia page to start learning it. The core concept makes sense: The Kolmogorov complexity for a a string s, K(s) is equivalent to the length of a program that generates that string (It can be any math object, not just strings.) So a string that's long but with a simple pattern behind it will have a short program and small K, where a random string will have larger K.
Then I got to this proof, which claims to show the incomputability of K. Its a proof by contradiction, here given in pseudo Python, and available on the Wikipedia page in pseudo Pascal.
This code enumerates through the set of all strings as s, until it finds the first one with K(s) > than some high number (in this case 8000000000) and outputs it. Since this program is shorter than 8000000000, its a contradiction, and they used it to say that K(s), (here written as KolmogorovComplexity(s)) must not be computable.
The problem is, using a similar dirty trick, I can construct a KolmogorovComplexity function that clearly is computable. The idea behind it is to generate and run all possible programs and return the first one that produces the string. It looks like this:
The LaunchOnNewVirtualProcessor runs Execute on a "virtual processor", and exploits the fact that any Turing machine can simulate any other number of Turing machines, so if the given code doesn't halt, it slows it down but the whole process keeps going. (Its not assumed all every number representing a program generates a number or halts) So long as the strings are finite, as they are in their function, and the programs that output strings halt (which is totally reasonable), than this works, and everything becomes incredibly confusing.
So what am I getting wrong, there's got to be something, because their proof seems totally sound, the more I go over it in my mind.
edit: Changed my code, can't assume that the process which ends first has the shortest code.
Then I got to this proof, which claims to show the incomputability of K. Its a proof by contradiction, here given in pseudo Python, and available on the Wikipedia page in pseudo Pascal.
Python:
function GenerateComplexString():
for i in range(infinity):
for each string s of length exactly i:
if KolmogorovComplexity(s) >= 8000000000
return s
The problem is, using a similar dirty trick, I can construct a KolmogorovComplexity function that clearly is computable. The idea behind it is to generate and run all possible programs and return the first one that produces the string. It looks like this:
Python:
function Execute(code, s):
string output = run(code)
if output = s:
addToPotentialAnswers(len(code), code)
function KolmogorovComplexity(s):
for i in range(infinity):
LaunchOnNewVirtualProcessor(Execute, (ConvertToBinary(i), s))
The LaunchOnNewVirtualProcessor runs Execute on a "virtual processor", and exploits the fact that any Turing machine can simulate any other number of Turing machines, so if the given code doesn't halt, it slows it down but the whole process keeps going. (Its not assumed all every number representing a program generates a number or halts) So long as the strings are finite, as they are in their function, and the programs that output strings halt (which is totally reasonable), than this works, and everything becomes incredibly confusing.
So what am I getting wrong, there's got to be something, because their proof seems totally sound, the more I go over it in my mind.
edit: Changed my code, can't assume that the process which ends first has the shortest code.
Last edited: