The Gateway to Computer Science Excellence
+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 by Boss (25.6k points) | 179 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
by Active (2.7k points)
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

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,257 answers
104,735 users