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...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article (Journal) |
| Language: | English |
| Published: |
1992
|
| In: |
Archive for mathematical logic
Year: 1992, Volume: 32, Issue: 1, Pages: 51-56 |
| ISSN: | 1432-0665 |
| DOI: | 10.1007/BF01270394 |
| Online Access: | Verlag, lizenzpflichtig, Volltext: https://doi.org/10.1007/BF01270394
|
| Author Notes: | Klaus Ambos-Spies, André Nies |
| Summary: | 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. |
|---|---|
| Item Description: | Gesehen am 26.06.2023 |
| Physical Description: | Online Resource |
| ISSN: | 1432-0665 |
| DOI: | 10.1007/BF01270394 |