Published May 19, 2022 - By Marco Garosi
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 ) are recursively enumerable (r.e.).
We can rewrite formally what we’ve just said:
Similarly to what we do to prove Rice’s Theorem, we have to prove the double implication.
Left to right,
Let’s assume that is recursive. Then it must have a characteristic function , which is total and recursive.
Function is partial (it does not always halt) and recursive; it is the semicharacteristic function of .
You can construct an analogous function for . In fact, you could define .
Since and have a semicharacteristic, partial recursive function , they are recursively enumerable (r.e.).
Right to left,
Let’s assume that and not be r.e., with semicharacteristic functions and . Hence we can define:
Since and are complementary, then . So, function always returns a value, as long as and are run in parallel on interleaving (one instruction of and one of ). Running them in such a way prevents one function diverging from blocking the other — no blockings are created.
Function , then, is total recursive; is thus recursive by definition.