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:
- A set
- ( is thus enumerated by partial function )
The theorem states that the three statements are equivalent. This “hides” some implications ( ). In order to correctly prove the theorem, it is thus necessary to prove that , and that . This circularity, if proven, proves the whole theorem.
Before continuing, please recall that mean the termination (halting) of a Turing Machine, while stands for it diverging.
Let’s start with the first one. Let be a Turing Machine (TM).
Let . By definition, there’s some partial recursive function such that . Then let’s define:
Let’s assume and that . By applying dovetail on the function:
Since , there exists such that dovetail halts at the step.
Let’s define by induction on the step of dovetail, thus making sure that has only the values in the list generated by applying dovetail to .
Then, if converges in with , then for all .
Now let’s suppose that to define we used the step. Then the following cases might show up:
- if in the dovetail step there are no new terminations, then ;
- if in the dovetail step converges (halts) with input with , then for all .
Iterate the previous step with .
The aforementioned procedure works as expected, thus defining a total recursive function such that .
If then with . is then r.e.
On the other hand, if (where is a total function), you just need to define
Of course, . Moreover, .
But then, and is thus r.e.