Posts's Theorem

Post’s Theorem, named after Emil Post, is a theorem in the computability theory that gives a characterization of recursive sets. Indeed it states that a set is recursive if and only if it and its complement (namely $\bar{A} = \N \setminus A$) are recursively enumerable (r.e.).

Theorem

We can rewrite formally what we’ve just said:

Proof

Let $A \subseteq \N \land \bar{A} = \N \setminus A$.

Similarly to what we do to prove Rice’s Theorem, we have to prove the double implication.

Left to right, $\implies$

Let’s assume that $A$ is recursive. Then it must have a characteristic function $f_A$, which is total and recursive.

Let’s define:

Function $\Psi$ is partial (it does not always halt) and recursive; it is the semicharacteristic function of $A$.

You can construct an analogous function for $\bar{A}$. In fact, you could define $f_{\bar{A}} = 1 - f_A$.

Since $A$ and $\bar{A}$ have a semicharacteristic, partial recursive function $\Psi$, they are recursively enumerable (r.e.).

Right to left, $\impliedby$

Let’s assume that $A$ and $\bar{A}$ not be r.e., with semicharacteristic functions $\Psi_A$ and $\Psi_{\bar{A}}$. Hence we can define:

Since $A$ and $\bar{A}$ are complementary, then $x \in A \lor x \in \bar{A}$. So, function $f_A$ always returns a value, as long as $\Psi_A$ and $\Psi_{\bar{A}}$ are run in parallel on interleaving (one instruction of $\Psi_A$ and one of $\Psi_{\bar{A}}$). Running them in such a way prevents one function diverging from blocking the other — no blockings are created.

Function $f_A$, then, is total recursive; $A$ is thus recursive by definition. $\square$