1 votes 1 votes Theory of Computation theory-of-computation recursive-and-recursively-enumerable-languages + – vaishali jhalani asked Jan 19, 2017 retagged Jul 4, 2017 by Arjun vaishali jhalani 491 views answer comment Share Follow See all 4 Comments See all 4 4 Comments reply Hradesh patel commented Jan 19, 2017 reply Follow Share S1 : not RE S2: RE but not REC 0 votes 0 votes vaishali jhalani commented Jan 19, 2017 reply Follow Share Can you please explain? 0 votes 0 votes focus _GATE commented Jan 19, 2017 reply Follow Share how s1 not re and s2 re but not rec ?? plzz explain ?? 0 votes 0 votes Kantikumar commented Jan 19, 2017 reply Follow Share I think, S1 : RE but not REC Run M on all inputs in an interleaved mode and halt whenever 3 inputs have been accepted. S2: not RE Clearly L={<M,x>| M does not halt on x} $\epsilon$ L2. As L is not RE L2 must be not RE. 1 votes 1 votes Please log in or register to add a comment.
0 votes 0 votes None of them is REC. You should go through Rice's theorem.Read it carefully. solve few problems to be able deal with decidabilty topic. http://gatecse.in/rices-theorem/ Lucky sunda answered Jan 20, 2017 Lucky sunda comment Share Follow See all 0 reply Please log in or register to add a comment.