1,080 views

1 Answer

Best answer
10 votes
10 votes

It is a Non trivial property in the sense of Rice's Theorem, hence Undecidable.

But, is it a Non monotonic Property ?

  • Let $T_{Yes} = \left \{ 0,1 \right \}$
  • And $T_{No} = \left \{ 0,1,011\right \}$

As, $T_{Yes} \subseteq T_{No}$, Making this even Non RE.

selected by

Related questions

2 votes
2 votes
2 answers
1
Akriti sood asked Jan 15, 2017
3,470 views
L={<M : M is a TM that accepts all even numbers }is it recursive/R.E??
1 votes
1 votes
1 answer
2
sh!va asked Jun 21, 2016
1,702 views
Is this language regular? L1:{wxwR&#8739;w,x&isin;{a,b}&lowast; and |w|,|x|>0},wR is the reverse of string wPlease explain..
1 votes
1 votes
1 answer
3
Xylene asked Jul 15, 2017
1,069 views
From rice theorem, I know that it is not recursive. But can someone prove that ? Or atleast give some intuitive proof?
11 votes
11 votes
2 answers
4
sourav. asked Sep 9, 2017
4,377 views
My Question $\{\langle M \rangle \mid M$ is a TM and there exist an input whose length is less than 100, on which $M$ halts$\}$I have to check that it is Turing Recogniza...