menu
Login
Register
search
Log In
account_circle
Log In
Email or Username
Password
Remember
Log In
Register
I forgot my password
Register
Username
Email
Password
Register
add
Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Prev
Blogs
New Blog
Exams
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
Update on GO Book for GATE 2022
Barc Interview Experience 2020- CSE stream
JEST 2021 registrations are open
TIFR GS-2021 Online Application portal
IIT Jodhpur Mtech AI - Interview Expierence (Summer Admission)
Subjects
All categories
General Aptitude
(2.1k)
Engineering Mathematics
(8.5k)
Digital Logic
(3k)
Programming and DS
(5.2k)
Algorithms
(4.5k)
Theory of Computation
(6.3k)
Compiler Design
(2.2k)
Operating System
(4.7k)
Databases
(4.3k)
CO and Architecture
(3.5k)
Computer Networks
(4.3k)
Non GATE
(1.2k)
Others
(1.4k)
Admissions
(595)
Exam Queries
(838)
Tier 1 Placement Questions
(16)
Job Queries
(71)
Projects
(19)
Unknown Category
(1.1k)
Recent questions tagged rice-theorem
Recent Blog Comments
Can you check again?
sir please revert back as soon as possible
sir today i have purchased gate overflow test...
This PDF contains all the Previous Year...
Mock 3 will be added soon.
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
theory-of-computation
rice-theorem
decidability
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
theory-of-computation
rice-theorem
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??
$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
theory-of-computation
decidability
rice-theorem
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
rice-theorem
theory-of-computation
decidability
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
theory-of-computation
rice-theorem
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
theory-of-computation
recursive-and-recursively-enumerable-languages
rice-theorem
Page:
« prev
1
2
...