Question

Show how to compute the descriptive complexity of strings K(x) with an oracle for A_TM.

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.

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.

• Construct Turning machine M’. We will construct M’ because we want all those transition which are in rejected state to be in accept state.

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›$

⇒Run$‹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.