Splitting theorems in recursion theory

Annals of Pure and Applied Logic 65 (1):1-106 (1993)

Abstract
A splitting of an r.e. set A is a pair A1, A2 of disjoint r.e. sets such that A1 A2 = A. Theorems about splittings have played an important role in recursion theory. One of the main reasons for this is that a splitting of A is a decomposition of A in both the lattice, , of recursively enumerable sets and in the uppersemilattice, R, of recursively enumerable degrees . Thus splitting theor ems have been used to obtain results about the structure of , the structure of R, and the relationship between the two structures. Furthermore it is fair to say that questions about splittings have often generated important new technical developments in recursion theory. In this article we survey most of the results and techniques associated with splitting properties of r.e. sets in ordinary recursion theory
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.1016/0168-0072(93)90234-5
Options
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: 43,044
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

The D.R.E. Degrees Are Not Dense.S. Cooper, Leo Harrington, Alistair Lachlan, Steffen Lempp & Robert Soare - 1991 - Annals of Pure and Applied Logic 55 (2):125-151.

View all 48 references / Add more references

Citations of this work BETA

Some Orbits for E.Peter Cholak, Rod Downey & Eberhard Herrmann - 2001 - Annals of Pure and Applied Logic 107 (1-3):193-226.
Maximal Contiguous Degrees.Peter Cholak, Rod Downey & Stephen Walk - 2002 - Journal of Symbolic Logic 67 (1):409-437.

View all 14 citations / Add more citations

Similar books and articles

Weak Cardinality Theorems.Till Tantau - 2005 - Journal of Symbolic Logic 70 (3):861 - 878.
Splitting Theorems and the Jump Operator.R. G. Downey & Richard A. Shore - 1998 - Annals of Pure and Applied Logic 94 (1-3):45-52.
Ray-Splitting Billiards.R. Blümel, P. M. Koch & L. Sirko - 2001 - Foundations of Physics 31 (2):269-281.
Analytic Countably Splitting Families.Otmar Spinas - 2004 - Journal of Symbolic Logic 69 (1):101-117.
A Theory of Rules for Enumerated Classes of Functions.Andreas Schlüter - 1995 - Archive for Mathematical Logic 34 (1):47-63.
Recursion Theory.Anil Nerode & Richard A. Shore (eds.) - 1985 - American Mathematical Society.
Generalized Recursion Theory.Jens Erik Fenstad & Peter G. Hinman (eds.) - 1974 - New York: American Elsevier Pub. Co..
Canonical Forms and Hierarchies in Generalized Recursion Theory.Phokion G. Kolaitis - 1985 - In Anil Nerode & Richard A. Shore (eds.), Recursion Theory. American Mathematical Society. pp. 42--139.
Axiomatic Recursion Theory and the Continuous Functionals.Simon Thompson - 1985 - Journal of Symbolic Logic 50 (2):442-450.

Analytics

Added to PP index
2014-01-16

Total views
9 ( #765,386 of 2,260,175 )

Recent downloads (6 months)
1 ( #905,492 of 2,260,175 )

How can I increase my downloads?

Downloads

My notes

Sign in to use this feature