Diagonal fixed points in algebraic recursion theory |
| |
Authors: | Jordan Zashev |
| |
Institution: | (1) Institute of Mathematics and Informatics, G.Bonchev Bl. 8, Sofia, 1113, Bulgaria |
| |
Abstract: | The relation between least and diagonal fixed points is a well known and completely studied question for a large class of
partially ordered models of the lambda calculus and combinatory logic. Here we consider this question in the context of algebraic
recursion theory, whose close connection with combinatory logic recently become apparent. We find a comparatively simple and
rather weak general condition which suffices to prove the equality of least fixed points with canonical (corresponding to
those produced by the Curry combinator in lambda calculus) diagonal fixed points in a class of partially ordered algebras
which covers both combinatory spaces of Skordev and operative spaces of Ivanov. Especially, this yields an essential improvement
of the axiomatization of recursion theory via combinatory spaces.
Supported in part by the Ministry of Education and Science of Republic of Bulgaria, contract No 705 |
| |
Keywords: | Algebraic recursion theory-Combinatory logic |
本文献已被 SpringerLink 等数据库收录! |
|