Explore BrainMass

Explore BrainMass

    Automata and Computability

    Not what you're looking for? Search our solutions OR ask your own Custom question.

    This content was COPIED 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 March 4, 2021, 7:38 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 ...