1,044 views
3 votes
3 votes
$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$ _____________

2 Answers

1 votes
1 votes

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.

0 votes
0 votes

Answer is 1. 

Reason:

In P1 there will be infinite set of strings. strings of same length aren’t accepted. Hence it will not be regular. Implies that its RE

In P2   there are finite set as mentioned that an input with length less than 100. either on acceptance the machine halts or on rejection the machine halts. Also for other inputs the machine either accepts + goes to infinite loop or rejects or goes to infinite loop. So its undecidable hence NOT RE

so answer is P1 ie only 1 option is correct as per question

edited by

Related questions

3 votes
3 votes
2 answers
1
4 votes
4 votes
2 answers
2
Kai asked Jan 29, 2017
721 views
When a Multi-tape TM of time complexity T(N) is reduced to a single tape turing machine, the complexity can go upto?
3 votes
3 votes
2 answers
3
3 votes
3 votes
1 answer
4