5
$\begingroup$

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$.

$\endgroup$
4
+50
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Here is what is going on conceptually: Take an enumeration of total computable functions. Consider the diagonal. It is total and computable and different from every function in the enumeration. $\endgroup$ – Kaveh Jun 1 '16 at 14:12

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.