Cappable recursively enumerable degrees and Post's program

Archive for Mathematical Logic 32 (1):51-56 (1992)
  Copy   BIBTEX

Abstract

We give a simple structural property which characterizes the r.e. sets whose (Turing) degrees are cappable. Since cappable degrees are incomplete, this may be viewed as a solution of Post's program, which asks for a simple structural property of nonrecursive r.e. sets which ensures incompleteness

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 90,616

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

Bounding cappable degrees.Angsheng Li - 2000 - Archive for Mathematical Logic 39 (5):311-352.
The computably enumerable degrees are locally non-cappable.Matthew B. Giorgi - 2004 - Archive for Mathematical Logic 43 (1):121-139.
The cupping theorem in r/m.Sui Yuefei & Zhang Zaiyue - 1999 - Journal of Symbolic Logic 64 (2):643-650.
Recursively enumerable generic sets.Wolfgang Maass - 1982 - Journal of Symbolic Logic 47 (4):809-823.
The Isolated D. R. E. Degrees are Dense in the R. E. Degrees.Geoffrey Laforte - 1996 - Mathematical Logic Quarterly 42 (1):83-103.
On a conjecture of Lempp.Angsheng Li - 2000 - Archive for Mathematical Logic 39 (4):281-309.
Complementation in the Turing degrees.Theodore A. Slaman & John R. Steel - 1989 - Journal of Symbolic Logic 54 (1):160-176.
Quasi-complements of the cappable degrees.Guohua Wu - 2004 - Mathematical Logic Quarterly 50 (2):189.
On the r.e. predecessors of d.r.e. degrees.Shamil Ishmukhametov - 1999 - Archive for Mathematical Logic 38 (6):373-386.

Analytics

Added to PP
2013-11-23

Downloads
16 (#774,541)

6 months
2 (#668,348)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Definable properties of the computably enumerable sets.Leo Harrington & Robert I. Soare - 1998 - Annals of Pure and Applied Logic 94 (1-3):97-125.

Add more citations

References found in this work

No references found.

Add more references