Characterization Theorem

Published May 25, 2022  -  By Marco Garosi

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.


The theorem states that the following three statements are equivalent:

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


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    21 \implies 2, 2    32 \implies 3 and that 3    13 \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 {φx}xN\{ \varphi_{x} \}_{x \in \N} be a Turing Machine (TM).

1    21 \implies 2

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

φ(y)={yif φx(y)otherwise \varphi (y) = \begin{cases} y &\text{if } \varphi_x(y) \downarrow \\ \uparrow &\text{otherwise} \end{cases}

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

2    32 \implies 3

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

ψ(y)={φx(y)if φx(y)otherwise \psi (y) = \begin{cases} \varphi_x(y) &\text{if } \varphi_x(y) \downarrow \\ \uparrow &\text{otherwise} \end{cases}

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

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

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

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

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

Iterate the previous step with jp+1=jp+1+kj_{p + 1} = j_p + 1 + k.

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

3    13 \implies 1

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

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

φ(x)=μz.(f(z)x=0) \varphi (x) = \mu z.(f(z) - x = 0)

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

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

Share on: