in Theory of Computation
740 views
1 vote
1 vote

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.

in Theory of Computation
740 views

4 Comments

@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

1
1
Got it :)
0
0

@ 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

 

0
0

1 Answer

0 votes
0 votes

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
 

Related questions