Preamble: Kleene [15], Post [42] and Mostowski [38]

The two seminal articles of Kleene and Post were published within a year of each other[1] and have had a deciding influence on the development of the theory of unsolvability up until today. Mostowski wrote his [38] in ignorance of Kleene [15], he discovered independently many of Kleene’s results and he asked some questions which influenced profoundly the development of the subject. We will discuss it in Sect. 5.1.4.

Kleene and Post approached “the undecidable” in markedly different ways: they chose different ways to measure the complexity of undecidable sets, they introduced different methods of proof and they employed distinct “styles of exposition”. The results in them and in the research they inspired are closely related, of course, as they are ultimately about the same objects—the undecidable relations on the natural numbers; but there is no doubting the fact that they led to two different traditions in the theory of unsolvability with many of the best researchers in one of them (sometimes) knowing very little of what has happened in the other.

The first, key question was how to measure the unsolvability of a set of natural numbers.

  • [1] Kleene had presented much of his [15] in a meeting of the American Mathematical Society inSeptember 1940. I do not know when Post obtained the results in his [42].
 
Source
< Prev   CONTENTS   Source   Next >