Self doubt- Undecidability

Question

L={TM | TM accepts only '11'}

A.Is this language an REL?

B. Is the complement of L REL or not REL? If REL is it Decidable or Semidecidable?

I think there is no logic to reject other string apart from '11', hence we cannot show in output all valid inputs so I think L is not REL please somebody verify.

But i have doubt in complement of this language is it REL or not REL?

Thanks

Comments

L={TM | TM accepts only '11'}

assuming $\Sigma = \{ 1\}$, the TM have to run all inputs of regex $1^*$, if machines accepts $11$ and rejects all other inputs then only that arbitrary TM will be in language $\text{L}$. So TM will run for infinite time and thus it is not Turning recognizable.

---

Complement of $\text{L}$ will contain those TM's will accept all strings but 11. Now this is also non RE because all TM's which are in L have to check all possible strings in $\Sigma^*$.

---

Thanks @Mk Utkarsh

But how can L complement accept only those TM which do not contain 11. There will be some TM which will contain say both 11 and 111. Since it's not just 11, hence its not a part of L, so it has to be a part of its complement isn't it?

So can't we check if there exists atleast 1 string other than '11', then it's part of L compliment?

Here by taking compliment of L we r including all the TMs which r not in L right?

​​​Thanks

---

yes you are right L complement will comprise of all TM's which are not in L. Those TM whose language is not $\{ 11 \}$.

---

So if L(TM) = {11,111} and L={111} both are present in L compliment. (Even though they contain '11' but it's not ONLY '11', something else is also present.

So to ensure that a TM is in L compliment we need to find 1 string other than '11' which belongs to lang right. So why we need to look at infinite strings, won't it make this problem as Semidecidable, L compliment has logic but L has no logic ?

---

I doubt that the problem is semi decidable because L is not RE so basically if we are checking all TM's then those TM's which belong in L are also checked and if they accept only 11 then they are not in $\overline{L}$ but those TM's will not halt so how can you say $\overline{L}$ is RE. There $\not\exists$ any condition where all TM's halt and we get $\overline{L}$.

---

I was saying about L complement being recursively enumerable (REL). And L as not Recursively enumerable. So if we check all TMs then yes if a TM which accepts only 11 is encountered, it will not halt, and it's invalid input. So I was thinking maybe it would be that L compliment is not recursive bcoz it's not haltin for all inputs, but its Recursively enumerable as it halts for valid (if there is any string other than 11 which is getting accepted).

---

$\overline{L}$ have to check all TM's on inputs 11 and any other string like 1 or 111 or if 11 is rejected then that TM is in $\overline{L}$ but the problem here is while checking a TM on input 11 imagine a situation where a TM belongs to L and accepts 11 now next task is to check whether that TM is accepting any other string so that we can include it to $\overline{L}$, but that will not halt. Infact all TM's in L will not halt which checking TM's for $\overline{L}$. So it is not even reclusively enumerable.

---

Yeah, now maybe I'm understanding the issue in including TMs to L compliment. If we have a TM L(TM) = {11,111} and it's not accepting '1'. It belongs to L compliment so we should be able to halt. Now we have to check all TMs for all inputs one by one, and if it happens that we check first with 1 as input, it may not halt, even though it's valid. Hence it's not Recursively enumerable. Am I right?

---

Chaitrasj it we are checking a TM with input 1 and it never halts then we cannot say L complement is  not RE. Read my comment above multiple times you'll understand what i'm trying to say.

---

Please tell me 1 thing, if a TM halts for its valid inputs and may or may not halt for its invalid inputs, then the language which TM is accepting can it be called Recursively enumerable?

---

I re-read your last comment multiple times. As per your last line, all TMs in L will not halt when checking for L compliment. And they are the invalid inputs for L compliment so why are we bothered about invalid inputs not coming to a halt, if valid input is halting isn't it sufficient to say it a Recursively enumerable lang.?

---

they are the invalid inputs for L compliment

You mean they are invalid TM's for $\overline{L}$ but how do we know if its invalid?  Invalid and valid can only be decided if TM's halt and TM's of L will never halt and until and there is no condition where all arbitrary TM's halt when checking $\overline{L}$. $\exists$ TM in L and it will never halt and because of which while checking that TM for all other inputs other than $11$ TM will never halt so we are unsure that this TM belongs to L or $\overline{L}$. If this TM halts after some time we can say it belongs to $\overline{L}$ but if it belongs to L then it will never halt and we can wait forever and ever. 

There exist no condition where all TM's are halting so we can get a set of TM's. We cannot say it is RE.

---

Yeah I'm getting your point what you want to say.

By that logic, suppose, L = {CFG | CFG is ambigious} Now we are giving all CFGs in input and if CFG is ambigious then it will give more than 1 parse tree and get accepted. But if we give in input an unambiguous CFG, then it will keep checking forever for some string to get more than 1 parse tree, but it will never halt. So this problem L, too is not REL? Because for all inputs TM is not coming to a halt?

---

@Mk Utkarsh

I think any trivial case, not acceped by any TM

Those are always non RE