what type of language

Question

{$<M>\mid M$ is a $TM$ that doesn't accept any even number}

what type of language is it?

• A. Recursively enumerable
• B. Recursive
• C. Not recursively enumerable
• D. none of the above

Comments

Complement is :- TM that accept at least one even e number.

Now complement is Undecidable as we can have Tyes=Sigma * and Tno= phi.

If complement is undecidable then the complement of complement (i.e the actual language) is Not RE.It should be C

---

Answer would be C only but the logic behind it is Not Correct.

Undecidable means NOT REC. Undecidable could be RE or NOT RE. Had it been RE but Not REC, then of course, its complement would be NOT RE. But Had it been NOT RE, then its Complement could be RE but not REC or NOT RE.

So, when you say that a language L is undecidable and thus its complement will be NOT RE, You'd first have to Prove that L was RE but NOT REC (Because When we say L is undecidable, we haven't proven it to be RE but NOT REC yet, It could be NOT RE too)

Answer 1

1. Checking Decidability :

By Rice's theorem, It can be shown that It is Undecidable because It is a Non-Trivial Property of RE languages. 

Any non-trivial property of the LANGUAGE recognizable by a Turing machine (recursively enumerable language) is undecidable. For a property of recursively enumerable set to be non-trivial, there should exist at least recursively enumerable languages, (hence two Turing machines), the property holding for one (Tyes being its TM) and not holding for the other (Tno being its TM).

Lyes = {  a, aaa, aaaaa }  Lno = { a, aa, aaa, aaaaa}   ..Thus There Exists a Language for which the given Property is satisfied and There Exists a Language for which the given Property is Not satisfied. Thus, The Property is Non-trivial and So, The Language is  Undecidable. 

But Undecidable means NOT REC. Undecidable could be RE  or NOT RE.

2. Checking Recognizability :

Now By Using Rice's Extended( Recognizability )  theorem, We can show that the Language is Unrecognizable (i.e. Not RE)

Any non-monotonic property of the LANGUAGE recognizable by a Turing machine (recursively enumerable language) is unrecognizable. For a property of recursively enumerable set to be non-monotonic, there should exist at least two recursively enumerable languages (hence two Turing machines), the property holding for one (Tyes being its TM) and not holding for the other (Tno being its TM) and the property holding set (language of Tyes) must be a proper subset of the set not having the property (language of Tno).

Lyes = {  a, aaa, aaaaa }  Lno = { a, aa, aaa, aaaaa}

Lyes  $\subset$ Lno thus, Language is Not RE.

Thus Option C is correct.

Useful Link : https://gatecse.in/rices-theorem/

Comments

your explanation is fine.But can you explain why it is not RE using reduction.i.e reducing non halting problem({<M,x>|M doesn't halt on x}) to this problem.

Answer 2

i think option A

because we know that RE language doesnt have an MEMBERSHIP ALGORITHM

so, as the question is asking about the acceptance of an even numbers can be dont or not TM cannot say directly soo i thin its RElanguage