Question

Prove that there exist two languages that are Turing-incomparable—that is,A '_TB where B'_T A.

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., TM 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.

Two languages A are B said to be Turing incompatible if language A is not Turing Compatible with language B and vice versa.

In this question, we don’t have any Turing Machine that can work as Oracle Turing Machine to detect decidability and Turing reducibility.

So there is no language from A and B which could be replaced by any intermediate language.

Also, Turing Machine cannot be constructed until decidability is proved.

Thus, no solution can be defined in our case to prove decidability of two languages so that language A and B are not Turing Reducible.

This proves that A and B is Turing Incomparable, A ' _TB and B'_TA.