Recent questions tagged rice-theorem

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} \}$.

Lakshman Patel RJIT asked in Theory of Computation Oct 20, 2019

by Lakshman Patel RJIT

259 views

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.

Lakshman Patel RJIT asked in Theory of Computation Oct 20, 2019

by Lakshman Patel RJIT

206 views

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.

Lakshman Patel RJIT asked in Theory of Computation Oct 20, 2019

by Lakshman Patel RJIT

280 views

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}$?

Lakshman Patel RJIT asked in Theory of Computation Jul 21, 2019

by Lakshman Patel RJIT

182 views

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.

Deepanshu asked in Theory of Computation Dec 29, 2018

455 views

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 .

Learner_jai asked in Theory of Computation Dec 17, 2018

286 views

1 vote

3 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)

gmrishikumar asked in Theory of Computation Dec 10, 2018

by gmrishikumar

1.1k views

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.

Ayush Upadhyaya asked in Theory of Computation Nov 23, 2018

by Ayush Upadhyaya

480 views

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

Deepanshu asked in Theory of Computation Nov 14, 2018

216 views

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.

Swapnil Naik asked in Theory of Computation Oct 30, 2018

by Swapnil Naik

326 views

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.

aambazinga asked in Theory of Computation Sep 21, 2018

278 views

0 votes

0 answers

12

TOC- Undecidability

sidlewis asked in Theory of Computation Sep 9, 2018

272 views

1 vote

0 answers

13

Rice's Theorem
What is monotonic and non-monotonic property. Please explain the second postulate of Rice's Theorem.

Sumaiya23 asked in Theory of Computation Jan 23, 2018

239 views

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 ............"

yogi_p asked in Theory of Computation Jan 13, 2018

by yogi_p

506 views

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 ??

Venkat Sai asked in Theory of Computation Jan 9, 2018

507 views

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.

Durgesh Singh asked in Theory of Computation Dec 15, 2017

by Durgesh Singh

324 views

0 votes

0 answers

17

Rice theorem G is a CFG. Is L(G)= Σ ∗ L(G)=Σ∗ .What is it - Decidable / Undeciable .How?

hem chandra joshi asked in Theory of Computation Dec 1, 2017

by hem chandra joshi

280 views

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

hem chandra joshi asked in Theory of Computation Dec 1, 2017

by hem chandra joshi

610 views

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.

hem chandra joshi asked in Theory of Computation Dec 1, 2017

by hem chandra joshi

224 views

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 ?

Salazar asked in Theory of Computation Oct 28, 2017

471 views

10 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$\}$

sourav. asked in Theory of Computation Sep 9, 2017

3.3k views

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.

rahul sharma 5 asked in Theory of Computation Aug 5, 2017

by rahul sharma 5

594 views

2 votes

0 answers

23

Rice theorem Example from (https://www.cs.rice.edu/~nakhleh/COMP481/final_review_sp06_sol.pdf)

akb1115 asked in Theory of Computation Jul 18, 2017

469 views

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

Arpit Dhuriya asked in Theory of Computation May 24, 2017

by Arpit Dhuriya

284 views

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 ϕ

Wanted asked in Theory of Computation Jan 24, 2017

by Wanted

139 views

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/)

rahul sharma 5 asked in Theory of Computation Jan 22, 2017

by rahul sharma 5

429 views

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

rahul sharma 5 asked in Theory of Computation Jan 13, 2017

by rahul sharma 5

407 views

5 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.

Lucky sunda asked in Theory of Computation Jan 3, 2017

790 views

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?

Lucky sunda asked in Theory of Computation Jan 2, 2017

191 views

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..??

Akriti sood asked in Theory of Computation Dec 27, 2016

1.1k views

Page:

Follow @gateoverflow

Recent questions tagged rice-theorem

Search GATE Overflow for GATE CSE