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 |
MARC
| LEADER | 00000caa a2200000 c 4500 | ||
|---|---|---|---|
| 001 | 1850966818 | ||
| 003 | DE-627 | ||
| 005 | 20230710185125.0 | ||
| 007 | cr uuu---uuuuu | ||
| 008 | 230626s1992 xx |||||o 00| ||eng c | ||
| 024 | 7 | |a 10.1007/BF01270394 |2 doi | |
| 035 | |a (DE-627)1850966818 | ||
| 035 | |a (DE-599)KXP1850966818 | ||
| 035 | |a (OCoLC)1389828019 | ||
| 040 | |a DE-627 |b ger |c DE-627 |e rda | ||
| 041 | |a eng | ||
| 084 | |a 28 |2 sdnb | ||
| 100 | 1 | |a Ambos-Spies, Klaus |d 1951- |e VerfasserIn |0 (DE-588)141551607 |0 (DE-627)629951861 |0 (DE-576)16006810X |4 aut | |
| 245 | 1 | 0 | |a Cappable recursively enumerable degrees and Post's program |c Klaus Ambos-Spies, André Nies |
| 264 | 1 | |c 1992 | |
| 300 | |a 6 | ||
| 336 | |a Text |b txt |2 rdacontent | ||
| 337 | |a Computermedien |b c |2 rdamedia | ||
| 338 | |a Online-Ressource |b cr |2 rdacarrier | ||
| 500 | |a Gesehen am 26.06.2023 | ||
| 520 | |a 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. | ||
| 650 | 4 | |a Cappable Degree | |
| 650 | 4 | |a Enumerable Degree | |
| 650 | 4 | |a Mathematical Logic | |
| 650 | 4 | |a Recursively Enumerable Degree | |
| 650 | 4 | |a Structural Property | |
| 700 | 1 | |a Nies, André |e VerfasserIn |0 (DE-588)113308426 |0 (DE-627)655097341 |0 (DE-576)33945864X |4 aut | |
| 773 | 0 | 8 | |i Enthalten in |t Archive for mathematical logic |d Berlin : Springer, 1988 |g 32(1992), 1, Seite 51-56 |h Online-Ressource |w (DE-627)235503215 |w (DE-600)1398309-X |w (DE-576)061935980 |x 1432-0665 |7 nnas |a Cappable recursively enumerable degrees and Post's program |
| 773 | 1 | 8 | |g volume:32 |g year:1992 |g number:1 |g pages:51-56 |g extent:6 |a Cappable recursively enumerable degrees and Post's program |
| 856 | 4 | 0 | |u https://doi.org/10.1007/BF01270394 |x Verlag |x Resolving-System |z lizenzpflichtig |3 Volltext |
| 951 | |a AR | ||
| 992 | |a 20230626 | ||
| 993 | |a Article | ||
| 994 | |a 1992 | ||
| 998 | |g 113308426 |a Nies, André |m 113308426:Nies, André |d 110000 |d 110100 |d 110000 |d 110400 |e 110000PN113308426 |e 110100PN113308426 |e 110000PN113308426 |e 110400PN113308426 |k 0/110000/ |k 1/110000/110100/ |k 0/110000/ |k 1/110000/110400/ |p 2 |y j | ||
| 998 | |g 141551607 |a Ambos-Spies, Klaus |m 141551607:Ambos-Spies, Klaus |d 110000 |d 110300 |e 110000PA141551607 |e 110300PA141551607 |k 0/110000/ |k 1/110000/110300/ |p 1 |x j | ||
| 999 | |a KXP-PPN1850966818 |e 4343474674 | ||
| BIB | |a Y | ||
| SER | |a journal | ||
| JSO | |a {"title":[{"title_sort":"Cappable recursively enumerable degrees and Post's program","title":"Cappable recursively enumerable degrees and Post's program"}],"person":[{"display":"Ambos-Spies, Klaus","roleDisplay":"VerfasserIn","role":"aut","family":"Ambos-Spies","given":"Klaus"},{"display":"Nies, André","roleDisplay":"VerfasserIn","role":"aut","family":"Nies","given":"André"}],"type":{"bibl":"article-journal","media":"Online-Ressource"},"note":["Gesehen am 26.06.2023"],"language":["eng"],"recId":"1850966818","origin":[{"dateIssuedDisp":"1992","dateIssuedKey":"1992"}],"id":{"eki":["1850966818"],"doi":["10.1007/BF01270394"]},"name":{"displayForm":["Klaus Ambos-Spies, André Nies"]},"physDesc":[{"extent":"6 S."}],"relHost":[{"recId":"235503215","language":["eng"],"note":["Gesehen am 04.07.25"],"disp":"Cappable recursively enumerable degrees and Post's programArchive for mathematical logic","type":{"media":"Online-Ressource","bibl":"periodical"},"part":{"extent":"6","volume":"32","text":"32(1992), 1, Seite 51-56","issue":"1","pages":"51-56","year":"1992"},"pubHistory":["Volume 27, issue 1 (March 1988)-"],"title":[{"title":"Archive for mathematical logic","title_sort":"Archive for mathematical logic"}],"physDesc":[{"extent":"Online-Ressource"}],"id":{"issn":["1432-0665"],"zdb":["1398309-X"],"eki":["235503215"]},"origin":[{"dateIssuedDisp":"1988-","dateIssuedKey":"1988","publisher":"Springer","publisherPlace":"Berlin ; Heidelberg ; New York"}]}]} | ||
| SRT | |a AMBOSSPIESCAPPABLERE1992 | ||