The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
Facebook Login
or
Email or Username
Password
Remember
Login
Register

I forgot my password
Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Prev
Blogs
New Blog
Exams
Recent questions tagged ricetheorem
+3
votes
1
answer
1
#Selfdoubt Rice's Theorem
What is the difference between Nontrivial property (in 1st theorem)and Nonmonotonic 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/ricestheorem/
asked
Dec 26, 2016
in
Theory of Computation
by
Prajwal Bhat
Boss
(
11.2k
points)

385
views
theoryofcomputation
ricetheorem
decidability
+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
theoryofcomputation
ricetheorem
decidability
+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
theoryofcomputation
decidability
ricetheorem
+2
votes
0
answers
4
Basic Doubt in Rice Theorem
I read this blog http://gatecse.in/ricestheorem/ 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
ricetheorem
theoryofcomputation
decidability
+3
votes
1
answer
5
Rice theorem
s Rice theorem says any nontrivial 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
theoryofcomputation
ricetheorem
+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
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
ricetheorem
Page:
« prev
1
2
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
Recent Posts
ISRO CSE 2020 PAPER ANALYSE
BARC OCES/DGFS 2020
ISI CMI PDF by GATE Overflow
Calculus Important Points
Management Trainee Recruitment COAL INDIA 2020
Follow @csegate
Recent questions tagged ricetheorem
Recent Blog Comments
Very slim chances..FML
100 percent
I am getting 151 marks excluding question not...
everyone will be surprised seeing the cutoff this...
There is no point of any debate/discourse here....
50,737
questions
57,293
answers
198,233
comments
104,916
users