Show that the function K (x) is not a computable function.© BrainMass Inc. brainmass.com December 19, 2018, 11:13 pm ad1c9bdddf
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