The Gateway to Computer Science Excellence
+1 vote
202 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 by Boss (25.6k points) | 202 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

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
198,086 comments
104,735 users