Bounds in the Turing reducibility of functions

&
Mathematical Logic Quarterly 38 (1):423-430 (1992)
  Copy   BIBTEX

Abstract

A hierarchy of functions with respect to their role as bounds in the Turing reducibility of functions is introduced and studied. This hierarchy leads to a certain notion of incompressibility of sets which is also investigated

Categories

Add categories

Keywords

Reprint years

DOI

10.1002/malq.19920380141

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 91,202

External links

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

Through your library

My notes

Similar books and articles

A New Reducibility between Turing‐ and wtt‐Reducibility.Sui Yuefei - 1994 - Mathematical Logic Quarterly 40 (1):106-110.
The existential theory of the poset of R.e. Degrees with a predicate for single jump reducibility.Steffen Lempp & Manuel Lerman - 1992 - Journal of Symbolic Logic 57 (3):1120-1130.
On Nondeterminism, Enumeration Reducibility and Polynomial Bounds.Kate Copestake - 1997 - Mathematical Logic Quarterly 43 (3):287-310.
Bounds in weak truth-table reducibility.Karol Habart - 1991 - Notre Dame Journal of Formal Logic 32 (2):233-241.
Strong Enumeration Reducibilities.Roland Sh Omanadze & Andrea Sorbi - 2006 - Archive for Mathematical Logic 45 (7):869-912.
A characterization of the Δ⁰₂ hyperhyperimmune sets.Roland Sh Omanadze & Andrea Sorbi - 2008 - Journal of Symbolic Logic 73 (4):1407-1415.
About Segment Complexity of Turing Reductions.Valeriy K. Bulitko - 1999 - Mathematical Logic Quarterly 45 (4):561-571.
Wtt-degrees and t-degrees of R.e. Sets.Michael Stob - 1983 - Journal of Symbolic Logic 48 (4):921-930.
The Logic of Interactive Turing Reduction.Giorgi Japaridze - 2007 - Journal of Symbolic Logic 72 (1):243 - 276.
Bounded enumeration reducibility and its degree structure.Daniele Marsibilio & Andrea Sorbi - 2012 - Archive for Mathematical Logic 51 (1-2):163-186.
Supervenience and reducibility: An odd couple.Ausonio Marras - 1994 - Philosophical Quarterly 44 (171):215-222.
On the logic of reducibility: Axioms and examples. [REVIEW]Karl-Georg Niebergall - 2000 - Erkenntnis 53 (1-2):27-61.
Post's Problem for Reducibilities of Bounded Complexity.Valeriy K. Bulitko - 2002 - Mathematical Logic Quarterly 48 (3):367-373.
On Subcreative Sets and S-Reducibility.John T. Gill Iii & Paul H. Morris - 1974 - Journal of Symbolic Logic 39 (4):669 - 677.

Analytics

Added to PP
2013-12-01

Downloads
11 (#1,070,627)

6 months
1 (#1,444,594)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

No citations found.

Add more citations

References found in this work

Add more references