1
$\begingroup$

So I was supposed to prove with the help of Rice's Theorem whether the language: $L_{5} = \{w \in \{0,1\}^{*}|\forall x \in \{0,1\}^{*}, M_{w}(w) =x\}$ is decidable.

First of all: I don't understand, why we can use Rice's Theorem in the first place: If I would chose two Turingmachines $M_{w}$ and $M_{w'}$ with $w \neq w'$ then I would get $M_{w}(w) = M_{w'}(w) = x$. But this would lead to $w'$ not being in $L_{5}$ and $w \in L_{5}$. Or am I misunderstanding something?

Second: The solution says, that the Language $L_{5}$ is decidable as $L_{5} = \emptyset$ because the output is clearly determined with a fixed input. But why is that so? I thought that $L_{5}$ is not empty because there are TM which output x on their own input and there are some which do not.

$\endgroup$
1
$\begingroup$

A word $w$ belongs to $L_5$ if for all $x \in \{0,1\}^*$ it is the case that $M_w(w) = x$. In particular, if $w \in L_5$ then $M_w(w) = 0$ and $M_w(w) = 1$, which can't both be true. So no word belongs to $L_5$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you so much!! $\endgroup$ – Daisy Jul 24 at 18:36

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.