Prove that there is no computable enumeration of all decidable languages

Question

The question:

Let $L_1,L_2,...$ be an enumeration of $\mathcal{R}$ and define $A_i = \{\langle M\rangle \ | \ L(M) = L_i\}$. Let $L$ be a language in $\mathcal{RE}$ such that $L \subset \{\langle M\rangle \ | \ \text{M is a TM that always halts}\}$. Prove that there exists an $i$ for which $L∩A_i = ∅$.

Hint $\downarrow$

Hint: Build a TM that returns some (which?) element of $L$ and apply a diagonalization argument.

My approach

I thought of the Hint but I am not sure that the language I get is decidable and I don't know how to prove that all its "always halting" TMs are not in $L$.

Answer 1

WLOG assume we are talking about languages over a binary alphabet $\{0,1\}$. Let $M'$ be an enumerating Turing Machine for $L$, i.e., every element of $L$ is eventually output by $M'$. Let $\langle M_j \rangle$ denote the $j$th TM output by $M'$. Define $$L_D = \{ x \mid M_x(x) \text{ does not accept} \},$$ where $x$ is interpreted as a number in base 2. Note that $L_D$ is decidable: given $x$ you can decide if $x \in L_D$ by running $M'$ until it outputs $x$th TM $M_x$ and then running $M_x$ on $x$ and flipping the output. This is a decider since all TMs output by $M'$ halt on all inputs. Thus $L_D$ appears in the enumeration of R, say, as $L_k$ for some $k$.

It is left to show that $L \cap A_k = \emptyset$. Suppose that there exists a TM $M$ such that $\langle M \rangle \in L \cap A_k$. Then let $\ell$ be the smallest number such that $\langle M \rangle$ is output as the $\ell$th element by the enumerator $M'$, i.e. $M = M_\ell$. Therefore, we have $\ell \in L(M) \iff \ell \in L(M_\ell) \iff \ell \notin L_D \iff \ell \notin L_k \iff \ell \notin L(M)$, which is a contradition.