INTRODUCTION

Post initiated the study of the degrees of unsolvability with his 1944 address to the American Mathematical Society and his subsequent paper (Post 1944) based on that address. The paper concentrated on “a very limited portion of a subtheory of the hoped for general theory (of recursive functions)”, the recursively enumerable sets and their degrees. The algebraic approach adopted by Post to study this theory has given rise to the field of classical recursion theory.

Post's expressed interest in the theory of recursive functions was to present an intuitive development of the general theory which “stripped of its formalism … can be followed, if not indeed pursued, by a mathematician, layman though he be in this formal field”. Post connected this theory to unsolvability questions in algebra, an area more familiar to the layman. Connections of recursion theory to algebra have since been actively studied by many researchers. The intuitive approach to recursion theory introduced by Post has been adopted by researchers in the field. The proof techniques which have been developed involve very complex combinatorial arguments which are not readily accessible to most mathematicians. But the results proved by these methods can be used to describe a global theory which is more readily accessible to mathematicians.

Post's paper introduced a problem which became the central problem of recursion theory until its solution by Friedberg (1957b) and Mucnik (1956) in 1956. Post showed that there is a least degree of unsolvability, O, and a greatest recursively enumerable degree of unsolvability, O', and asked whether any other recursively enumerable degrees existed.