Archive for Mathematical Logic 41 (5):483-495 (2002)
AbstractIf 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
Added to PP
Historical graph of downloads
References found in this work
No references found.
Citations of this work
No citations found.
Similar books and articles
Review: T. G. McLaughlin, Retraceable Sets and Recursive Permutations. [REVIEW]Fred J. Sansone - 1968 - Journal of Symbolic Logic 33 (1):114-114.
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.
Review: Louise Hay, On Creative Sets and Indices of Partial Recursive Functions; Louise Hay, Isomorphism Types of Index Sets of Partial Recursive Functions; Louise Hay, Index Sets of Finite Classes of Recursively Enumerable Sets. [REVIEW]Forbes D. Lewis - 1974 - Journal of Symbolic Logic 39 (1):186-187.
Review: K. I. Appel, No Recursively Enumerable Set is the Union of Finitely Many Immune Retraceable Sets. [REVIEW]C. E. M. Yates - 1968 - Journal of Symbolic Logic 33 (4):621-621.
On a Class of Recursively Enumerable Sets.Farzad Didehvar - 1999 - Mathematical Logic Quarterly 45 (4):467-470.
A Blend of Methods of Recursion Theory and Topology: A Π1 0 Tree of Shadow Points. [REVIEW]Iraj Kalantari & Larry Welch - 2004 - Archive for Mathematical Logic 43 (8):991-1008.
J. C. E. Dekker and J. Myhill. Retraceable sets. Canadian journal of mathematics, vol. 10 , pp. 357–373. [REVIEW]A. Nerode - 1962 - Journal of Symbolic Logic 27 (1):84-85.
Review: T. G. McLaughlin, Co-Immune Retraceable Sets. [REVIEW]C. E. M. Yates - 1967 - Journal of Symbolic Logic 32 (1):123-123.
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.
Computable Real‐Valued Functions on Recursive Open and Closed Subsets of Euclidean Space.Qing Zhou - 1996 - Mathematical Logic Quarterly 42 (1):379-409.
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.