Editing Kolmogorov complexity (section)

==== A naive attempt at a program to compute ''K'' ====

At first glance it might seem trivial to write a program which can compute ''K''(''s'') for any ''s'', such as the following:

 '''function''' KolmogorovComplexity('''string''' s)
     '''for''' i = 1 '''to''' infinity:
         '''for each''' string p '''of''' length exactly i
             '''if''' isValidProgram(p) '''and''' evaluate(p) == s
                 '''return''' i

This program iterates through all possible programs (by iterating through all possible strings and only considering those which are valid programs), starting with the shortest. Each program is executed to find the result produced by that program, comparing it to the input ''s''. If the result matches then the length of the program is returned.

However this will not work because some of the programs ''p'' tested will not terminate, e.g. if they contain infinite loops. There is no way to avoid all of these programs by testing them in some way before executing them due to the non-computability of the [[halting problem]].

What is more, no program at all can compute the function ''K'', be it ever so sophisticated. This is proven in the following.