Max and min limiters

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

Abstract

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

Download options

PhilArchive



    Upload a copy of this work     Papers currently archived: 72,743

External links

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

Through your library

Analytics

Added to PP
2013-12-01

Downloads
11 (#859,575)

6 months
1 (#387,390)

Historical graph of downloads
How can I increase my downloads?

References found in this work

No references found.

Add more references

Citations of this work

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.