2. Computable Enumerability

A language $L$ is said to be computably enumerable if there is some machine $M$ that is:

• Sound: if $M(w)=1$ then $w\in L$
• Complete: if $w\in L$ then $M(w)=1$

Theorem: The Halting problem ${\text{HALT}}_{TM}$ is computably enumerable.

Proof:

1. Construct the following sound and complete machine $\text{halt}\overline{}$:
2. Note the following relationship: $\text{halt}\overline{}(⟨code(M),w⟩)=\begin{array}{c}{\mathcal{M}}_u(⟨code(M),w⟩)=1\\ \text{or }{\mathcal{M}}_u(⟨code(M),w⟩)=0\end{array}$
3. By the definition of our Universal Turing Machine we have that: $\text{halt}\overline{}(⟨code(M),w⟩)=1\iff M(w)=1\text{ or }M(w)=0$
   • The right-to-left direction is soundness
   • The left-to-right direction is completeness

Theorem: The non-emptiness problem $\overline{E_{TM}}$ is C.E.

Proof:

1. Let $w_0,w_1,\dots ,w_n$ be an enumeration of all possible input words from ${\Sigma }^{\ast }$.
2. Construct the following algorithm $\text{empty}\overline{}$:
   1. For each $k=0,1,2,3,\dots$:
      1. For each $i=0,1,2,3,\dots ,k$:
         1. Run ${\mathcal{M}}_u$ on $⟨code(M),w⟩$ for $k$ steps
         2. If ${\mathcal{M}}_u$ accepts then return True
3. Note the following relationship: $\text{empty}\overline{}(code(M))=1\iff \text{there is some }{w}_i\in {\Sigma }^{\ast }\text{ such that }{\mathcal{M}}_u(⟨code(M),w_i⟩)=1\text{ within }k\text{ steps}$
4. By definition of $\overline{E_{TM}}$, we have that $\text{empty}\overline{}(code(M))=1\iff code(M)\in \overline{E_{TM}}$
   • The right-to-left direction is soundness
   • The left-to-right direction is completeness

Co-computable Enumerability

A language $L$ is said to be co-computably enumerable if it’s complement is computably enumerable.

Theorem: if $L$ and $\bar{L}$ are both C.E., then $L$ is decidable.

Proof:

1. Suppose that (i) $L$ is C.E. and (ii) $\bar{L}$ is C.E.
2. By (i), let $M_L$ be a machine that is sound and complete w.r.t. $L$ By (ii), let $M_{\bar{L}}$ be a machine that is sound and complete w.r.t. $\bar{L}$
3. Construct a machine $M^{\prime }$ which runs $M_L$ and $M_{\bar{L}}$ in parallel

Theorem: The non-Halting problem $\overline{{\text{HALT}}_{TM}}$ is not C.E.

Proof:

1. We have that: ${\text{HALT}}_{TM}\Leftarrow \{\begin{array}{l}{\text{HALT}}_{TM}\text{ is C.E.}\\ \overline{{\text{HALT}}_{TM}}\text{ is C.E.}\end{array}$
2. However, we have that ${\text{HALT}}_{TM}$ is undecidable but C.E.: ${\text{HALT}}_{TM}\Leftarrow \{\begin{array}{l}{\text{HALT}}_{TM}\text{ is C.E.}\\ \overline{{\text{HALT}}_{TM}}\text{ is C.E.}\end{array}$
3. Therefore, $\overline{{\text{HALT}}_{TM}}$ must not be C.E. as required: ${\text{HALT}}_{TM}\Leftarrow \{\begin{array}{l}{\text{HALT}}_{TM}\text{ is C.E.}\\ \overline{{\text{HALT}}_{TM}}\text{ is C.E.}\end{array}$