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
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)
Interview experience at IIT Tirupati for MS program winter admission
Subjects
All categories
General Aptitude
(2.1k)
Engineering Mathematics
(8.5k)
Digital Logic
(3k)
Programming and DS
(5.1k)
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.3k)
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
hi this pdf have gate prevoius year questions or...
Thanks, dude for sharing your experience !! It...
Congratulations, at least you made it to the...
seems like you really enjoyed the process.......
I wrote an email to IISC regarding JEST 2021 but...
Network Sites
GO Mechanical
GO Electrical
GO Electronics
GO Civil
CSE Doubts
Recent questions tagged rice-theorem
1
vote
0
answers
1
Michael Sipser Edition 3 Exercise 5 Question 30 (Page No. 241)
Use Rice’s theorem, to prove the undecidability of each of the following languages. $INFINITE_{TM} = \{\langle M \rangle \mid \text{M is a TM and L(M) is an infinite language}\}$. $\{\langle M \rangle \mid \text{M is a TM and }\:1011 \in L(M)\}$. $ ALL_{TM} = \{\langle M \rangle \mid \text{ M is a TM and}\: L(M) = Σ^{\ast} \}$.
Use Rice’s theorem, to prove the undecidability of each of the following languages. $INFINITE_{TM} = \{\langle M \rangle \mid \text{M is a TM and L(M) is an infinite language}\}$. $\{\langle M \rangle \mid \text{M is a TM and }\:1011 \in L(M)\}$. $ ALL_{TM} = \{\langle M \rangle \mid \text{ M is a TM and}\: L(M) = Σ^{\ast} \}$.
asked
Oct 20, 2019
in
Theory of Computation
Lakshman Patel RJIT
111
views
michael-sipser
theory-of-computation
turing-machine
decidability
rice-theorem
proof
0
votes
0
answers
2
Michael Sipser Edition 3 Exercise 5 Question 29 (Page No. 241)
Rice's theorem. Let $P$ be any nontrivial property of the language of a Turing machine. Prove that the problem of determining whether a given Turing machine's language has property $P$ is undecidable. In more formal ... that $P$ is an undecidable language. Show that both conditions are necessary for proving that $P$ is undecidable.
Rice's theorem. Let $P$ be any nontrivial property of the language of a Turing machine. Prove that the problem of determining whether a given Turing machine's language has property $P$ is undecidable. In more formal terms, let $P$ be a language consisting of Turing ... any $TMs$. Prove that $P$ is an undecidable language. Show that both conditions are necessary for proving that $P$ is undecidable.
asked
Oct 20, 2019
in
Theory of Computation
Lakshman Patel RJIT
58
views
michael-sipser
theory-of-computation
turing-machine
decidability
rice-theorem
proof
0
votes
0
answers
3
Michael Sipser Edition 3 Exercise 5 Question 28 (Page No. 241)
Rice's theorem. Let $P$ be any nontrivial property of the language of a Turing machine. Prove that the problem of determining whether a given Turing machine's language has property $P$ is undecidable. In more formal terms, let $P$ be a language ... $M_{1}$ and $M_{2}$ are any $TMs$. Prove that $P$ is an undecidable language.
Rice's theorem. Let $P$ be any nontrivial property of the language of a Turing machine. Prove that the problem of determining whether a given Turing machine's language has property $P$ is undecidable. In more formal terms, let $P$ ... $M_{1}$ and $M_{2}$ are any $TMs$. Prove that $P$ is an undecidable language.
asked
Oct 20, 2019
in
Theory of Computation
Lakshman Patel RJIT
90
views
michael-sipser
theory-of-computation
turing-machine
decidability
rice-theorem
proof
0
votes
1
answer
4
Ullman (TOC) Edition 3 Exercise 9.3 Question 4 (Page No. 400)
We know by Rice's theorem that none of the following problems are decidable. However are they recursively enumerable,or non-RE? Does $L(M)$ contain at least two strings? Is $L(M)$ infinite? Is $L(M)$ a context-free language? Is $L(M) = (L(M))^{R}$?
We know by Rice's theorem that none of the following problems are decidable. However are they recursively enumerable,or non-RE? Does $L(M)$ contain at least two strings? Is $L(M)$ infinite? Is $L(M)$ a context-free language? Is $L(M) = (L(M))^{R}$?
asked
Jul 21, 2019
in
Theory of Computation
Lakshman Patel RJIT
74
views
ullman
theory-of-computation
rice-theorem
descriptive
0
votes
1
answer
5
SELF DOUBT_ RICE THEOREM
L = {<M1, M2>M1 and M2 are two TMs, and ε ∈ L(M1) \ L(M2) }. is it RECURSIVE OR RECURSIVE ENUMERABLE OR NOT EVEN RECURSIVE ENUM.
L = {<M1, M2>M1 and M2 are two TMs, and ε ∈ L(M1) \ L(M2) }. is it RECURSIVE OR RECURSIVE ENUMERABLE OR NOT EVEN RECURSIVE ENUM.
asked
Dec 29, 2018
in
Theory of Computation
Deepanshu
212
views
rice-theorem
recursive-and-recursively-enumerable-languages
0
votes
0
answers
6
Rice theorem
1.{<M>| M is a TM accepts any string starting with 1} 2.{<M>| M is TM accept exactly 20 strings} Please guide I don’t know how to apply rice theorem. for 1. Is Tyes = { string starting with 1} Tno = { all strings – strings starting with 1} what is Tyes and Tno here? I only conclude by intution that when we provide strings as input some got into loop and some got accepts .
1.{<M>| M is a TM accepts any string starting with 1} 2.{<M>| M is TM accept exactly 20 strings} Please guide I don’t know how to apply rice theorem. for 1. Is Tyes = { string starting with 1} Tno = { all strings – strings starting with 1} what is Tyes and Tno here? I only conclude by intution that when we provide strings as input some got into loop and some got accepts .
asked
Dec 17, 2018
in
Theory of Computation
Learner_jai
171
views
rice-theorem
decidability
0
votes
2
answers
7
Halting problem of TM which recognize recursive languages is undecidable?
Halting problem of Turing machines which recognize recursive languages is undecidable. (True / False)
Halting problem of Turing machines which recognize recursive languages is undecidable. (True / False)
asked
Dec 10, 2018
in
Theory of Computation
gmrishikumar
567
views
decidability
recursive-and-recursively-enumerable-languages
theory-of-computation
turing-machine
rice-theorem
2
votes
0
answers
8
TOC-Undecidability
Here is my analysis. P1: When we bound the number of steps a turing machine can tape, the total number of input possible that can be taken by such turing machine becomes finite and by running TM in an interleaved mode I can decide whether TM M halts on x within k ... decide P3. Hence, P3 is decidable.->REC. So, I think here answer must be 1. Please let me know what's right.
Here is my analysis. P1: When we bound the number of steps a turing machine can tape, the total number of input possible that can be taken by such turing machine becomes finite and by running TM in an interleaved mode I can decide whether TM M halts on x within k steps. So, ... hence I can decide P3. Hence, P3 is decidable.->REC. So, I think here answer must be 1. Please let me know what's right.
asked
Nov 23, 2018
in
Theory of Computation
Ayush Upadhyaya
283
views
theory-of-computation
decidability
rice-theorem
0
votes
0
answers
9
SELF DOUBT _ RICE THEOREM
L1 = { <M> | M is a TM and | L (M) <=1 } L2= { <M> | M is a TM and | L (M) >=1 } NOW QUESTION IS WHICH ARE RECURSIVE ENUMERABLE AND WHICH ARE NOT ???? I JUST READ BASICS OF rice theorem DONT PRACTICE MUCH QUESTIONS ON THIS I ... = 0...... and REL_yes as string length >= 1 . REL_YES is a proper subset of REL _NO . so we can say that it is also non re
L1 = { <M> | M is a TM and | L (M) <=1 } L2= { <M> | M is a TM and | L (M) >=1 } NOW QUESTION IS WHICH ARE RECURSIVE ENUMERABLE AND WHICH ARE NOT ???? I JUST READ BASICS OF rice theorem DONT PRACTICE MUCH QUESTIONS ON THIS I SOLVED ABOVE QUESTION BY THIS... ... string length >= 0...... and REL_yes as string length >= 1 . REL_YES is a proper subset of REL _NO . so we can say that it is also non re
asked
Nov 14, 2018
in
Theory of Computation
Deepanshu
120
views
rice-theorem
theory-of-computation
rice
0
votes
0
answers
10
Undecidability
L1:{<M> | there exist a Turing machine M' such that <M>$\neq$<M'> and L(M) = L(M')} How this problem becomes trivial? and if it non-trivial then please explain why is that so. According to my understanding, non-trivial properties ... it is then is it okay to say M1=M2 because they are kind of same machine but other one is just with some non deterministic nature.
L1:{<M> | there exist a Turing machine M' such that <M>$\neq$<M'> and L(M) = L(M')} How this problem becomes trivial? and if it non-trivial then please explain why is that so. According to my understanding, non-trivial properties are the one where a language ... and if it is then is it okay to say M1=M2 because they are kind of same machine but other one is just with some non deterministic nature.
asked
Oct 30, 2018
in
Theory of Computation
Swapnil Naik
143
views
theory-of-computation
rice-theorem
turing-machine
decidability
0
votes
0
answers
11
undecidability
Writes Non Blank: Given a turing machine T, does it ever writes a non-blank symbol on its tape, when started with a blank tape. how the above problem is solvable? somewhere i got this explanation: Let the machine only writes blank symbol. Then ... is a non-trivial property of turing machine and every non trivial property of turing machine is undecidable, so this is also undecidable.
Writes Non Blank: Given a turing machine T, does it ever writes a non-blank symbol on its tape, when started with a blank tape. how the above problem is solvable? somewhere i got this explanation: Let the machine only writes blank symbol. Then its ... this is a non-trivial property of turing machine and every non trivial property of turing machine is undecidable, so this is also undecidable.
asked
Sep 21, 2018
in
Theory of Computation
aambazinga
134
views
theory-of-computation
decidability
rice-theorem
turing-machine
0
votes
0
answers
12
TOC- Undecidability
asked
Sep 9, 2018
in
Theory of Computation
sidlewis
161
views
theory-of-computation
decidability
rice-theorem
context-free-languages
turing-machine
1
vote
0
answers
13
Rice's Theorem
What is monotonic and non-monotonic property. Please explain the second postulate of Rice's Theorem.
What is monotonic and non-monotonic property. Please explain the second postulate of Rice's Theorem.
asked
Jan 23, 2018
in
Theory of Computation
Sumaiya23
165
views
rice-theorem
decidability
theory-of-computation
self-doubt
turing-machine
2
votes
2
answers
14
Undecidability Confusion
I was Studying About Undecidability on GateCSE. I am facing a doubt that : L = {<M> | M accepts "1"} L is set of String & each String is an Encoding of TM & TM accepts 1 L = {<M> | L(M) = {1}} Given a Input Program ... really is difference between both of them ? Can you definition of 2 in words like " L is set of String ............"
I was Studying About Undecidability on GateCSE. I am facing a doubt that : L = {<M> | M accepts "1"} L is set of String & each String is an Encoding of TM & TM accepts 1 L = {<M> | L(M) = {1}} Given a Input Program we have to see it Accepts 1 & nothing ... selected encoding ?) What really is difference between both of them ? Can you definition of 2 in words like " L is set of String ............"
asked
Jan 13, 2018
in
Theory of Computation
yogi_p
309
views
theory-of-computation
decidability
rice-theorem
2
votes
0
answers
15
undecidability
Define languages L0 and L1 as follows : L0={⟨M,w,0⟩∣M halts on w} L1={⟨M,w,1⟩∣M does not halt on w} Here ⟨M,w,i⟩is a triplet, whose first component M is an encoding of a Turing Machine, second component w is a string, and the third component i is a ... an acceptor for L as even when L0 is RE L1 is not RE but can anyone explain me what about L COMPLEMENT what is the language ??
Define languages L0 and L1 as follows : L0={⟨M,w,0⟩∣M halts on w} L1={⟨M,w,1⟩∣M does not halt on w} Here ⟨M,w,i⟩is a triplet, whose first component M is an encoding of a Turing Machine, second component w is a string, and the third component i is a bit. Let ... even design an acceptor for L as even when L0 is RE L1 is not RE but can anyone explain me what about L COMPLEMENT what is the language ??
asked
Jan 9, 2018
in
Theory of Computation
Venkat Sai
311
views
theory-of-computation
decidability
rice-theorem
0
votes
0
answers
16
Doubt in Rice's Theorem
I have a doubt while understanding step 2 in proof of Rice's Theorem- According to my understanding,proof of Rice's theorem as follows ( Please suggest If something is wrong in my understanding) P is a property of languages of TM which is non-trivial ... Same problem as ATM). Can M' take decision in finite time. Please give me some insights to I can understand this point.
I have a doubt while understanding step 2 in proof of Rice's Theorem- According to my understanding,proof of Rice's theorem as follows ( Please suggest If something is wrong in my understanding) P is a property of languages of TM which is non-trivial and semantic. We ... at all(Same problem as ATM). Can M' take decision in finite time. Please give me some insights to I can understand this point.
asked
Dec 15, 2017
in
Theory of Computation
Durgesh Singh
224
views
rice-theorem
decidability
theory-of-computation
self-doubt
turing-machine
0
votes
0
answers
17
Rice theorem G is a CFG. Is L(G)= Σ ∗ L(G)=Σ∗ .What is it - Decidable / Undeciable .How?
asked
Dec 1, 2017
in
Theory of Computation
hem chandra joshi
158
views
rice-theorem
0
votes
0
answers
18
Rice theorem problem
Problem : It is undecidable whether an arbitrary Turing Machines halt within 10 steps? Let consider Two Turing machine in which first one it is halt in 10 steps while in other it is not , so as it is undecidable. @arjun sir ,@bikram sir or @others
Problem : It is undecidable whether an arbitrary Turing Machines halt within 10 steps? Let consider Two Turing machine in which first one it is halt in 10 steps while in other it is not , so as it is undecidable. @arjun sir ,@bikram sir or @others
asked
Dec 1, 2017
in
Theory of Computation
hem chandra joshi
422
views
rice-theorem
theory-of-computation
decidability
theorem
rice
0
votes
0
answers
19
Can any one proof decidability/undecidability of following on Rice Theorem ?
Rice theorem : 1. Any non-trivial property of the LANGUAGE recognizable by a Turing machine is undecidable. 2. Any non-monotonic property of the LANGUAGE recognizable by a Turing machine is unrecognizable While ... is regular. Whether a finite state automation halts on all inputs. Membership problem for type 00 languages.
Rice theorem : 1. Any non-trivial property of the LANGUAGE recognizable by a Turing machine is undecidable. 2. Any non-monotonic property of the LANGUAGE recognizable by a Turing machine is unrecognizable While solving please describe non-trivial/trivial and non- ... context-free language is regular. Whether a finite state automation halts on all inputs. Membership problem for type 00 languages.
asked
Dec 1, 2017
in
Theory of Computation
hem chandra joshi
170
views
rice-theorem
0
votes
0
answers
20
Rice's Theorem
Example# 3 from Part-1 Rice's Theorem from https://gatecse.in/rices-theorem/ states as follows (3) L(M) is recognized by a TM having even number of states Sol: This is a trivial property. This set equals the set of recursively enumerable languages. According to ... then? Can someone give me an example for which TYES and TNO cannot be found and let me know if my approach is correct ?
Example# 3 from Part-1 Rice's Theorem from https://gatecse.in/rices-theorem/ states as follows (3) L(M) is recognized by a TM having even number of states Sol: This is a trivial property. This set equals the set of recursively enumerable languages. According to the ... property then? Can someone give me an example for which TYES and TNO cannot be found and let me know if my approach is correct ?
asked
Oct 28, 2017
in
Theory of Computation
Salazar
351
views
decidability
rice-theorem
theory-of-computation
self-doubt
7
votes
2
answers
21
$\{\langle M \rangle \mid M$ is a TM and there exist an input whose length is less than 100, on which $M$ halts$\}$
My Question $\{\langle M \rangle \mid M$ is a TM and there exist an input whose length is less than 100, on which $M$ halts$\}$ I have to check that it is Turing Recognizable or not (i.e R.E) My Approach/Doubt Question taken from https://gateoverflow.in/7427/which-following ... $100$ $T_{yes}\subset T_{no}$. Hence it is not RE.But in the solution it is R.E.
asked
Sep 9, 2017
in
Theory of Computation
sourav.
2.3k
views
theory-of-computation
turing-machine
decidability
rice-theorem
1
vote
0
answers
22
Turing Machine Rice's Theorem
L = {M|M is a TM that accepts all even numbers} For the above language i can have Tyes machine which has all even numbers.And Tno as machine whose language is empty.So i can say it is undecidable. But to show it is Not RE. What ... am assuming here that the property of the language as "Only all even numbers",i guess the same has been given in the question.
L = {M|M is a TM that accepts all even numbers} For the above language i can have Tyes machine which has all even numbers.And Tno as machine whose language is empty.So i can say it is undecidable. But to show it is Not RE. What should be my Tno,so that ... Tno machine?I am assuming here that the property of the language as "Only all even numbers",i guess the same has been given in the question.
asked
Aug 5, 2017
in
Theory of Computation
rahul sharma 5
363
views
decidability
rice-theorem
theory-of-computation
turing-machine
self-doubt
2
votes
0
answers
23
Rice theorem Example from (https://www.cs.rice.edu/~nakhleh/COMP481/final_review_sp06_sol.pdf)
L={<M>: M is a TM that accepts all even numbers } Why it is not recursively enumerable language???
asked
Jul 18, 2017
in
Theory of Computation
akb1115
369
views
rice-theorem
theory-of-computation
decidability
0
votes
0
answers
24
http://www.cs.rice.edu/~nakhleh/COMP481/
Can anybody please explain this reduction and rice theorem. http://www.cs.rice.edu/~nakhleh/COMP481/ Thanks
Can anybody please explain this reduction and rice theorem. http://www.cs.rice.edu/~nakhleh/COMP481/ Thanks
asked
May 24, 2017
in
Theory of Computation
Arpit Dhuriya
214
views
theory-of-computation
rice-theorem
decidability
0
votes
0
answers
25
rice theorem problem
L(M) has at most 10 strings We can have Tyes for ϕ and Tno for Σ∗. Hence, L={M∣L(M) has at most 10 strings} is not Turing decidable (not recursive). problem : It should not b Tyes Σ∗ and Tno for ϕ
L(M) has at most 10 strings We can have Tyes for ϕ and Tno for Σ∗. Hence, L={M∣L(M) has at most 10 strings} is not Turing decidable (not recursive). problem : It should not b Tyes Σ∗ and Tno for ϕ
asked
Jan 24, 2017
in
Theory of Computation
Wanted
103
views
rice-theorem
2
votes
1
answer
26
General Doubt In rice theorem
If we are not able to apply non-monote property ,then is it always true that it is RE but not REC,are there any scenarios where we can't apply non-monotone property but still language is NOT RE. Say,L={TM| L(TM) has atleast one string}, Now it is ... theat RE but not REC. P.S:- By (i) and (ii) ,i mean the definitions mentioned here.(http://gatecse.in/rices-theorem/)
If we are not able to apply non-monote property ,then is it always true that it is RE but not REC,are there any scenarios where we can't apply non-monotone property but still language is NOT RE. Say,L={TM| L(TM) has atleast one string}, Now it is clearly Language property ... mean theat RE but not REC. P.S:- By (i) and (ii) ,i mean the definitions mentioned here.(http://gatecse.in/rices-theorem/)
asked
Jan 22, 2017
in
Theory of Computation
rahul sharma 5
296
views
theory-of-computation
rice-theorem
decidability
1
vote
0
answers
27
Rice theorem Clarification
I need to understand when to apply RICE's theorem and when to not. Questions like:- Turing machine makes at least five moves,It accepts a string input of length atleast five ,TM halts for every input on length <50 are all decidable. But these are ... some TM will say yes and some will say NO.Then why can't we use same concept on above metioned questions? Please help
I need to understand when to apply RICE's theorem and when to not. Questions like:- Turing machine makes at least five moves,It accepts a string input of length atleast five ,TM halts for every input on length <50 are all decidable. But these are NON TRIVIAL properties ... because some TM will say yes and some will say NO.Then why can't we use same concept on above metioned questions? Please help
asked
Jan 13, 2017
in
Theory of Computation
rahul sharma 5
273
views
theory-of-computation
rice-theorem
decidability
4
votes
1
answer
28
Rice's Theorem
I am unable to understand when to apply Rice's theorem and when to not. How L2 is decidable.
I am unable to understand when to apply Rice's theorem and when to not. How L2 is decidable.
asked
Jan 3, 2017
in
Theory of Computation
Lucky sunda
493
views
rice-theorem
decidability
theory-of-computation
1
vote
1
answer
29
Rices theorem
I mean how it is a trivial property, we can write Tyes ( TM having even states) and Tno ( TM having odd states) for it.Can Turing machine can never have odd number of states?
I mean how it is a trivial property, we can write Tyes ( TM having even states) and Tno ( TM having odd states) for it.Can Turing machine can never have odd number of states?
asked
Jan 2, 2017
in
Theory of Computation
Lucky sunda
144
views
decidability
rice-theorem
3
votes
2
answers
30
L1 = {<M> | M is a TM and L(M) ⊆ {00, 11}}
L1 = {<M> | M is a TM and L(M) ⊆ {00, 11}} R.E or not RE..??
L1 = {<M> | M is a TM and L(M) ⊆ {00, 11}} R.E or not RE..??
asked
Dec 27, 2016
in
Theory of Computation
Akriti sood
618
views
theory-of-computation
decidability
rice-theorem
Page:
1
2
next »
...