I came across this problem that I could not figure out... For every language $A$, there is supposed to be a language $B$ such that:

$$ A \leq_T B $$


$$ B \not \leq_T A $$

If it is $A \leq_TB$ and $B \leq_T A$, this is easy since we can just let $B := \bar{A}$, but for the above I could not think of anything. Any help ?


There are a few ways to approach this.

You can use a counting argument to show that for every $A$ there exists $B$ such that $B\nleq_T A$. Let $L_A=\{B| B\le_T A\}$ denote the set of all languages reducible to $A$. Show that $f:L_A\rightarrow \mathbb{N}$ that maps languages $B\in L_A$ to $n$ such that $M_n$ is a reduction from $B$ to $A$ is an injection, and conclude that there exists a language outside of $L_A$. Next, you want to make it comparable to $A$. We can get such a language with the join operator:

$A\sqcup B=\{0w|w\in A\}\cup\{1w|w\in B\}$.

I leave it to you to show that $A\sqcup B$ is the least upper bound for $A,B$, i.e. $A,B\le_T A\sqcup B$ and additionally for every $L$ such that $A,B\le_T L$ we have $A\sqcup B\le L$ (you only care about the former). Show that if $B\nleq_T A$ then $A\sqcup B\nleq_T A$.

Another way to prove this is to use the jump operator. We need to introduce the notion of oracle machines, and then show that $B=\left\{\left(M^A,w\right)| \text{$M^A$ halts on $w$}\right\}$ is a strictly harder language. The proof is identical to the undecidability of the standard halting problem, only that now we show the stronger property that no machine with oracle access to $A$ can decide $B$.

You can also directly construct such a language via diagonalization. define $B=\left\{n | M_n(n)\notin A\right\}$. We constructed $B$ such that any computable function $M_n$ fails to be a reduction from $B$ to $A$ on at least one input (specifically, the encoding of the reduction). You can now use the join operator to make them comparable.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.