search
Log In
1 vote
268 views

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 268 views
0

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 .

0
And your T(NO) is also fine making it non RE.
0
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?
0
Yes, the language is represented as a set form, so it contains all the (only even length strings) .

And, your statement is also correct .
0
Thank you for the confirmation:)
0

@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.

0
Yes, correct.
0

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

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

@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

0
Got it :)
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

 

Please log in or register to answer this question.

Related questions

1 vote
0 answers
1
139 views
What is monotonic and non-monotonic property. Please explain the second postulate of Rice's Theorem.
asked Jan 23, 2018 in Theory of Computation Sumaiya23 139 views
0 votes
0 answers
2
186 views
I have a doubt while understanding step 2 in proof of Rice's Theorem- According to my understanding,proof of Rice's theorem as follows ( Please suggest If something is wrong in my understanding) P is a property of languages of TM which is non-trivial and semantic. We ... at all(Same problem as ATM). Can M' take decision in finite time. Please give me some insights to I can understand this point.
asked Dec 15, 2017 in Theory of Computation Durgesh Singh 186 views
0 votes
0 answers
3
275 views
Example# 3 from Part-1 Rice's Theorem from https://gatecse.in/rices-theorem/ states as follows (3) L(M) is recognized by a TM having even number of states Sol: This is a trivial property. This set equals the set of recursively enumerable languages. According to the ... property then? Can someone give me an example for which TYES and TNO cannot be found and let me know if my approach is correct ?
asked Oct 28, 2017 in Theory of Computation Salazar 275 views
1 vote
1 answer
4
330 views
1) I know that turing decidable means recursive language. But does is also means its decidable? So basically i want to know if REC imples decidability and RE implies undecidability or not. I got confused with word decidable in "turing decidable" 2) http://www. ... ? If they have same expressive power why can't we use DTM in NP decision problems? Thanks for being patient and reading doubt.
asked Nov 29, 2017 in Theory of Computation ♥_Less 330 views
...