Login
Register
Dark Mode
Brightness
Profile
Edit Profile
Messages
My favorites
My Updates
Logout
Recent questions tagged rice-theorem
5
votes
1
answer
31
#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 ... for the language of other (Tno) and L(Tyes)⊂L(Tno) Source: http://gatecse.in/rices-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 differen...
Prajwal Bhat
1.3k
views
Prajwal Bhat
asked
Dec 26, 2016
Theory of Computation
theory-of-computation
rice-theorem
decidability
+
–
4
votes
1
answer
32
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.
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 ...
Akriti sood
797
views
Akriti sood
asked
Dec 16, 2016
Theory of Computation
theory-of-computation
rice-theorem
decidability
+
–
8
votes
3
answers
33
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??
$L=\left \{ <TM | TM\ halts\ on\ every\ input\ \right \}$is above language Recursively enumerable or non recursively enumerable??
Akriti sood
4.9k
views
Akriti sood
asked
Dec 16, 2016
Theory of Computation
theory-of-computation
decidability
rice-theorem
+
–
2
votes
0
answers
34
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.
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 d...
Xylene
622
views
Xylene
asked
Nov 25, 2016
Theory of Computation
rice-theorem
theory-of-computation
decidability
+
–
4
votes
1
answer
35
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?
sRice 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?
thor
2.0k
views
thor
asked
Nov 16, 2016
Theory of Computation
theory-of-computation
rice-theorem
+
–
3
votes
1
answer
36
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.
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 encodi...
Rajat Sharma 1
2.1k
views
Rajat Sharma 1
asked
Dec 15, 2015
Theory of Computation
theory-of-computation
recursive-and-recursively-enumerable-languages
rice-theorem
+
–
Page:
« prev
1
2
Email or Username
Show
Hide
Password
I forgot my password
Remember
Log in
Register
