418 views
0 votes
0 votes

How to tell whether a language is recursively enumerable or not?

Also answer the question with proper algorithm :-)


2 Answers

Best answer
1 votes
1 votes

Here we can not apply rice's second theorem since we can not have Tyes and Tno such that L(Tyes) subset of L(Tno).

But for Tyes  case we can run Turing machine and can ans yes for Language. This can be done be feeding the TM different inputs in the order of string length (also running in steps so that even if one input is going to infinite loop, we proceed with the others) and finally stopping when 312929 strings are accepted. We are guaranteed to terminate because IF 312929 strings are accepted, it must have a largest string and in some finite time we would be giving the TM that input.  But for complement for L Turing machine can Go into infinite loop - as we can never be sure if there is a larger string which the TM may accept or not.

Tno can't be answered . Tyes  can be answered.

This is property of RES so L is not decidable but is recursive enumerable

selected by
0 votes
0 votes

No I think ans will be (C)

M will be non recursive enumerable here.

After accepting 312929 strings it will accepting inputs, but here it accepts all. So, here is a chance of forming loop.(we can think like dfa, when dfa accepts all, it forms a self loop on last state). But when we examining  loop doesnot gives 'yes' answer. So, 'yes' answer not possible. According to rice theorem it will be non trivial property. So, M will be non recursive enumerable here.

Related questions

0 votes
0 votes
0 answers
1
manisha11 asked Aug 16, 2018
383 views
Set of all languages that are not Recursively Enumerable is uncountable.This is true. WHY?
0 votes
0 votes
0 answers
2
thor asked Jan 9, 2017
538 views
A Turing Machine goes on to an infinite loop on string $\epsilon$. Is it correct? And thus Any language containing $\epsilon$ is not REL.Is it correct?
0 votes
0 votes
0 answers
3