menu
search
Log In
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

Subjects

Network Sites

 GO Mechanical
 GO Electrical
 GO Electronics
 GO Civil
 CSE Doubts

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

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.

← Prev. Next →
← Prev. Qn. in Sub. Next Qn. in Sub. →

Related questions

2 votes
0 answers
1
376 views
Rice theorem Example from (https://www.cs.rice.edu/~nakhleh/COMP481/final_review_sp06_sol.pdf)
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
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
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
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/)
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
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
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
Dark theme
Muffin by Hélio Chun
Thanks to Q2A
...