首页 | 本学科首页   官方微博 | 高级检索  
     检索      


Fixed point theorems for precomplete numberings
Authors:Henk Barendregt  Sebastiaan A Terwijn
Institution: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 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号