Computer Science Asked on December 28, 2021
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.
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$.
Answered by Yuval Filmus on December 28, 2021
Get help from others!
Recent Questions
Recent Answers
© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP