0
$\begingroup$

I am having troubles in understanding why this proof is done like that. Why do we need to make a reduction to Ld which isn't even in RE to disprove Lu being rec?

And why does the book (Automata Theory, Languages and computation by Hopcroft, Motwani, ullman) constructs a machine for Ld to get a contradiction?

This is the machine that I dont understand at all

Thanks everybody in advance

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

The reduction is not done to the diagonalization language, but from the diagonalization language. The difference is very important here.

The idea of reduction is that the fact that there is a reduction from $A$ to $B$, noted $A\leqslant B$, can be translated as:

if we know how to solve $B$, then we know how to solve $A$.

Another interpretation could be:

if we cannot solve $A$, then we cannot solve $B$.

The principle of such a reduction is the following: from an instance $x$ of the problem $A$, construct an instance $y$ of the problem $B$ such that $x\in A\Leftrightarrow y \in B$.

In the reduction in HMU, the proof gives a reduction from $L_d$ to $\overline{L_u}$. Since the book has previously proved that $L_d$ is not recursive (indeed, it is not even recursively enumerable), the reduction $L_d\leqslant \overline{L_u}$ proves that $\overline{L_u}$ is not recursive, hence $L_u$ is not recursive.

Improve this answer
$\endgroup$
2
  • $\begingroup$ And why are we copying w twice? What's the sense in doing that? Thanks a lot anyways! I kinda got the point now $\endgroup$
    – Nicola
    Dec 17, 2022 at 11:41
  • $\begingroup$ In $L_d$, you are asking if $w$ doesn't belong to the language of the Turing Machine of code $w$. In $\overline{L_u}$, the input is two words: the code $\langle M\rangle$ of a Turing Machine, and a word $w$, and you asks if $w\notin L(M)$. So $L_d$ is more or less $\overline{L_u}$ when using the same word twice ($w$ is the code $\langle M \rangle$ of a Turing Machine and the word that belongs or not to $L(M)$, hence the duplication). $\endgroup$
    – Nathaniel
    Dec 17, 2022 at 12:24

Your Answer

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

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