Turing jump
कम्प्यूटेबिलिटी सिद्धांत में, ट्यूरिंग जंप या ट्यूरिंग जंप ऑपरेटर, जिसे एलन ट्यूरिंग के नाम से जाना जाता है, एक ऐसा ऑपरेशन है जो प्रत्येक निर्णय समस्या को उस गुण के साथ एक क्रमिक रूप से कठिन निर्णय समस्या प्रदान करता है जो एक ओरेकल मशीन द्वारा एक ओरेकल के साथ निर्णायक नहीं है। प्रचालक को कूद प्रचालक कहा जाता है क्योंकि यह समस्या के ट्यूरिंग स्तर को बढ़ाता है। यानी, समस्या ट्यूरिंग-कम करने योग्य नहीं है। पोस्ट की प्रमेय ट्यूरिंग जंप प्रचालक और प्राकृतिक संख्याओं के समुच्चयों के अंकगणितीय पदानुक्रम के बीच संबंध स्थापित करती है। अनौपचारिक रूप से, एक समस्या को देखते हुए, ट्यूरिंग जंप ट्यूरिंग मशीनों के सेट को लौटाता है जो उस समस्या को हल करने वाले ओरेकल तक पहुंच दिए जाने पर रुक जाती है। परिभाषा एक्स की ट्यूरिंग कूद को एक्स के लिए एक ओरेकल के साथ ओरेकल मशीनों के लिए रुकने की समस्या के लिए एक ओरेकल के रूप में सोचा जा सकता है। औपचारिक रूप से, एक समूह और-संगणनीय कार्यों की एक गोडेल संख्या को देखते हुए, ट्यूरिंग जंप को इस प्रकार परिभाषित किया गया है कि द थ्यूरिंग जंप को प्रेरक रूप से परिभाषित किया गया है। संकेतन या अक्सर खाली सेट के ट्यूरिंग कूद के लिए उपयोग किया जाता है। इसे शून्य-कूद या कभी-कभी शून्य-प्राइम पढ़ा जाता है। इसी तरह, खाली सेट की वीं छलांग है। परिमित के लिए, ये समुच्चय अंकगणितीय पदानुक्रम से निकटता से संबंधित हैं, और विशेष रूप से पोस्ट के प्रमेय से जुड़े हुए हैं। जंप को ट्रांसफाइनाइट ऑर्डिनल्स में दोहराया जा सकता हैः प्राकृतिक संख्याओं के सेट के लिए जंप ऑपरेटर होते हैं जब एक ऑर्डिनल होता है जिसमें क्लेन में एक कोड होता है (कोड की परवाह किए बिना, परिणामी जंप स्पेक्टर के एक प्रमेय द्वारा समान होते हैं), विशेष रूप से सेट के लिए, जहां चर्च-क्लेन ऑर्डिनल है, हाइपररिथमेटिक पदानुक्रम से निकटता से संबंधित हैं। इसके अलावा, इस प्रक्रिया को निर्माण योग्य ब्रह्मांड के गणना योग्य क्रम के माध्यम से जारी रखा जा सकता है, जिसमें जेन्सेन के गोडेल के एल. के सूक्ष्म संरचना सिद्धांत पर काम का उपयोग किया गया है। उदाहरण खाली सेट का ट्यूरिंग कूदना रुकने की समस्या के समतुल्य है। प्रत्येक के लिए, सेट अंकगणितीय पदानुक्रम (पोस्ट के प्रमेय द्वारा) में स्तर पर एम-पूर्ण है। पीनो अंकगणित की भाषा में सही सूत्रों की गोडेल संख्याओं का सेट एक विधेय के साथ गणना योग्य है। गुण गणना योग्य हैं लेकिन गणना योग्य नहीं हैं। यदि ट्यूरिंग समतुल्य है, तो ट्यूरिंग समतुल्य है। इस निहितार्थ का उल्टा सच नहीं है। (शोर और स्लैमन, 1999) टू के कार्य मानचित्रण को ट्यूरिंग डिग्री के आंशिक क्रम में परिभाषित किया जा सकता है। ट्यूरिंग कूद प्रचालक के कई गुणों पर ट्यूरिंग डिग्री पर लेख में चर्चा की गई है। संदर्भ एंबोस-स्पाइज, के. और फेजर, पी. डिग्री ऑफ अनसोल्वेबिलिटी। अप्रकाशित। http://www.cs.umb.edu ~ फ़ेजर/लेख/हिस्ट्री _ ऑफ _ डिग्रीज़. पी. डी. एफ. परिचय का वर्ष गुम कम्प्यूटेबिलिटी सिद्धांत एलन ट्यूरिंग