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

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

सिंहावलोकन

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

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

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

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

Main article: ट्यूरिंग कमी

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

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

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

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

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

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

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

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

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

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

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

आदेश गुण

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

कूद सम्मिलित गुण

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

तार्किक गुण

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

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

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

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

• (गेराल्ड ई. सैक्स अथवा जी.ई. सैक्स, 1964) आर.ई डिग्री सघन हैं; किन्हीं दो आर.ई. के बीच तीसरा आर.ई. डिग्री है।
• (ए.एच. लचलन, 1966ए और सी.ई.एम. येट्स , 1966) आर.ई. डिग्री में कोई सबसे बड़ी निचली सीमा के साथ दो आर.ई. डिग्री हैं।
• (ए.एच. लचलन, 1966ए और सी.ई.एम. येट्स , 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 एन-ट्रायल विधेय है: सभी एक्स के लिए, ए₀(एक्स )=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 हैं।

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

"पोस्ट की समस्या" redirects here. For अन्य "पोस्ट की समस्या", see पोस्ट की पत्राचार समस्या.

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

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

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

sdsउदाहरण के लिए, साधारण सेट (और इसलिए गैर-कम्प्यूटेबल रे) कम (कम्प्यूटेबिलिटी) एक्स (निम्न का कारण एक्स' = 0') का निर्माण असीम रूप से कई चरणों में किया जा सकता है। चरण n के प्रारंभ में, मान लीजिए T_n आउटपुट (बाइनरी) टेप हो, जिसे सेल इंडेक्स के सेट से पहचाना जाता है, जहां हमने अभी तक 1 रखा है (इसलिए एक्स =∪_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 पड़ाव को बाधित करने से; सभी प्राथमिकताएं अंततः स्थिर होती हैं।sds

यह देखने के लिए कि एक्स कम है, मशीन i एक्स पर रुकती है यदि यह कुछ T_n पर <n चरणों में रुकती है जैसे कि मशीनें <i जो एक्स पर रुकती हैं, ऐसा <n-i चरण (रिकर्सन द्वारा, यह 0' से समान रूप से संगणनीय है)करती हैं <n-i चरण (रिकर्सन द्वारा, यह 0' से समान रूप से संगणनीय है)। एक्स गैर-कम्प्यूटेबल है क्योंकि अन्यथा ट्यूरिंग मशीन वाई पर रुक सकती है यदि वाई\एक्स गैर-रिक्त है, इसके निर्माण का विरोध करता है क्योंकि एक्स इच्छानुसार से बड़े i के लिए कुछ प्राथमिकता i सेल को बाहर करता है; और एक्स सरल है क्योंकि प्रत्येक 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