1

I'm reading this and the first part in Lemma 4 is confusing:

Lemma 4. For all acceptable languages L and L′, the languages L ∪ L′ and L ∩ L′ are also acceptable.

Proof: Let M and M′ be Turing machines that decide L and L′, respectively.

I don't follow how we prove the existence of $M$ and $M'$. We know these languages $L$ and $L'$ are acceptable (as stated) but are they really decidable? From what I understand acceptable language $L$ implies a Turing machine that accepts every string of $w \in L$; a decidable language $L_D$ implies a Turning machine that accepts every string of $w \in L_D$ and halts for every $w \in \Sigma^*$ (or in other words does not diverge for any $w$).

sprajagopal
  • 622
  • 1
  • 5
  • 20
  • 2
    Indeed, at first it says that machines $M$ and $M'$ decide $L$ and $L'$, respectively, but reading further, the first paragraph does take into account the case where $M$ or $M'$ diverge. Maybe it's just a typo? – frabala Jan 12 '21 at 15:39
  • True if it was "accept" instead of "decide" then the rest makes sense. I wanted to make sure I'm not missing any basics here. – sprajagopal Jan 12 '21 at 15:40
  • 1
    I think that the author means "accepts". The combined machine accepts $w$ iff $M$ accepts $w$ and $M'$ accepts $w$. – Henno Brandsma Jan 12 '21 at 15:58

0 Answers0