ट्यूरिंग डिग्री

कंप्यूटर विज्ञान और गणितीय तर्क में ट्यूरिंग डिग्री (एलन ट्यूरिंग के नाम पर) या प्राकृतिक संख्याओं के एक सेट की असम्बद्धता की डिग्री सेट की एल्गोरिथम असम्बद्धता के स्तर को मापती है।

सिंहावलोकन

कम्प्यूटेबिलिटी संगणनीयता सिद्धांत ट्यूरिंग डिग्री की अवधारणा मौलिक है, जहां प्राकृतिक संख्याओं के सेट को अक्सर निर्णय समस्याओं के रूप में माना जाता है। एक सेट की ट्यूरिंग डिग्री इस बात का एक उपाय है कि सेट से जुड़ी निर्णय समस्या को हल करना कितना मुश्किल है, यह निर्धारित करने के लिए कि दिए गए सेट में एक मनमाना संख्या है या नहीं।

दो सेट ट्यूरिंग समतुल्य हैं यदि उनके पास समान स्तर की अघुलनशीलता है; प्रत्येक ट्यूरिंग डिग्री ट्यूरिंग समतुल्य सेटों का एक संग्रह है, ताकि दो सेट अलग-अलग ट्यूरिंग डिग्री में हों, जब वे ट्यूरिंग समकक्ष नहीं हैं। इसके अलावा, ट्यूरिंग डिग्री आंशिक क्रम हैं, ताकि यदि एक सेट 'एक्स' की ट्यूरिंग डिग्री एक सेट 'वाई' की ट्यूरिंग डिग्री से कम हो, तो कोई भी (संभवतः गैर-गणना योग्य) प्रक्रिया जो सही ढंग से तय करती है कि संख्याएं हैं या नहीं Y में हैं को प्रभावी रूप से एक ऐसी प्रक्रिया में परिवर्तित किया जा सकता है जो सही ढंग से यह तय करती है कि संख्याएँ X में हैं या नहीं। यह इस अर्थ में है कि एक सेट की ट्यूरिंग डिग्री इसके एल्गोरिथम असम्बद्धता के स्तर से मेल खाती है।

ट्यूरिंग डिग्रियों को एमिल लियोन पोस्ट (1944) द्वारा पेश किया गया था, और स्टीफन कोल क्लेन और पोस्ट (1954) द्वारा कई मौलिक परिणाम स्थापित किए गए थे। तब से ट्यूरिंग डिग्रियां गहन शोध का क्षेत्र रही हैं। क्षेत्र में कई प्रूफ एक प्रूफ तकनीक का उपयोग करते हैं जिसे प्राथमिकता पद्धति के रूप में जाना जाता है।

ट्यूरिंग तुल्यता

Main article: Turing reduction

इस लेख के शेष भाग के लिए, शब्द समुच्चय प्राकृतिक संख्याओं के समुच्चय को संदर्भित करेगा। एक समुच्चय X को एक समुच्चय Y के लिए 'ट्यूरिंग रिड्यूसिबल' कहा जाता है यदि एक ओरेकल ट्यूरिंग मशीन है जो Y में सदस्यता के लिए एक ऑरेकल दिए जाने पर X में सदस्यता तय करती है। अंकन X ≤_T Y इंगित करता है कि X, Y के लिए ट्यूरिंग रिड्यूसिबल है।

दो सेट X और Y को 'ट्यूरिंग समतुल्य' के रूप में परिभाषित किया गया है यदि X, Y के लिए ट्यूरिंग रिड्यूसिबल है और Y, X के लिए ट्यूरिंग रिड्यूसिबल है। नोटेशन X ≡_T Y इंगित करता है कि X और Y ट्यूरिंग समकक्ष हैं। संबंध ≡_T एक तुल्यता संबंध के रूप में देखा जा सकता है, जिसका अर्थ है कि सभी सेट X, Y और Z के लिए:

• एक्स ≡_T एक्स
• एक्स ≡_T Y का तात्पर्य Y ≡ से है_T एक्स
• यदि एक्स ≡_T वाई और वाई ≡_T जेड तो एक्स ≡_T जेड

एक 'ट्यूरिंग डिग्री' संबंध ≡ का एक तुल्यता वर्ग है_T. संकेतन [X] एक सेट X वाले तुल्यता वर्ग को दर्शाता है। ट्यूरिंग डिग्री के पूरे संग्रह को निरूपित किया जाता है ${\mathcal {D}}$.

ट्यूरिंग डिग्री का एक आंशिक क्रम ≤ परिभाषित है ताकि [X] ≤ [Y] अगर और केवल अगर X ≤_T वाई। एक अद्वितीय ट्यूरिंग डिग्री है जिसमें सभी गणना योग्य सेट शामिल हैं, और यह डिग्री हर दूसरी डिग्री से कम है। इसे '0' (शून्य) के रूप में दर्शाया गया है क्योंकि यह पोसेट का सबसे छोटा तत्व है ${\mathcal {D}}$. (ट्यूरिंग डिग्री के लिए बोल्डफेस नोटेशन का उपयोग करना सामान्य है, ताकि उन्हें सेट से अलग किया जा सके। जब कोई भ्रम नहीं हो सकता है, जैसे [एक्स] के साथ, बोल्डफेस आवश्यक नहीं है।)

किसी भी सेट X और Y के लिए, X 'जॉइन' Y, लिखित X ⊕ Y, को सेट के मिलन के रूप में परिभाषित किया गया है {2n : n ∈ X} और {2m+1 : m ∈ Y}. X ⊕ Y की ट्यूरिंग डिग्री X और Y की डिग्री का जोड़ (गणित) है। इस प्रकार ${\mathcal {D}}$ एक ज्वाइन-सेमी-जाली है। डिग्री a और b की सबसे छोटी ऊपरी सीमा को a ∪ b द्वारा निरूपित किया जाता है। ह ज्ञात है कि ${\mathcal {D}}$ एक जाली (आदेश) नहीं है, क्योंकि डिग्री के जोड़े हैं जिनमें कोई सबसे बड़ी निचली सीमा नहीं है।

किसी भी सेट एक्स के लिए नोटेशन एक्स' ऑरैकल मशीनों के सूचकांकों के सेट को दर्शाता है जो एक्स को ऑरैकल के रूप में उपयोग करते समय रुक जाता है (जब इनपुट के रूप में उनकी अनुक्रमणिका दी जाती है)। सेट X' को X का 'ट्यूरिंग कूदो' कहा जाता है। एक डिग्री [X] के ट्यूरिंग जंप को डिग्री [X'] के रूप में परिभाषित किया जाता है; यह एक मान्य परिभाषा है क्योंकि X' ≡_T Y' जब भी X ≡_T Y. एक प्रमुख उदाहरण '0 है, रुकने की समस्या की डिग्री।

ट्यूरिंग डिग्री के मूल गुण

• प्रत्येक ट्यूरिंग डिग्री गणनीय रूप से अनंत होती है, अर्थात इसमें सटीक रूप से समाहित होता है $\aleph _{0}$ सेट।
• वहाँ हैं $2^{\aleph _{0}}$ विशिष्ट ट्यूरिंग डिग्री।
• प्रत्येक डिग्री के लिए सख्त असमानता a <a′ रखती है।
• प्रत्येक डिग्री a के लिए, a के नीचे की डिग्री का समुच्चय गणनीय समुच्चय है। a से बड़े अंशों का समुच्चय है $2^{\aleph _{0}}$.

ट्यूरिंग डिग्री की संरचना

ट्यूरिंग डिग्रियों की संरचना में काफी शोध किया गया है। निम्नलिखित सर्वेक्षण कई ज्ञात परिणामों में से केवल कुछ को सूचीबद्ध करता है। एक सामान्य निष्कर्ष जो शोध से निकाला जा सकता है वह यह है कि ट्यूरिंग डिग्रियों की संरचना अत्यंत जटिल है।

आदेश गुण

• न्यूनतम डिग्री हैं। एक डिग्री 'न्यूनतम' है अगर एक शून्य नहीं है और 0 और एक के बीच कोई डिग्री नहीं है। इस प्रकार डिग्रियों पर क्रम संबंध सघन क्रम नहीं है।
• ट्यूरिंग डिग्रियों को ≤_T.
• वास्तव में, प्रत्येक गैर शून्य डिग्री के लिए एक डिग्री बी अतुलनीय है।
• का एक सेट है $2^{\aleph _{0}}$ जोड़ीदार अतुलनीय ट्यूरिंग डिग्री।
• डिग्रियों के ऐसे जोड़े हैं जिनकी कोई सबसे बड़ी निचली सीमा नहीं है। इस प्रकार ${\mathcal {D}}$ जाली नहीं है।
• हर काउंटेबल आंशिक रूप से ऑर्डर किए गए सेट को ट्यूरिंग डिग्री में एम्बेड किया जा सकता है।
• एक अनंत सख्ती से बढ़ता हुआ क्रम a₁, ए₂, ... ऑफ ट्यूरिंग डिग्रियों में सबसे कम ऊपरी सीमा नहीं हो सकती है, लेकिन इसमें हमेशा एक सटीक जोड़ी 'c', 'd' होती है जैसे कि ∀'e' ('e'<'c'∧'e'<'d' ⇔ ∃i 'ई'≤'ए'_i), और इस प्रकार इसकी (गैर-अद्वितीय) न्यूनतम ऊपरी सीमाएं हैं।
• रचनाशीलता के स्वयंसिद्ध को मानते हुए, यह दिखाया जा सकता है कि ऑर्डर प्रकार की डिग्री की एक अधिकतम श्रृंखला है $\omega _{1}$.

कूद शामिल गुण

• प्रत्येक डिग्री के लिए a और a' के बीच सख्ती से एक डिग्री होती है। वास्तव में, a और a' के बीच जोड़ीदार अतुलनीय डिग्री का एक गणनीय परिवार है।
• जंप इनवर्जन: a डिग्री a, b' अगर और केवल अगर 0' ≤ a के रूप में है।
• किसी भी डिग्री a के लिए एक डिग्री b होती है जैसे a < b और b′ = a′; ऐसी डिग्री b को a के सापेक्ष निम्न कहा जाता है।
• एक अनंत क्रम है a_i डिग्री की ऐसी है कि a′_i+1 ≤ ए_i प्रत्येक मैं के लिए
• पोस्ट की प्रमेय, अंकगणितीय पदानुक्रम और खाली सेट के बारीक पुनरावृत्त ट्यूरिंग जंप के बीच घनिष्ठ पत्राचार स्थापित करना

तार्किक गुण

• सिम्पसन (1977) ने दिखाया कि प्रथम-क्रम सिद्धांत ${\mathcal {D}}$ भाषा में ⟨ ≤, = ⟩ या ⟨ ≤, ′, = ⟩ is अनेक-एक कमी|कई-एक True_arithmetic#True_theory_of_second-order_arithmetic|true द्वितीय-क्रम अंकगणित के सिद्धांत के बराबर है। यह इंगित करता है कि की संरचना ${\mathcal {D}}$ अत्यंत जटिल है।
• शोर और स्लैमन (1999) ने दिखाया कि जंप ऑपरेटर की प्रथम-क्रम संरचना में परिभाषित किया जा सकता है ${\mathcal {D}}$ भाषा के साथ ⟨ ≤, = ⟩.

पुनरावर्ती रूप से गणना करने योग्य ट्यूरिंग डिग्री

एक परिमित जाली जिसे रे में एम्बेड नहीं किया जा सकता है। डिग्री।

एक डिग्री को रिकर्सिवली इन्युमरेबल (आर.ई.) या कंप्यूटेबली इन्युमरेबल (सी.ई.) कहा जाता है, अगर इसमें पुनरावर्ती गणना योग्य सेट होता है। हर आर.ई. डिग्री '0' से नीचे है, लेकिन '0' से नीचे हर डिग्री फिर से नहीं है। हालांकि, एक सेट $A$ अनेक-एक को 0' iff तक घटाया जा सकता है $A$ रे है..

• (गेराल्ड सैक्स | जी। ई। सैक्स, 1964) द रे। डिग्री सघन हैं; किन्हीं दो आर.ई. के बीच डिग्री वहाँ एक तीसरा आर.ई. डिग्री।
• (A. H. Lachlan, 1966a और C. E. M. Yates, 1966) दो रे हैं। डिग्री जिसमें कोई सबसे बड़ी निचली सीमा नहीं है। डिग्री।
• (A. H. Lachlan, 1966a और C. E. M. Yates, 1966) नॉनज़रो री की एक जोड़ी है। डिग्री जिसकी सबसे बड़ी निचली सीमा 0 है।
• (ए. एच. लचलन, 1966बी) रे की कोई जोड़ी नहीं है। डिग्री जिसकी सबसे बड़ी निचली सीमा 0 है और जिसकी सबसे छोटी ऊपरी सीमा 0' है। इस परिणाम को अनौपचारिक रूप से गैर हीरा प्रमेय कहा जाता है।
• (एस. के. थॉमसन, 1971) प्रत्येक परिमित वितरण जाली को री में एम्बेड किया जा सकता है। डिग्री। वास्तव में, गणनीय परमाणु (आदेश सिद्धांत) बूलियन बीजगणित को इस तरीके से एम्बेड किया जा सकता है जो निम्नतम और उच्चतम को संरक्षित करता है।
• (ए. एच. लाचलान और रॉबर्ट आई. सोरे | आर. आई. सोरे, 1980) सभी परिमित जालक (आदेश) को रे में एम्बेड नहीं किया जा सकता है। डिग्री (एक एम्बेडिंग के माध्यम से जो सुप्रीम और इन्फिमा को संरक्षित करता है)। एक विशेष उदाहरण दाईं ओर दिखाया गया है।
• (लियो हैरिंगटन | एल। ए। हैरिंगटन और थियोडोर स्लैमन | टी। ए। स्लैमन, नीस, शोर और स्लैमन देखें (1998)) आरई का पहला क्रम सिद्धांत। भाषा में डिग्रियां 〈 0, ≤, = 〉 कई-एक वास्तविक अंकगणितीय के सिद्धांत के समतुल्य है | वास्तविक प्रथम-क्रम अंकगणित।

इसके अतिरिक्त, शोएनफील्ड की सीमा प्रमेयिका है, एक सेट ए संतुष्ट करता है $[A]\leq _{T}\emptyset '$ iff इसके विशिष्ट कार्य के लिए एक पुनरावर्ती सन्निकटन है: एक फ़ंक्शन g ऐसा है कि पर्याप्त रूप से बड़े s के लिए, $g(s)=\chi _{A}(s)$. एक समुच्चय A को n-r e कहा जाता है। अगर कार्यों का एक परिवार है $(A_{s})_{s\in \mathbb {N} }$ ऐसा है कि:* ए_s A का पुनरावर्ती सन्निकटन है: कुछ t के लिए, किसी भी s≥t के लिए हमारे पास A है_s(एक्स) = ए (एक्स), विशेष रूप से ए को इसके विशिष्ट कार्य के साथ मिलाते हुए. (इस स्थिति को हटाने से A की कमजोर n-r.e होने की परिभाषा मिलती है।)

• ए_s एक एन-ट्रायल विधेय है: सभी एक्स के लिए, ए₀(x)=0 और की कार्डिनैलिटी $\{s\mid A_{s}(x)\neq A_{s+1}(x)\}$ ≤n है।

n-r.e के गुण। डिग्री:* n-r.e के सेट का वर्ग। डिग्री (n+1)-r.e के सेट के वर्ग का एक सख्त उपवर्ग है। डिग्री।

• सभी n>1 के लिए दो (n+1)-r.e हैं। डिग्री 'ए', 'बी' के साथ $\mathbf {a} \leq _{T}\mathbf {b}$, जैसे कि खंड $\{\mathbf {c} \mid \mathbf {a} \leq _{T}\mathbf {c} \leq _{T}\mathbf {b} \}$ इसमें कोई n-r.e नहीं है। डिग्री।
• $A$ और ${\overline {A}}$ हैं (एन+1)-आर.ई. अगर दोनों सेट कमजोर-n-r.e हैं।

पोस्ट की समस्या और प्राथमिकता विधि

"Post's problem" redirects here. For the other "Post's problem", see Post's correspondence problem.

एमिल पोस्ट ने आरई का अध्ययन किया। ट्यूरिंग डिग्री और पूछा कि क्या कोई आरई है। डिग्री सख्ती से 0 और 0 के बीच। ऐसी डिग्री के निर्माण की समस्या (या यह दिखाना कि कोई भी मौजूद नहीं है) को पोस्ट की समस्या के रूप में जाना जाने लगा। इस समस्या को 1950 के दशक में रिचर्ड एम. फ्रीडबर्ग और अल्बर्ट मुचनिक द्वारा स्वतंत्र रूप से हल किया गया था, जिन्होंने दिखाया कि ये मध्यवर्ती आर.ई. डिग्रियां मौजूद हैं (फ्रीडबर्ग-मुचनिक प्रमेय)। उनके प्रमाणों में से प्रत्येक ने आरई के निर्माण के लिए एक ही नई विधि विकसित की। डिग्री, जिसे प्राथमिकता पद्धति के रूप में जाना जाने लगा। प्राथमिकता विधि अब r.e के बारे में परिणाम स्थापित करने की मुख्य तकनीक है। सेट।

एक आरई के निर्माण के लिए प्राथमिकता पद्धति का विचार। सेट X आवश्यकताओं के एक गणनीय अनुक्रम को सूचीबद्ध करना है जिसे X को पूरा करना होगा। उदाहरण के लिए, एक आरई का निर्माण करने के लिए। 'X को 0 और 0' के बीच सेट करें, यह 'A' की आवश्यकताओं को पूरा करने के लिए पर्याप्त है_eऔर बी_eप्रत्येक प्राकृतिक संख्या ई के लिए, जहां ए_eआवश्यकता है कि इंडेक्स ई वाली ओरेकल मशीन एक्स और बी से 0' की गणना नहीं करती है_eआवश्यकता है कि इंडेक्स ई (और कोई ओरेकल) के साथ ट्यूरिंग मशीन एक्स की गणना नहीं करती है। इन आवश्यकताओं को प्राथमिकता क्रम में रखा जाता है, जो आवश्यकताओं और प्राकृतिक संख्याओं का एक स्पष्ट आक्षेप है। उपपत्ति प्रत्येक प्राकृत संख्या के लिए आगमनात्मक रूप से एक चरण के साथ आगे बढ़ती है; इन चरणों को उस समय के चरणों के रूप में माना जा सकता है जिसके दौरान सेट एक्स की गणना की जाती है। प्रत्येक चरण में, संख्याओं को X में डाला जा सकता है या हमेशा के लिए (यदि चोटिल नहीं है) आवश्यकताओं को पूरा करने के प्रयास में X में प्रवेश करने से रोका जा सकता है (अर्थात, सभी X की गणना हो जाने के बाद उन्हें रोकने के लिए बाध्य करें)। कभी-कभी, एक आवश्यकता को पूरा करने के लिए X में एक संख्या की गणना की जा सकती है, लेकिन ऐसा करने से पहले से संतुष्ट आवश्यकता असंतुष्ट हो जाएगी (अर्थात, घायल हो जाना)। आवश्यकताओं पर प्राथमिकता क्रम का उपयोग यह निर्धारित करने के लिए किया जाता है कि इस मामले में किस आवश्यकता को पूरा करना है। अनौपचारिक विचार यह है कि यदि कोई आवश्यकता घायल हो जाती है तो अंततः सभी उच्च प्राथमिकता आवश्यकताओं को घायल होने से रोकने के बाद अंततः घायल होना बंद हो जाएगा, हालांकि प्रत्येक प्राथमिकता तर्क में यह संपत्ति नहीं है। एक तर्क दिया जाना चाहिए कि समग्र सेट X r.e है। और सभी आवश्यकताओं को पूरा करता है। प्राथमिकता वाले तर्कों का इस्तेमाल r.e के बारे में कई तथ्यों को साबित करने के लिए किया जा सकता है। सेट; उपयोग की गई आवश्यकताओं और जिस तरीके से वे संतुष्ट हैं, उन्हें आवश्यक परिणाम उत्पन्न करने के लिए सावधानी से चुना जाना चाहिए।

उदाहरण के लिए, एक साधारण सेट (और इसलिए गैर-कम्प्यूटेबल रे) कम (कम्प्यूटेबिलिटी) एक्स (निम्न का मतलब एक्स' = 0') का निर्माण असीम रूप से कई चरणों में किया जा सकता है। चरण n के प्रारंभ में, मान लीजिए T_n आउटपुट (बाइनरी) टेप हो, जिसे सेल इंडेक्स के सेट से पहचाना जाता है, जहां हमने अभी तक 1 रखा है (इसलिए X=∪_n T_n; टी₀=∅); और पी_n(एम) स्थान एम पर 1 आउटपुट नहीं करने के लिए प्राथमिकता हो; पी₀(एम) = ∞। चरण n पर, यदि संभव हो (अन्यथा चरण में कुछ भी न करें), कम से कम i <n चुनें ताकि ∀m P_n(m)≠i और ट्यूरिंग मशीन i कुछ इनपुट S⊇T पर <n चरणों में रुकती है_n ∀m∈S\T के साथ_n P_n(एम) ≥i। कोई भी ऐसा (परिमित) S चुनें, T सेट करें_n+1= एस, और प्रत्येक सेल एम के लिए एस पर मशीन आई द्वारा दौरा किया गया, पी सेट करें_n+1(एम) = मिनट (मैं, पी_n(एम)), और सभी प्राथमिकताओं को सेट करें> i से ∞, और फिर एक प्राथमिकता ∞ सेल सेट करें (कोई भी करेगा) S में प्राथमिकता i के लिए नहीं। अनिवार्य रूप से, हम मशीन को रुकवाते हैं यदि हम प्राथमिकताओं को परेशान किए बिना ऐसा कर सकते हैं <i, और फिर मशीनों को रोकने के लिए प्राथमिकताएं निर्धारित करते हैं>i पड़ाव को बाधित करने से; सभी प्राथमिकताएं अंततः स्थिर होती हैं।

यह देखने के लिए कि X कम है, मशीन i X पर रुकती है अगर यह कुछ T पर <n चरणों में रुकती है_n ऐसी कि मशीनें <i जो X पर रुकती हैं, ऐसा करती हैं <n-i चरण (रिकर्सन द्वारा, यह 0' से समान रूप से संगणनीय है)। X गैर-कम्प्यूटेबल है क्योंकि अन्यथा एक ट्यूरिंग मशीन Y पर रुक सकती है यदि Y\X गैर-रिक्त है, निर्माण का विरोध करता है क्योंकि X मनमाने ढंग से बड़े i के लिए कुछ प्राथमिकता i कोशिकाओं को बाहर करता है; और X सरल है क्योंकि प्रत्येक i के लिए प्राथमिकता वाले i कक्षों की संख्या परिमित है।

यह भी देखें

• मार्टिन उपाय

संदर्भ

Monographs (undergraduate level)

• Cooper, S.B. Computability theory. Chapman & Hall/CRC, Boca Raton, FL, 2004. ISBN 1-58488-237-9
• Cutland, N. Computability. Cambridge University Press, Cambridge-New York, 1980. ISBN 0-521-22384-9; ISBN 0-521-29465-7

Monographs and survey articles (graduate level)

• Ambos-Spies, K. and Fejer, P. Degrees of Unsolvability. Unpublished. http://www.cs.umb.edu/~fejer/articles/History_of_Degrees.pdf
• Lerman, M. Degrees of unsolvability. Perspectives in Mathematical Logic. Springer-Verlag, Berlin, 1983. ISBN 3-540-12155-2
• Odifreddi, P. G. (1989), Classical Recursion Theory, Studies in Logic and the Foundations of Mathematics, vol. 125, Amsterdam: North-Holland, ISBN 978-0-444-87295-1, MR 0982269
• Odifreddi, P. G. (1999), Classical recursion theory. Vol. II, Studies in Logic and the Foundations of Mathematics, vol. 143, Amsterdam: North-Holland, ISBN 978-0-444-50205-6, MR 1718169
• Rogers, H. The Theory of Recursive Functions and Effective Computability, MIT Press. ISBN 0-262-68052-1, ISBN 0-07-053522-1
• Sacks, Gerald E. Degrees of Unsolvability (Annals of Mathematics Studies), Princeton University Press. ISBN 978-0-6910-7941-7
• Simpson, S. Degrees of unsolvability: a survey of results. Handbook of Mathematical Logic, North-Holland, 1977, pp. 631–652.
• Shoenfield, Joseph R. Degrees of Unsolvability, North-Holland/Elsevier, ISBN 978-0-7204-2061-6.
• Shore, R. (1993). "The theories of the T, tt, and wtt r.e. degrees: undecidability and beyond". In Univ. Nac. del Sur, Bahía Blanca (ed.). Proceedings of the IX Latin American Symposium on Mathematical Logic, Part 1 (Bahía Blanca, 1992). Notas Lógica Mat. Vol. 38. pp. 61–70.
• Soare, R. Recursively enumerable sets and degrees. Perspectives in Mathematical Logic. Springer-Verlag, Berlin, 1987. ISBN 3-540-15299-7
• Soare, Robert I. Recursively enumerable sets and degrees. Bull. Amer. Math. Soc. 84 (1978), no. 6, 1149–1181. MR508451

Research papers

• Kleene, Stephen Cole; Post, Emil L. (1954), "The upper semi-lattice of degrees of recursive unsolvability", Annals of Mathematics, Second Series, 59 (3): 379–407, doi:10.2307/1969708, ISSN 0003-486X, JSTOR 1969708, MR 0061078
• Lachlan, A.H. (1966a), "Lower Bounds for Pairs of Recursively Enumerable Degrees", Proceedings of the London Mathematical Society, 3 (1): 537–569, CiteSeerX 10.1.1.106.7893, doi:10.1112/plms/s3-16.1.537.
• Lachlan, A.H. (1966b), "The impossibility of finding relative complements for recursively enumerable degrees", J. Symb. Log., 31 (3): 434–454, doi:10.2307/2270459, JSTOR 2270459, S2CID 30992462.
• Lachlan, A.H.; Soare, R.I. (1980), "Not every finite lattice is embeddable in the recursively enumerable degrees", Advances in Mathematics, 37: 78–82, doi:10.1016/0001-8708(80)90027-4.
• Nies, André; Shore, Richard A.; Slaman, Theodore A. (1998), "Interpretability and definability in the recursively enumerable degrees", Proceedings of the London Mathematical Society, 77 (2): 241–291, CiteSeerX 10.1.1.29.9588, doi:10.1112/S002461159800046X, ISSN 0024-6115, MR 1635141, S2CID 16488410
• Post, Emil L. (1944), "Recursively enumerable sets of positive integers and their decision problems", Bulletin of the American Mathematical Society, 50 (5): 284–316, doi:10.1090/S0002-9904-1944-08111-1, ISSN 0002-9904, MR 0010514
• Sacks, G.E. (1964), "The recursively enumerable degrees are dense", Annals of Mathematics, Second Series, 80 (2): 300–312, doi:10.2307/1970393, JSTOR 1970393.
• Shore, Richard A.; Slaman, Theodore A. (1999), "Defining the Turing jump", Mathematical Research Letters, 6 (6): 711–722, doi:10.4310/mrl.1999.v6.n6.a10, ISSN 1073-2780, MR 1739227
• Simpson, Stephen G. (1977), "First-order theory of the degrees of recursive unsolvability", Annals of Mathematics, Second Series, 105 (1): 121–139, doi:10.2307/1971028, ISSN 0003-486X, JSTOR 1971028, MR 0432435
• Thomason, S.K. (1971), "Sublattices of the recursively enumerable degrees", Z. Math. Logik Grundlag. Math., 17: 273–280, doi:10.1002/malq.19710170131.
• Yates, C.E.M. (1966), "A minimal pair of recursively enumerable degrees", Journal of Symbolic Logic, 31 (2): 159–168, doi:10.2307/2269807, JSTOR 2269807, S2CID 38778059.

Inline citations