search
Log In
2 votes
371 views

L={<M>: M is a TM that accepts all even numbers } Why it is not recursively enumerable language???

in Theory of Computation 371 views
2
Actually there are infinite number of even numbers. So, yes cases of this language  form a loop. This language produce loop in 'yes' cases of the language, so we can say yes case is not satisfied here.That is why it is non R.E.
0

"So, yes cases of this language  form a loop" Can you please elaborate this line  a bit more  

0
@srestha
So do you want to say that complement of halting problem(i.e given an input w whether the Turing machine will go into an infinite loop or not) which is completely undecidable can be reduced to this given problem????

Which will make this problem undecidable.
0

but we have enumeration method for this .According to that it must be recursive enumerable

 akb1115  srestha 

Please log in or register to answer this question.

Related questions

0 votes
0 answers
1
214 views
Can anybody please explain this reduction and rice theorem. http://www.cs.rice.edu/~nakhleh/COMP481/ Thanks
asked May 24, 2017 in Theory of Computation Arpit Dhuriya 214 views
0 votes
0 answers
2
426 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 426 views
2 votes
1 answer
3
298 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 298 views
1 vote
0 answers
4
273 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 273 views
...