Splitting theorems in recursion theory

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

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

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 74,662

External links

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

Through your library

Similar books and articles

Recursion Theory for Metamathematics.Raymond Merrill Smullyan - 1993 - Oxford, England: Oxford University Press.
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.
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
2014-01-16

Downloads
12 (#798,201)

6 months
1 (#419,921)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Some Orbits for E.Peter Cholak, Rod Downey & Eberhard Herrmann - 2001 - Annals of Pure and Applied Logic 107 (1-3):193-226.
Some Properties of R-Maximal Sets and Q 1,N -Reducibility.R. Sh Omanadze - 2015 - Archive for Mathematical Logic 54 (7-8):941-959.
Effectively and Noneffectively Nowhere Simple Sets.Valentina S. Harizanov - 1996 - Mathematical Logic Quarterly 42 (1):241-248.

View all 15 citations / Add more citations