A message from our CEO about the future of Stack Overflow and Stack Exchange. Read now.

# Tag Info

## New answers tagged semi-decidability

0

Let's write formally what $L$ and $\overline{L}$ are: $$L=\{\langle M,w,b \rangle| (b=0 \wedge M(w) \mbox{ halts}) \vee (b=1 \wedge M(w) \mbox{ does not halt}) \}$$ $$\overline{L}=\{\langle M,w,b \rangle| (b=1 \vee M(w) \mbox{ does not halt}) \wedge (b=0 \vee M(w) \mbox{ halts}) \}$$ The latter is confusing, so let's rearrange it: \overline{L}=\{\langle ...

Top 50 recent answers are included