Explore BrainMass

Automata and Computability

Show that the function K (x) is not a computable function.


Solution Preview

Please see the attached file.

In other words, there is no program which takes a string s as input and produces the integer K(s) as output. We show this by contradiction. Suppose there is a program
function KolmogorovComplexity(string s)
that takes as input a string s and returns K(s). Now consider the program
function GenerateComplexString(int n)
for i = 1 to infinity:
for each string s of length exactly i
if ...