Turing Machine Rice's Theorem

Question

L = {M|M is a TM that accepts all even numbers}

For the above language i can have Tyes machine which has all even numbers.And Tno as machine whose language is empty.So i can say it is undecidable. 

But to show it is Not RE. What should be my Tno,so that it should be proper superset of Tyes?Can i take sigma* as my Tno?Although it will accepts the even numbers ,but still it has odd numbers also.Will that work as Tno machine?I am assuming here that the property of the language as "Only all even numbers",i guess the same has been given in the question.

Comments

If you simply think, that accepting all even numbers requires to prove all that infinite set of even numbers to belong to this language .

Now, to check all those infinite numbers is not possible which makes it NON RE .

---

Now, here no use of Rice theorem .

---

And your T(NO) is also fine making it non RE.

---

Thanks kapil. And the language accepted is "Only all even numbers" ,correct? If some other machine excepts all even numbers + some extra strings then it will be different language ,right?

---

Yes, the language is represented as a set form, so it contains all the (only even length strings) .

And, your statement is also correct .

---

Thank you for the confirmation:)

---

@Kapil.Can you clear one general doubt?Like you said

accepting all even numbers requires to prove all that infinite set of even numbers to belong to this language . 

1.For these type of questions,assume L has some Mi as its member.So when that member will be input to the machine M' whose language is L,then that machine M' will simulate behavior of the input machine and check if it satisfying the required property.

2.If my above statement is correct,then assume that Mi is a member ,now to say that it is my member my the machine M' will try to simulate it but since there are infinite strings that i need to accept to say yes so it is NOT RE.If it would have been RE then it should have said yes for the member.

---

Yes, correct.

---

I am not satisfied with this reason to conclude as not RE

then assume that Mi is a member ,now to say that it is my member my the machine M' will try to simulate it but since there are infinite strings that i need to accept to say yes so it is NOT RE.If it would have been RE then it should have said yes for the member.

Because even we have infinite set of strings to check can't we apply Dovetailing?

https://courses.engr.illinois.edu/cs373/sp2009/lectures/lect_24.pdf

https://gateoverflow.in/1994/gate2014-2-35

---

Yes, sure you can apply dovetailing but still you won't be able to prove for all .

---

@Vs but upto what length you will check to say yes for members?

For https://gateoverflow.in/1994/gate2014-2-35 . We can check for only for 2014 length string.So we have a bound here.But in case of all even number we dont have any bound to stop.

We can also prove it is not re by Rice's

---

Got it :)

---

@Kapil sir please check if my understanding is right

To say language decidable / undecidable we should be able to answer for ALL instance of problem 

Here instance of problem is given  -  TM , {Set of all even numbers } , Ques TM accepts all even numbers or not ?
If we use dovetailing -  Means run step 1 for String 1 on TM1 then String2 of input2 on TM1 ...........

But here Our UTM will be doing checking on TM1 only forever as set of Strings (even numbers here) is infinite

So even for YES instance of problem we have to wait for infinite time 

Hence Non RE and UD

------------------------------------------------------------------------------------------------------------

In https://gateoverflow.in/1994/gate2014-2-35 this problem

Instance of prob  - given TM , Set of all Strings of length 2014 , Wherther TM accepts any of them or not ?

If we use dovetailing  , Means run step 1 for String 1 on TM1 then String2 of input2 on TM1 .

two cases may happen  -- > 1) TM1 halts on some input and we take new TM2 to check on UTM

2) TM1 may go in infinite loop ...

But for atleast YES instance of problem we have to wait for finite time here

Hence RE (as we can't say about no instance) but not REC

 

Answer 1

L = {M|M is a TM that accepts all even numbers}

Language accepts all even number is a non trivial proper because we can have a language which don't accept all even number or which does not accept any even number so, it is a non-trivial property. Hence, it is not decidable. 
So now we will check if a language is RE, means it should accept all of its member. Now, set of all even number is an infinite set so, we need to check all the infinite strings to see whether machine halts is on every single string or not and it will take infinite time. Even if we apply dovetailing  technic it won't help us because then also we are supposed to check the complete set which is actually infinite. So, this computation will take infinite time even on members and hence it is a NOT RE language