Characterization Theorem

Characterization Theorem is a theorem in the computability theory that gives a characterization of recursively enumerable (r.e.) sets. Indeed it provides three different but equivalent statements that, as the name says, chacarterize recursively enumerable sets. Although they might seem completely disconnected from one another — and even somehow weird — they have profound consequences.

Theorem

The theorem states that the following three statements are equivalent:

1. A set $A \in \text{r.e.}$
2. $\exists \varphi \in \wp_{\mu} : A = \text{range}(\varphi)$ ( $A$ is thus enumerated by partial function $\varphi$)
3. $A = \emptyset$ or $\exists f \in \R : A = \text{range}(f)$

Proof

The theorem states that the three statements are equivalent. This “hides” some implications ( $\implies$). In order to correctly prove the theorem, it is thus necessary to prove that $1 \implies 2$, $2 \implies 3$ and that $3 \implies 1$. This circularity, if proven, proves the whole theorem.

Before continuing, please recall that $\downarrow$ mean the termination (halting) of a Turing Machine, while $\uparrow$ stands for it diverging.

Let’s start with the first one. Let $\{ \varphi_{x} \}_{x \in \N}$ be a Turing Machine (TM).

$1 \implies 2$

Let $A \in \text{r.e.}$. By definition, there’s some partial recursive function $\varphi_x$ such that $A = \text{dom}(\varphi_x) = W_x$. Then let’s define:

$\varphi$ is partial recursive and $\text{range}(\varphi) = \text{dom}(\varphi_x) = A$. The first implication has now been proven.

$2 \implies 3$

Let’s assume $A = \text{range}(\varphi_x)$ and that $A \neq \emptyset$. By applying dovetail on the function:

Since $A = \text{range}(\varphi_x) \neq \emptyset$, there exists $n_0 \in \N$ such that dovetail halts at the $n_0^{\text{th}}$ step.

Let’s define $f$ by induction on the $n^\text{th}$ step of dovetail, thus making sure that $f$ has only the values in the list $L$ generated by applying dovetail to $\psi$.

Then, if $\psi$ converges in $\{ m_0, \dots, m_{j_0} \}$ with $0 \leq j_0 \leq n_0$, then for all $i \in [0, j_0]: f(i) = \psi(m_i)$.

Now let’s suppose that to define $f(j_p)$ we used the $n_p^{\text{th}}$ step. Then the following cases might show up:

• if in the $\{n_p + 1\}^{\text{th}}$ dovetail step there are no new terminations, then $f(j_p + 1) = f(j_p)$;
• if in the $\{n_p + 1\}^{\text{th}}$ dovetail step $\psi$ converges (halts) with input $\{ p_0, \dots, p_k \}$ with $0 \leq k \leq n_p + 1$, then for all $i \in [0, k]: f(j_p + 1 + i) = \psi(p_i)$.

Iterate the previous step with $j_{p + 1} = j_p + 1 + k$.

The aforementioned procedure works as expected, thus defining a total recursive function $f$ such that $A = \text{range}(f)$.

$3 \implies 1$

If $A = \emptyset$ then $A = \text{dom}(\psi)$ with $\psi = \lambda x.\uparrow$. $A$ is then r.e.

On the other hand, if $A = \text{range}(f)$ (where $f$ is a total function), you just need to define

Of course, $\varphi \in \wp_{\mu}$. Moreover, $\varphi (x) \downarrow \iff \exist z : f(z) = x$.

But then, $A = \text{dom}(\varphi)$ and $A$ is thus r.e. $\square$