Myhill's work in recursion theory

DOI10.1016/0168-0072(92)90067-AMaRDI QIDQ1192344zbMATH OpenOpenAlexFDO

Publication date 27 September 1992

Published in Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0168-0072(92)90067-a

Baire category combinatorial functions creative sets isols isomorphism theorems recursive equivalence types

History of mathematics in the 20th century (01A60) History of mathematical logic and foundations (03-03) Recursive functions and relations, subrecursive hierarchies (03D20) Recursively (computably) enumerable sets and degrees (03D25) Recursive equivalence types of sets and structures, isols (03D50)

Review text

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.

Recommendations

Cites work

Cited in

(1)

scientific article; zbMATH DE number 4160737 (Why is no real title available?)

This page was built for publication: Myhill's work in recursion theory

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1192344)