Undecidability and 1-types in the recursively enumerable degrees
Ambos-Spies, K. and R.A. Shore, Undecidability and 1-types in the recursively enumerable degrees, Annals of Pure and Applied Logic 63 (1993) 3-37. We show that the theory of the partial ordering of recursively enumerable Turing degrees is undecidable and has uncountably many 1-types. In contrast to...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article (Journal) |
| Language: | English |
| Published: |
1993
|
| In: |
Annals of pure and applied logic
Year: 1993, Volume: 63, Issue: 1, Pages: 3-37 |
| ISSN: | 1873-2461 |
| DOI: | 10.1016/0168-0072(93)90206-S |
| Online Access: | Verlag, lizenzpflichtig, Volltext: https://doi.org/10.1016/0168-0072(93)90206-S Verlag, lizenzpflichtig, Volltext: https://www.sciencedirect.com/science/article/pii/016800729390206S 
|
| Author Notes: | Klaus Ambos-Spies, Richard A. Shore |
MARC
| LEADER | 00000caa a2200000 c 4500 | ||
|---|---|---|---|
| 001 | 1848773668 | ||
| 003 | DE-627 | ||
| 005 | 20230710184029.0 | ||
| 007 | cr uuu---uuuuu | ||
| 008 | 230612s1993 xx |||||o 00| ||eng c | ||
| 024 | 7 | |a 10.1016/0168-0072(93)90206-S |2 doi | |
| 035 | |a (DE-627)1848773668 | ||
| 035 | |a (DE-599)KXP1848773668 | ||
| 035 | |a (OCoLC)1389827809 | ||
| 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 Undecidability and 1-types in the recursively enumerable degrees |c Klaus Ambos-Spies, Richard A. Shore |
| 264 | 1 | |c 1993 | |
| 300 | |a 35 | ||
| 336 | |a Text |b txt |2 rdacontent | ||
| 337 | |a Computermedien |b c |2 rdamedia | ||
| 338 | |a Online-Ressource |b cr |2 rdacarrier | ||
| 500 | |a Elektronische Reproduktion der Druck-Ausgabe 13. Mai 2002 | ||
| 500 | |a Gesehen am 12.06.2023 | ||
| 520 | |a Ambos-Spies, K. and R.A. Shore, Undecidability and 1-types in the recursively enumerable degrees, Annals of Pure and Applied Logic 63 (1993) 3-37. We show that the theory of the partial ordering of recursively enumerable Turing degrees is undecidable and has uncountably many 1-types. In contrast to the original proof of the former which used a very complicated O''' argument our proof proceeds by a much simpler infinite injury argument. Moreover, it combines with the permitting technique to get similar results for any ideal of the r.e. degrees. | ||
| 700 | 1 | |a Shore, Richard A. |d 1946- |e VerfasserIn |0 (DE-588)172660513 |0 (DE-627)697594041 |0 (DE-576)133519058 |4 aut | |
| 773 | 0 | 8 | |i Enthalten in |t Annals of pure and applied logic |d Amsterdam [u.a.] : Elsevier, 1983 |g 63(1993), 1, Seite 3-37 |h Online-Ressource |w (DE-627)265784409 |w (DE-600)1466371-5 |w (DE-576)074891073 |x 1873-2461 |7 nnas |a Undecidability and 1-types in the recursively enumerable degrees |
| 773 | 1 | 8 | |g volume:63 |g year:1993 |g number:1 |g pages:3-37 |g extent:35 |a Undecidability and 1-types in the recursively enumerable degrees |
| 856 | 4 | 0 | |u https://doi.org/10.1016/0168-0072(93)90206-S |x Verlag |x Resolving-System |z lizenzpflichtig |3 Volltext |
| 856 | 4 | 0 | |u https://www.sciencedirect.com/science/article/pii/016800729390206S |x Verlag |z lizenzpflichtig |3 Volltext |
| 951 | |a AR | ||
| 992 | |a 20230612 | ||
| 993 | |a Article | ||
| 994 | |a 1993 | ||
| 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-PPN1848773668 |e 4331362345 | ||
| BIB | |a Y | ||
| SER | |a journal | ||
| JSO | |a {"physDesc":[{"extent":"35 S."}],"relHost":[{"type":{"media":"Online-Ressource","bibl":"periodical"},"disp":"Undecidability and 1-types in the recursively enumerable degreesAnnals of pure and applied logic","note":["Gesehen am 09.11.2020"],"language":["eng"],"recId":"265784409","pubHistory":["24.1983 -"],"part":{"year":"1993","issue":"1","pages":"3-37","text":"63(1993), 1, Seite 3-37","volume":"63","extent":"35"},"title":[{"title":"Annals of pure and applied logic","title_sort":"Annals of pure and applied logic"}],"physDesc":[{"extent":"Online-Ressource"}],"origin":[{"dateIssuedDisp":"1983-","publisher":"Elsevier","dateIssuedKey":"1983","publisherPlace":"Amsterdam [u.a.]"}],"id":{"zdb":["1466371-5"],"eki":["265784409"],"issn":["1873-2461"]}}],"origin":[{"dateIssuedKey":"1993","dateIssuedDisp":"1993"}],"id":{"eki":["1848773668"],"doi":["10.1016/0168-0072(93)90206-S"]},"name":{"displayForm":["Klaus Ambos-Spies, Richard A. Shore"]},"type":{"media":"Online-Ressource","bibl":"article-journal"},"note":["Elektronische Reproduktion der Druck-Ausgabe 13. Mai 2002","Gesehen am 12.06.2023"],"language":["eng"],"recId":"1848773668","title":[{"title":"Undecidability and 1-types in the recursively enumerable degrees","title_sort":"Undecidability and 1-types in the recursively enumerable degrees"}],"person":[{"given":"Klaus","family":"Ambos-Spies","role":"aut","display":"Ambos-Spies, Klaus","roleDisplay":"VerfasserIn"},{"given":"Richard A.","family":"Shore","role":"aut","display":"Shore, Richard A.","roleDisplay":"VerfasserIn"}]} | ||
| SRT | |a AMBOSSPIESUNDECIDABI1993 | ||