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. Formal proof of uncomputability of K Theorem: There exist strings of arbitrarily large Kolmogorov complexity. Formally: for each natural number n, there is a string s with K(s) ≥ n. Proof: Otherwise all of the infinitely many possible finite strings could be generated by the finitely many programs with a complexity below n bits. Theorem: K is not a computable function. In other words, there is no program which takes any string s as input and produces the integer K(s) as output. The following proof by contradiction uses a simple Pascal-like language to denote programs; for sake of proof simplicity assume its description (i.e. an interpreter) to have a length of bits. Assume for contradiction there is a program function KolmogorovComplexity(string s) which takes as input a string s and returns K(s). All programs are of finite length so, for sake of proof simplicity, assume it to be bits. Now, consider the following program of length bits: function GenerateComplexString() for i = 1 to infinity: for each string s of length exactly i if KolmogorovComplexity(s) ≥ 8000000000 return s Using KolmogorovComplexity as a subroutine, the program tries every string, starting with the shortest, until it returns a string with Kolmogorov complexity at least bits, i.e. a string that cannot be produced by any program shorter than bits. However, the overall length of the above program that produced s is only bits, which is a contradiction. (If the code of KolmogorovComplexity is shorter, the contradiction remains. If it is longer, the constant used in GenerateComplexString can always be changed appropriately.) The above proof uses a contradiction similar to that of the Berry paradox: "The smallest positive integer that cannot be defined in fewer than twenty English words". It is also possible to show the non-computability of K by reduction from the non-computability