The Gateway to Computer Science Excellence
+1 vote
128 views
$P_{1}:$ {$<M>|M $ is a TM that accepts atleast $2$ strings of different length}

$P_{2}:$  {$<M>|M $ is a TM and there exists an input whose length less than $100,$ on which $M$ halts }

The number of problem which is $RE$ but not $REC$ _____________
in Theory of Computation by Veteran (117k points) | 128 views
0
Answer is 1

P1 :  RE but not REC

P2:   REC

plz check??
0
Can u explain P1??

1 Answer

+1 vote

Ans is 1

First lets look at P2, P2 is finite as it is less than 100, so it is regular therefore also Recursive

Now lets look at P1, for P1 we can generate infinite strings of different length and the TM may or may not accept those strings, so we need to check for infinite amount of time whether there exist any string whose length does not matches with any string that is accepted by the TM, so we are not sure whether our TM will halt or not. So it is definitely Non-Recursive, but Recursively Enumerable.

by Active (3.5k points)
0
R u sure , P2 will be recursive? I donot think so
0

According to my concept, there are finite number of inputs which have length less than 100, so our Turing machine will definitely halt after a time, be it 100 years or 10000 years it doesn't matter, but we can assure that it will halt, because there are finite number of input less than 100 and one day we should have checked all those inputs!

0
0

@srestha

See this link--> https://gateoverflow.in/39596/gate2016-2-44

See the part where Arjun sir has proved why L2 is recursive. This thing relates to our problem.

And specially this line--> "we can just give it all possible inputs of length less than 2016 and see if it reaches a halt state within 2016 steps".

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,654 questions
56,169 answers
193,878 comments
94,301 users