TransWikia.com

Rice's Theorem for Turing machine with fixed output

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.

One Answer

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

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP