search
Log In
0 votes
105 views
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 or string may get accepted by some Turing machine and not by some other Turing machines and hence it becomes undecidable. Hence it becomes undecidable when a given Turing machine it will accept a given string or not as it becomes non-trivial property.

For every non deterministic TM M1 there exists an equivalent deterministic TM M2 recognizing the same language, in this case we will have 2 different machines and both will accept same language, is this description holds true?? 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.
in Theory of Computation 105 views
0

I think the language is decidable ..for a language to be  decidable we have to answer a question for every string  that YES it belongs to L or NO it does not belongs to L

Given any Valid TM encoding ..we have to answer whether there is one TM different from this and accept same language.We know for every NTM <---> DTM which accepts same language hence Our question is trivial with answer YES always ..Hence we can say that language is decidable..

correct me if wrong 

@Arjun sir @Swapnil Naik

Please log in or register to answer this question.

Related questions

0 votes
0 answers
1
97 views
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 97 views
1 vote
0 answers
3
65 views
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 65 views
0 votes
0 answers
4
37 views
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 37 views
...