91Ó°ÊÓ

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.

It is to know that Descriptive Complexity of strings K(x) is also known as Kolmogorov complexity.

In this question we need to design an algorithm which on taking input x, can compute descriptive complexity of strings K(x) by using oracle(a subroutine) for A_TM.

So we have to design the algorithm in such a way that on input , the oracle will return one if accepts w. If not accepts, then output would be zero.

Algorithm for computing K(x).

• $M=oninput‹M,x›$
• We will go in lexicographical order to each string s, and resolve these string as$‹M\text{'},x›$

If s is not able to resolve(parse), then we will move to next string.

If M’ accepts$‹M\text{'},x›$

⇒M halts on w

• Now, we will query A_TMon input $‹M\text{'},x›$
• If A_TM accepts $‹M\text{'},x›$

⇒R³Ü²Ô$‹M\text{'},x›$

If M halts on input w when x is written on tape.

Output: Length[s]

This will give us length of shortest description.

By this way we can compute descriptive complexity of strings K(x) with an oracle for A_TM.