Question

Use the result of Problem 6.21 to give a function f that is computable with an oracle for A_TM, where for each n,f(n) is an incompressible string of length n.

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.

We have already computed descriptive complexity of string K(x) with an oracle for A_TM.

We have to know about the definition of incompressible string of length n.

Let as assume (x)be any string.

So, if (x)don’t have description smaller than itself, which means (x) is incompressible.

Let f be a function which is computable by oracle for A_TM.

Now we will calculate f(n) for each value of n. For this we will construct oracle Turing Machine M which work as:

• Enumerate all strings (x) of length
• Calculate K(x) for each x by using A_TM
• If we get (x) =f(n) and K(x) ≥ Length (x)

Output: (x)

Halt

Here, K(x) ≥ Length(x) signifies that we got a string which is greater than its description.