in Theory of Computation
228 views
0 votes
0 votes

Which of the following is not REL?

  1. $L$ = {$<M>$ | $L(M)$ = $\phi$, M is a TM}
  2. $L$ = {$<M>$ | $L(M)$ $\neq$ $\phi$, M is a TM}
  3. $L$ = {$<M, x>$ | M halts on x}
  4. $L$ = {$<M, x>$ | accepts x}
in Theory of Computation
by
228 views

3 Comments

edited by

The questions asks for which language is not $REL$.

We will use Rice Theorem and check if any property is non-monotonous

$1.$ Say, $M=\left \{ \right \} $ So, $L(M)=\phi$

So, $L(M)=T_{yes}$

$M_1=\left \{ 1,2\right\}$ So, $L(M_1)\neq\phi$

So, $L(M_1)=T_{no}$

as $M\subset M_1$ then $T_{yes}\subset T_{no}$

So, $L = \left\{ M\,|\,L(M)=\phi\right\}$, is non-REL

Correct me if i'm wrong

Ref : here

0
0

@Shobhit Joshi

acc to rice theorem 

Rice’s theorem the language describing any nontrivial property of Turing machine is not recursive

What you mean by non trivial property here ???

0
0

For a property of recursively enumerable set to be non-trivial, there should exist at least recursively enumerable languages, (hence two Turing machines), the property holding for one ($T_{yes}$ being its TM) and not holding for the other ($T_{no}$ being its TM)

1
1

Please log in or register to answer this question.

Related questions