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

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

अवलोकन

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

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

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

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

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

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

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

• X ≡_T X
• X ≡_T Y का तात्पर्य Y ≡_T X से है
• यदि X ≡_T Y और Y ≡_T Z तो X ≡_T Z होगा।

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

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

किसी भी समुच्चय X और Y के लिए, 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 का 'ट्यूरिंग जंप' कहा जाता है। डिग्री X के ट्यूरिंग जंप को डिग्री X' के रूप में परिभाषित किया जाता है; यह मान्य परिभाषा है क्योंकि X ' ≡_T Y' जब भी X ≡_T Y होता है। प्रमुख उदाहरण '0 , हॉल्टिंग समस्या की डिग्री है।

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

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

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

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

आदेश गुण

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

तार्किक गुण

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

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

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

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

• (गेराल्ड ई. सैक्स अथवा जी.ई. सैक्स, 1964) r.e डिग्री सघन हैं; किन्हीं दो r.e. के बीच तीसरा r.e. डिग्री है।
• (ए.एच. लचलन, 1966ए और सी.ई.एम. येट्स , 1966) r.e. डिग्री में कोई सबसे बड़ी निचली सीमा के साथ दो r.e. डिग्री हैं।
• (ए.एच. लचलन, 1966ए और सी.ई.एम. येट्स , 1966) नॉनज़रो अथवा गैर-शून्य r.e. डिग्री की एक जोड़ी है जिसकी सबसे बड़ी निचली सीमा 0 है।
• (ए. एच. लचलन, 1966बी) r.e. डिग्री का कोई ऐसा युग्म नहीं है जिसकी सबसे बड़ी निचली सीमा 0 है और जिसकी सबसे छोटी ऊपरी सीमा 0' है। इस परिणाम को अनौपचारिक रूप से नॉनडायमंड प्रमेय अथवा गैर हीरा प्रमेय कहा जाता है।
• (एस. के. थॉमसन, 1971) प्रत्येक परिमित वितरण जाली को r.e. डिग्री में एम्बेड किया जा सकता है। वास्तव में, गणनीय परमाणु(आदेश सिद्धांत) रहित बूलियन बीजगणित को इस प्रणालियों से एम्बेड किया जा सकता है जो निम्नतम और उच्चतम(सुप्रीमा और इन्फिमा) को संरक्षित करता है।
• (ए. एच. लाचलान और रॉबर्ट आई. सोरे अथवा आर. आई. सोरे, 1980) सभी परिमित जालक (आदेश) को r.e. डिग्री में एम्बेड नहीं किया जा सकता है। डिग्री ( एम्बेडिंग के माध्यम से जो सुप्रीम और इन्फिमा को संरक्षित करता है)। विशेष उदाहरण दाईं ओर दिखाया गया है।
• (लियो ए. हैरिंगटन अथवा एल.ए. हैरिंगटन और थियोडोर ए. स्लैमनबी अथवा टी.ए. स्लैमन, नीस, ध्वनि और स्लैमन(1998) देखें) भाषा में r.e. डिग्री का प्रथम-क्रम सिद्धांत ⟨ 0, ≤, = ⟩ सत्य प्रथम-क्रम अंकगणित के सिद्धांत के समतुल्य बहु-एक है।

इसके अतिरिक्त, शोएनफील्ड की सीमा प्रमेयिका(लिमिट लेम्मा) है, समुच्चय A के लिए $[A]\leq _{T}\emptyset '$ को संतुष्ट करता है यदि इसके विशिष्ट कार्य के लिए पुनरावर्ती सन्निकटन है: तथा फ़ंक्शन g ऐसा है कि पर्याप्त रूप से बड़े s के लिए $g(s)=\chi _{A}(s)$है।

समुच्चय A को n-r.e. कहा जाता है। यदि कार्यों का समूह $(A_{s})_{s\in \mathbb {N} }$ ऐसा है कि:

• A_s A का पुनरावर्ती सन्निकटन है: कुछ t के लिए, किसी भी s≥t के लिए हमारे पास A_s(X) = A(X) है, विशेष रूप से A को इसके विशिष्ट कार्य के साथ मिलाते है (इस स्थिति को हटाने से A की कमजोर n-r.e. होने की परिभाषा मिलती है)।

• A_s एन-ट्रायल विधेय है: सभी X के लिए, A₀(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. डिग्री 'a', 'b' के साथ $\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}}$(n+1)-r.e. हैं , यदि दोनों समुच्चय कमजोर-n-r.e. हैं।

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

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

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

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

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

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

यह देखने के लिए कि X कम है, यंत्र i X पर रुकती है यदि यह कुछ Tn पर <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