Show that the function K (x) is not a computable function.© BrainMass Inc. brainmass.com September 21, 2018, 12:40 pm ad1c9bdddf - https://brainmass.com/computer-science/algorithms/automata-and-computability-113199
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