Recent questions tagged rice-theorem - GATE Overflow

+3 votes

1 answer

1

#Selfdoubt Rice's Theorem
What is the difference between Non-trivial property (in 1st theorem)and Non-monotonic property ( in 2nd theorem)? I was going through Rice's theorem but unable to differentiate between these 2 properties.Please give the detail to differentiate both For a property to be ... for the language of other (Tno) and L(Tyes)⊂L(Tno) Source: http://gatecse.in/rices-theorem/

asked Dec 26, 2016 in Theory of Computation by Prajwal Bhat Boss (11.2k points) | 385 views

+2 votes

1 answer

2

L={⟨M⟩|TM accepts exactly 154 strings}
L={⟨M⟩|TM accepts exactly 154 strings} -------------------------------------------------------------------------------------------------------- this language is not decidable but is this R.E?? by second rice theorem, Tyes ={154 strings} and Tno = more than 154 strings hence, Tyes is subset of Tno.so,it is not even R.E. am i right? please correct me.

asked Dec 16, 2016 in Theory of Computation by Akriti sood Boss (12.2k points) | 288 views

+8 votes

2 answers

3

L= {<TM> | TM halts on every input}
$L=\left \{ <TM> | TM\ halts\ on\ every\ input\ \right \}$ is above language Recursively enumerable or non recursively enumerable??

asked Dec 16, 2016 in Theory of Computation by Akriti sood Boss (12.2k points) | 1.8k views

+2 votes

0 answers

4

Basic Doubt in Rice Theorem
I read this blog http://gatecse.in/rices-theorem/ and I have a doubt in the first property. An example in this blog is L(M) = {0} and it's written that TMno =sigma* . My doubt is how can it be sigma* as sigma* can also contain {0} which should be accepted by TM.

asked Nov 25, 2016 in Theory of Computation by Xylene Active (3.6k points) | 165 views

+3 votes

1 answer

5

Rice theorem
s Rice theorem says any non-trivial property of a language is Undecidable. Then how is above one REL. Does it mean we cannot say anything for a trivial property?

asked Nov 17, 2016 in Theory of Computation by thor Loyal (6.8k points) | 592 views

+2 votes

1 answer

6

Please explain?
Consider the following Languages: $L_{ne}=\{\langle M \rangle \mid L(M)\neq \phi \}$ $L_{e}=\{\langle M \rangle \ \mid L(M)=\phi \}$ where $\langle M \rangle$ denotes encoding of a Turing Machine $M$ Then which of the following is true? (a) $L_{ne}$ is r.e. but not ... .e. (b) Both are not r.e. (c) Both are recursive (d) $L_{e}$ is r.e. but not recursive and $L_{ne}$ is not r.e.

asked Dec 15, 2015 in Theory of Computation by Rajat Sharma 1 Junior (541 points) | 384 views

Page:

Recent questions tagged rice-theorem

50,737 questions

57,293 answers

198,233 comments

104,916 users