Log In
2 votes

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 of RE and hence undecidable,But if we look on non-monotone property,then the Tno is phi as it is the only machine which will say NO as per me,and the langauge having atleast one string will never be proper subset of Tno,so non-monotone property doesn't hold,so is this sufficient to say that it is turing recogonizable?I mean satisfying Rice theorem (i) part and not (ii) will always mean theat RE but not REC.

P.S:- By (i) and (ii) ,i mean the definitions mentioned here.(

in Theory of Computation 250 views

L(M) contain at least k strings: This is R.E. (k is finite)

But I am not sure about the sufficient conditions because in extended rice there are two more conditions, which we do not generally apply.

1 Answer

0 votes
No its not sufficient

consider the language L={TM| L(TM) is infinite} we can not apply rice theorem but it is still non RE
How can you say it is Not RE?
how will you design a turing machine to accept that

exactly how many strings should the machine accept before it can halt?

Related questions

2 votes
0 answers
I read this blog and I have a doubt in the first property. An example in this blog is L(M) = {0} and it's written that TMno =sigma* . My doubt is how can it be sigma* as sigma* can also contain {0} which should be accepted by TM.
asked Nov 25, 2016 in Theory of Computation Xylene 187 views
0 votes
0 answers
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 353 views
2 votes
0 answers
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 309 views
1 vote
0 answers
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 232 views