Myhill's work in recursion theory (Q1192344): Difference between revisions

The authors discuss, from the present-day point of view, John Myhill's contribution to recursion theory. The isomorphism theorems are presented using a new, uniform method of proof. J. Myhill's theorem on isomorphism of creative sets, the theorem on recursive equivalence (recursive analogue of Cantor-Bernstein theorem), his investigations on combinatorial functions and the application of the category method to recursion theory are thoroughly discussed. New and detailed proofs to most of these theorems are given. For example, the Myhill results stating that (i) there are isols which are neither even nor odd, and (ii) the ring \(\Lambda^*\) has zero divisors, are reproved using the Baire category theorem. A theorem on recursive combinatorial functions published by Myhill without proof is provided with a proof ``he might have done''. A short guide to the references is given.