Language $L$ is trivial if $L=\varnothing$ or $L=\Sigma^*$. I'm trying to prove the following theorem:

If $L_1\in R$ and $L_2$ is non-trivial language then $L_1\leq L_2$.

If $L_2$ is non-trivial the $L_2\neq\varnothing$ and $L_2\neq\Sigma^*$. If I want to prove that $L_1\leq L_2$, then I need to show that there exists $f:\Sigma^*\to\Sigma^*$ which is total, can be calculated by a Turing machine and follows: $\forall x\in\Sigma^*$, $x\in L_1$ iff $f(x)\in L_2$. I also know that $L_1\in R$ then there is a turing machine $M_1$ that decides language $L_1$. But how do I continue from here? How $f$ should look like?


1 Answer 1


We know there are two $x_1,x_2\in \Sigma^*$ such that $x_1\in L_2$ and $x_2\notin L_2$, since $L_2$ is not trivial. Now, we will build the following reduction:

$f(x)=\cases{x_1 & $x\in L(M_1)=L_1$ \\ x_2 & otherwise}$

Notice that $f$ is computable: calculate $M_1(x)$, and output either $x_1$ or $x_2$ according to the answer you got.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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