MadeEasy Test Series: Theory Of Computation - Recursive And Recursive Enumerable Languages

Question

consider the following problems

p1: {<M,x,k>| M is a Turing machine M does not halt on x within k steps }

p2:{<M>|M is a Turing machine and M accepts at least two strings of different length}

p3:{<M>| M is a Turing machine and there exists an input whose length is less than 100 on which M halts }

the problems which are  RE but not REC?

Comments

How?

---

P2 and P3

Reason

P1 : we will surely halt within k step at max. so halting turing machine lang lead to Rec language.which is also REL.

P2,P3 : no gurantee whether it will halt or not so REL but not Recursive.You may get doubt for P3 that "whose length is less than 100" but within 100 it might fall in some infinite loop.

---

I think both of them non RE

how do u know those are RE?

Answer 1

1) rec

2)RE

3)RE 

explanation 

1  take the complement of 1st   and we get set of encoding of turing machine M that halt on x within k steps   now here is the constraint on the no of step that is k    

it means this is the set of turing machine which halt within k step so it is recursive , when complement of L is recursive then L will be recursive

2)  we can think it as  membership problem because we have to test 2 string of different length means whether two different length string accepted by turing machine .  so undecidable 

now it can be done with rice theorem 

T yes= when turing machine accept atleast two string of  different length

T no= turing machine  does not accept atleast two string of  different length  . 

so here it is the non trivial property  so undecidable

3) again membership problem

whether it halt on string length less than 100 

so undecidable    now why it is RE?  because we have enumeration method ,start from 0 length string and go upto 100 . here it may be case that it does not halt 

alter method:Tyes =there is some turing machine which halt within 100 steps

 Tno = not eccepted any string until 100 steps 

so by rice theorem undecidable , moreover semidecidable and RE

Comments

Regarding the statement 1, what about the strings that do not belong to the language. Nothing is said for those strings. So, it should be RE.

---

No, here we going to only k steps. It's REC

---

How did you interpret the language that way?