# Reduction to Diagonalization language to prove that Universal language is not REC

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

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.

• And why are we copying w twice? What's the sense in doing that? Thanks a lot anyways! I kinda got the point now Dec 17, 2022 at 11:41
• 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). Dec 17, 2022 at 12:24