Explore BrainMass

Automata and Computability

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

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


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