Explore BrainMass

Automata and Computability

This content was STOLEN from BrainMass.com - View the original, and get the already-completed solution here!

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

© BrainMass Inc. brainmass.com December 19, 2018, 11:13 pm ad1c9bdddf


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 ...