328 views

1 Answer

0 votes
0 votes
I think, THINK it's C: No TM exists

Let me explain why,

In the proof of non-recursivly enumerable langauges we have seen that for every RE language there exists a TM,

Here, L is actually a superset of all the possible TM on a. Therefore L' will be

universel set - set of all possible string over a for which a TM exists.

Therefore basically it will a non - recirsivly emumerable language. Which cannot be accepted by a TM.

But I am not sure of the fact that this might be a recursive language also which are closed under complement but then also we had a set of TM which accpted a set of strings therefore its a RE.

Please correct me if I am wrong, this is actually a very good question.

But I am pretty aure I am right :P ;)
edited by

Related questions

0 votes
0 votes
0 answers
1
RahulVerma3 asked Apr 2
52 views
Is this the correct Turing machine for the language $0^n 1^n0^n$?assuming $ at the end and begining of the input tape
3 votes
3 votes
2 answers
4