Question

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.

Was it helpful?

Solution

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

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top