additions, such as 2 + 2 = 4, derived from the axiom1 + 1 = 2.
Example 13.6 illustrates in a simple manner the original intent of Post
systems as a mechanism for rigorously proving mathematical statements from a
set of axioms. It also shows the inherent awkwardness of such a completely
rigorous approach and why it is rarely used. But Post systems, even though they
are cumbersome for proving complicated theorems, are general models for
computation, as the next theorem shows.
Theorem 13.6
A language is recursively enumerable if and only if there exists some Post
system that generates it.
Proof: The arguments here are relatively simple and we sketch them briefly.
First, since a derivation by a Post system is completely mechanical, it can be
carried out on a Turing machine. Therefore, any language generated by a Post
system is recursively enumerable.
For the converse, remember that any recursively enumerable language is
generated by some unrestricted grammar G, having productions all of the form
x→y,
with x, y ∈ (V ∪ T)*. Given any unrestricted grammar G, we create a Post
system = (V ,C,A,P ), where V = {V 1 , V 2 },C N = V, C T = T, A = {S}, and
with productions
V 1x V 2 → V 1y V 2 ,
for every production x → y of the grammar. It is then an easy matter to show that
a w can be generated by the Post system II if and only if it is in the language
generated by G.
EXERCISES
1. For Σ = {a,b,c}, find a Post system that generates the following languages.