Kleene [15] Versus Post [42]

There is little overlap between these two papers, except that they both characterize the recursive sets as exactly those which are r.e. and have r.e. complements (Post’s Theorem). Beyond that, Post limits himself to the complexity structure of r.e. sets which comprise precisely Kleene’s —about which Kleene says nothing nontrivial.

Both papers are brilliant examples of concept formation, the identification of fundamental notions which is characteristic of some of the best work in logic. Post also proves several non-trivial technical results, some by very clever constructions; there is little of this in the Kleene paper, whose technical results are proved mostly by seemingly routine computations.

Then there is the style of exposition: Post is eloquent, even colorful. He introduces suggestive, descriptive terms (complete, creative, simple) which give life to the formulation of his results and right in his first paragraph, he declares that his purpose is

to demonstrate by example that this concept [of recursive function] admits .. .of an intuitive development which can be followed, if not indeed pursued, by a mathematician, layman though he be in this formal field.[1]

His exhortation to explain rather than detail proofs resonated strongly in the work of those who followed him, sometimes with beautiful results, e.g., in the classic Rogers [45]. At the other end, Kleene is dry, formal, and more worried about whether he has a constructive (intuitionistic) proof than if his proof is easily comprehensible—and to some extent, these traits persisted in the writings of those who followed him.

  • [1] He also said that “.with a few exceptions explicitly so noted, we have obtained formal proofsof all the consequently mathematical theorems here developed informally”, and it is clear that thepurely intuitive approach can only go so far: we cannot hope to prove that (say) the word problemfor semigroups is unsolvable on the basis of our intuitions about computability, without a rigorousdefinition of recursive functions and an appeal to the Church-Turing Thesis.
< Prev   CONTENTS   Source   Next >