Max and min limiters

Archive for Mathematical Logic 41 (5):483-495 (2002)

If and the function is partial recursive, it is easily seen that A is recursive. In this paper, we weaken this hypothesis in various ways (and similarly for ``min'' in place of ``max'') and investigate what effect this has on the complexity of A. We discover a sharp contrast between retraceable and co-retraceable sets, and we characterize sets which are the union of a recursive set and a co-r.e., retraceable set. Most of our proofs are noneffective. Several open questions are raised
Keywords Legacy
Categories (categorize this paper)
DOI 10.1007/s001530100121
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

Our Archive

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 48,987
External links

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library

References found in this work BETA

No references found.

Add more references

Citations of this work BETA

No citations found.

Add more citations

Similar books and articles

A Fine Structure in the Theory of Isols.Joseph Barback - 1998 - Mathematical Logic Quarterly 44 (2):229-264.
Weakly Semirecursive Sets.Carl G. Jockusch & James C. Owings - 1990 - Journal of Symbolic Logic 55 (2):637-644.
On a Class of Recursively Enumerable Sets.Farzad Didehvar - 1999 - Mathematical Logic Quarterly 45 (4):467-470.
An Invariance Notion in Recursion Theory.Robert E. Byerly - 1982 - Journal of Symbolic Logic 47 (1):48-66.
Unary Primitive Recursive Functions.Daniel E. Severin - 2008 - Journal of Symbolic Logic 73 (4):1122-1138.
A Note on Recursive Models of Set Theories.Domenico Zambella & Antonella Mancini - 2001 - Notre Dame Journal of Formal Logic 42 (2):109-115.
Ramsey's Theorem for Pairs and Provably Recursive Functions.Alexander Kreuzer & Ulrich Kohlenbach - 2009 - Notre Dame Journal of Formal Logic 50 (4):427-444.


Added to PP index

Total views
11 ( #747,643 of 2,310,364 )

Recent downloads (6 months)
1 ( #754,118 of 2,310,364 )

How can I increase my downloads?


My notes

Sign in to use this feature