search
Log In
0 votes
217 views

Can anybody please explain this reduction and rice theorem.

http://www.cs.rice.edu/~nakhleh/COMP481/

Thanks

in Theory of Computation 217 views

Please log in or register to answer this question.

Related questions

2 votes
0 answers
1
376 views
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 376 views
0 votes
0 answers
2
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
2 votes
1 answer
3
300 views
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 300 views
1 vote
0 answers
4
279 views
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 279 views
...