1
$\begingroup$

I know that the reduction relation is not symmetric. Writing formal proofs is the main core of the course I take on Theory of Computation. So I'm trying to prove that theorem. For that I need to show two languages $L_{1},L_{2}$ so $L_{1}\leq L_{2}$ and $L_{2}\not\leq L_{1}$. My textbook suggests to use $L_{1}\triangleq\Sigma^{*}$ and $L_{2}\triangleq HP$ and show that $L_{1}\leq L_{2}$ and $L_{2}\not\leq L_{1}$. So I need to split the proof into two sections:

  • Prove $L_{1}\leq L_{2}$ - Stuck. Not sure how to prove it formally.
  • Prove $L_{2}\not\leq L_{1}$. I want to use that $HP\not \in R$. So lets assume by contradiction that $HP\leq\Sigma^{*}$. This means there such function $f\,:\,\Sigma^{*}\to\Sigma^{*}$ between $HP$ and $\Sigma^*$. How to continue?

The definition of reduction: Given two languages $L_1$ and $L_2$, we say that there is reduction from $L_1$ to $L_2$ (and mark $L_1\leq L_2$) if there is a function $f\,:\,\Sigma^{*}\to\Sigma^{*}$ so:

  • $f$ is full - for each $x\in \Sigma^*$ there is one $y\in \Sigma^*$ so $f(x)=y$.
  • $f$ can be computed - there is a Turing machine that can compute $f$.
  • fulfils: $x\in L_1$ iff $f(x)\in L_2$.

As formality is important, how do I fill the blank spaces up to the full proof?

$\endgroup$
1
$\begingroup$

In order to show that $L_1 \leq L_2$, we need to come up with a computable function $f$ such that $x \in L_1$ iff $f(x) \in L_2$. Since $L_1 = \Sigma^*$, every $x$ satisfies $x \in L$, and so we need to find a computable function $f$ such that $f(x) \in L_2$ for all $x$. The easiest way to satisfy this is to choose $f$ to be a constant function.

In order to show that $L_2 \not\leq L_1$, we need to show that $f$ is a computable function that it is not the case that $x \in L_2$ iff $f(x) \in L_1$. That is, we need to show that for every computable $f$ there exists $x$ such that it is not the case that $x \in L_2$ iff $f(x) \in L_1$. Since $L_1 = \Sigma^*$, we always have $f(x) \in L_1$, so the only way in which "$x \in L_2$ iff $f(x) \in L_1$" can fail is if $x \notin L_2$. That is, we need to show that for every computable $f$ there exists $x$ such that $x \notin L_2$. The goal doesn't involve $f$, so it suffices to show that there exists $x$ such that $x \notin L_2$.

You take it from here.

$\endgroup$
2
  • $\begingroup$ For the first part: how to prove that if $f(x)=1$ then $x\in \Sigma^*$ iff $f(x)\in HP$? $\endgroup$
    – vesii
    May 15 at 14:29
  • $\begingroup$ I gave you enough hints. $\endgroup$ May 15 at 14:29

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.