menu
search
Log In
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

Subjects

Recent questions tagged rice-theorem

Network Sites

 GO Mechanical
 GO Electrical
 GO Electronics
 GO Civil
 CSE Doubts

Recent questions tagged rice-theorem

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/
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 non-trivial, there ... holding 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 Prajwal Bhat 539 views
3 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.
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 Akriti sood 381 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??
$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 Akriti sood 2.6k 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.
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 Xylene 216 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?
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 thor 881 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.
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}$ ... r.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 Rajat Sharma 1 877 views
Page:
Dark theme
Muffin by Hélio Chun
Thanks to Q2A
...