search
Log In

Recent questions tagged rice-theorem

1 vote
0 answers
1
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
0 votes
0 answers
2
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
0 votes
0 answers
3
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
0 votes
1 answer
4
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
0 votes
1 answer
5
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
0 votes
0 answers
6
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
2 votes
0 answers
8
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
0 votes
0 answers
9
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
0 votes
0 answers
10
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
0 votes
0 answers
11
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
1 vote
0 answers
13
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
2 votes
2 answers
14
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
2 votes
0 answers
15
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
0 votes
0 answers
16
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
0 votes
0 answers
18
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
0 votes
0 answers
19
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
0 votes
0 answers
20
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
7 votes
2 answers
21
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
1 vote
0 answers
22
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
2 votes
0 answers
23
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
0 votes
0 answers
24
0 votes
0 answers
25
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
2 votes
1 answer
26
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
1 vote
0 answers
27
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
4 votes
1 answer
28
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
1 vote
1 answer
29
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
3 votes
2 answers
30
...