How to prove that the reduction relation is not symmetric

Question

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?

Answer 1

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.