The Gateway to Computer Science Excellence
+2 votes

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

in Theory of Computation by Active (3.3k points) | 265 views
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.

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

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.

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

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
50,737 questions
57,322 answers
105,144 users