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 Answer 1

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

$\endgroup$
1
  • $\begingroup$ Thank you so much!! $\endgroup$
    – Momo
    Commented Jul 24, 2020 at 18:36

Your Answer

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

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