Suggested languages for you:

Americas

Europe

Problem 16

# Prove that there exist two languages $$A$$ and $$B$$ that are Turing-incomparable- that is, where $$A \not{Z} \mathrm{~T} B$$ and $$B \not \mathrm{T} A$$.

Expert verified
We proved the existence of two Turing-incomparable languages, A and B, using the diagonalization argument. We showed that there are uncountably many languages in P({0, 1}), but only countably many Turing-decidable languages. By selecting a non-Turing-decidable language A and a language B from the complement of the Turing degree of A (P({0, 1}) - deg(A)), we demonstrated that neither A ≤T B nor B ≤T A holds, thus establishing that A and B are Turing-incomparable.
See the step by step solution

## Step 1: Understand the Definitions

Before we proceed, we need to recall the definitions of Turing reducibility and Turing degrees. Turing reducibility (≤T): A language A is Turing reducible to language B, denoted as A ≤T B, if there exists a Turing machine M with an oracle to B that can decide A. Turing degree: A Turing degree is a set of languages such that all languages in the set are Turing equivalent. Two languages A and B are Turing equivalent if A ≤T B and B ≤T A. Equivalently, Turing degree is an equivalence class of languages under Turing equivalence relation. Turing-incomparable: Two languages A and B are Turing-incomparable if neither A ≤T B nor B ≤T A holds.

## Step 2: Use diagonalization argument

We will use diagonalization argument to show that two Turing-incomparable languages exist. Start by considering the set of all Turing-decidable languages, denoted by TDL. Since there are countably many Turing machines, there are countably many Turing-decidable languages (each decidable language corresponds to the language accepted by a specific Turing machine). Now, consider the set of all languages over the alphabet {0, 1}, denoted by P({0, 1}). There are uncountably many languages in P({0, 1}), because the set of all languages over {0, 1} has the same cardinality as the power set of natural numbers, which is uncountable (proven by Cantor's theorem).

## Step 3: Prove the existence of Turing-incomparable languages

Since there are countably many Turing-decidable languages and uncountably many languages in P({0, 1}), there must exist some languages in P({0, 1}) that are not Turing-decidable (uncountably many languages minus countably many languages leaves uncountably many languages). Let A be one of these non-Turing-decidable languages. Now, consider the Turing degree of A, denoted by deg(A). By definition, all the languages in deg(A) are Turing equivalent to A, so none of the languages in deg(A) can be Turing reducible to any of the Turing-decidable languages. Next, consider the complement of deg(A), denoted by P({0, 1}) - deg(A). Since deg(A) is only a proper subset of P({0, 1}), P({0, 1}) - deg(A) must contain some languages. Let B be one of those languages. Now we have two languages, A and B, where: - A is not Turing-decidable, so A is not Turing reducible to any Turing-decidable language. - B belongs to P({0, 1}) - deg(A), so B is not Turing-reducible to A. Thus, we have found two languages, A and B, such that A and B are Turing-incomparable, which means A ∉T B and B ∉T A.

We value your feedback to improve our textbook solutions.

## Access millions of textbook solutions in one place

• Access over 3 million high quality textbook solutions
• Access our popular flashcard, quiz, mock-exam and notes features

## Join over 22 million students in learning with our Vaia App

The first learning app that truly has everything you need to ace your exams in one place.

• Flashcards & Quizzes
• AI Study Assistant
• Smart Note-Taking
• Mock-Exams
• Study Planner