Fixed point theorems for precomplete numberings |
| |
Authors: | Henk Barendregt Sebastiaan A. Terwijn |
| |
Affiliation: | 1. Radboud University Nijmegen, Institute for Computing and Information Sciences, P.O. Box 9010, 6500 GL Nijmegen, the Netherlands;2. Radboud University Nijmegen, Department of Mathematics, P.O. Box 9010, 6500 GL Nijmegen, the Netherlands |
| |
Abstract: | In the context of his theory of numberings, Ershov showed that Kleene's recursion theorem holds for any precomplete numbering. We discuss various generalizations of this result. Among other things, we show that Arslanov's completeness criterion also holds for every precomplete numbering, and we discuss the relation with Visser's ADN theorem, as well as the uniformity or nonuniformity of the various fixed point theorems. Finally, we base numberings on partial combinatory algebras and prove a generalization of Ershov's theorem in this context. |
| |
Keywords: | Corresponding author. 03D25 03B40 03D45 03D80 Precomplete numberings Ershov recursion theorem ADN theorem Arslanov completeness criterion |
本文献已被 ScienceDirect 等数据库收录! |
|