search
Log In
0 votes
162 views
in Theory of Computation 162 views
0

This problem is reducible to Post correspondence problem which is undecidable.

0
I am Unable to read this problem,may you brief little bit more

Please log in or register to answer this question.

Related questions

0 votes
1 answer
1
220 views
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 220 views
0 votes
0 answers
2
173 views
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 173 views
0 votes
0 answers
3
124 views
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 124 views
0 votes
0 answers
4
427 views
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 427 views
...