Question

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

Short answer

The given statement is proved.

Step-by-step solution

Turing Recognizable

A language L is said to be Turing Recognizable if and only if there exist any Turing Machine (TM) which recognize it i.e., Turing Machine halt and accept strings belong to language L and will reject or not halt on the input strings that doesn’t belong to language L.

Proof of the statement.

Let as assume y_a be the lexicographical 1^st string s which satisfy n < K(y)

Let us assume to have Turing Machine M in which if the input is ‘n’, then we are able to generate binary strings x₀, x₁, x₂.....

So, M will work as follows:

• M compute K(x_i)
• If K(x) > n
• Output: x_i

Halt

• If Not Halt

Then check other lexicographical string x_i+1

So, TM M will encounter a string x which will satisfy K(x) > n

For input n, the output generated is y_a whereas the input string length would be: log₂(n). For all n K(x)>n, length would be n < log₂(n) + c

But this is not true for sufficiently large value of n. This is contradicting as M will never compute K(x_i), which clearly states that K(x_i) is not computable function.