Cappable recursively enumerable degrees and Post's program
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 incompletene...
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Dokumenttyp: | Article (Journal) |
| Sprache: | Englisch |
| Veröffentlicht: |
1992
|
| In: |
Archive for mathematical logic
Year: 1992, Jahrgang: 32, Heft: 1, Pages: 51-56 |
| ISSN: | 1432-0665 |
| DOI: | 10.1007/BF01270394 |
| Online-Zugang: | Verlag, lizenzpflichtig, Volltext: https://doi.org/10.1007/BF01270394
|
| Verfasserangaben: | Klaus Ambos-Spies, André Nies |
| Zusammenfassung: | 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. |
|---|---|
| Beschreibung: | Gesehen am 26.06.2023 |
| Beschreibung: | Online Resource |
| ISSN: | 1432-0665 |
| DOI: | 10.1007/BF01270394 |