Diagonal fixed points in algebraic recursion theory

Archive for Mathematical Logic 44 (8):973-994 (2005)
  Copy   BIBTEX

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

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 74,466

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

On the Recursion Theorem in Iterative Operative Spaces.J. Zashev - 2001 - Journal of Symbolic Logic 66 (4):1727-1748.
Diagonalization and Self-Reference.Raymond Merrill Smullyan - 1994 - Oxford, England: Clarendon Press.
The Church-Rosser Property in Symmetric Combinatory Logic.Katalin Bimbó - 2005 - Journal of Symbolic Logic 70 (2):536 - 556.
A General Form of Relative Recursion.Jaap van Oosten - 2006 - Notre Dame Journal of Formal Logic 47 (3):311-318.
Recursion Theory and the Lambda-Calculus.Robert E. Byerly - 1982 - Journal of Symbolic Logic 47 (1):67-83.
ŁΠ Logic with Fixed Points.Luca Spada - 2008 - Archive for Mathematical Logic 47 (7-8):741-763.
A Theory of Rules for Enumerated Classes of Functions.Andreas Schlüter - 1995 - Archive for Mathematical Logic 34 (1):47-63.
Some Unifying Fixed Point Principles.Raymond M. Smullyan - 1991 - Studia Logica 50 (1):129 - 141.

Analytics

Added to PP
2013-11-23

Downloads
16 (#662,530)

6 months
1 (#417,143)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

No citations found.

Add more citations