ट्यूरिंग पूर्णता

कम्प्यूटिबिलिटी थ्योरी में, डेटा-हेरफेर नियमों की एक प्रणाली (जैसे कि कंप्यूटर का निर्देश सेट, एक प्रोग्रामिंग भाषा, या एक सेलुलर ऑटोमेटन) को ट्यूरिंग-पूर्ण या कम्प्यूटेशनल रूप से सार्वभौमिक कहा जाता है, यदि इसका उपयोग किसी भी ट्यूरिंग मशीन को अनुकरण करने के लिए किया जा सकता है)अंग्रेजी गणितज्ञ और कंप्यूटर वैज्ञानिक एलन ट्यूरिंग द्वारा)।इसका मतलब यह है कि यह प्रणाली अन्य डेटा-हेरफेर नियम सेट को पहचानने या तय करने में सक्षम है।ट्यूरिंग पूर्णता का उपयोग इस तरह के डेटा-हेरफेर नियम सेट की शक्ति को व्यक्त करने के लिए एक तरीके के रूप में किया जाता है।वस्तुतः सभी प्रोग्रामिंग भाषाएं आज-पूर्ण हैं।

एक संबंधित अवधारणा ट्यूरिंग तुल्यता की है – दो कंप्यूटर पी और क्यू को समतुल्य कहा जाता है यदि पी क्यू का अनुकरण कर सकता है और क्यू पी। का अनुकरण कर सकता है। चर्च -ट्यूरिंग थीसिस का अनुमान है कि किसी भी फ़ंक्शन का एक एल्गोरिथ्म द्वारा गणना की जा सकती है, जिसे ट्यूरिंग मशीन द्वारा गणना की जा सकती है, और इसलिए कि यदि कोई वास्तविक-वर्ल्ड कंप्यूटर एक ट्यूरिंग मशीन का अनुकरण कर सकता है, यह एक ट्यूरिंग मशीन के बराबर ट्यूरिंग है।एक सार्वभौमिक ट्यूरिंग मशीन का उपयोग किसी भी ट्यूरिंग मशीन को अनुकरण करने और किसी भी संभावित वास्तविक दुनिया के कंप्यूटर के कम्प्यूटेशनल पहलुओं को विस्तारित करके किया जा सकता है।^{[NB 1]} यह दिखाने के लिए कि कुछ ट्यूरिंग-पूर्ण है, यह दिखाने के लिए पर्याप्त है कि इसका उपयोग कुछ ट्यूरिंग-पूर्ण प्रणाली को अनुकरण करने के लिए किया जा सकता है।किसी भी भौतिक प्रणाली में अनंत स्मृति नहीं हो सकती है, लेकिन अगर परिमित स्मृति की सीमा को नजरअंदाज कर दिया जाता है, तो अधिकांश प्रोग्रामिंग भाषाएं अन्यथा ट्यूरिंग-पूर्ण हैं।

गैर-गणितीय उपयोग

बोलचाल के उपयोग में, ट्यूरिंग-पूर्ण और ट्यूरिंग-समतुल्य शब्द का उपयोग किया जाता है, इसका मतलब यह है कि कोई भी वास्तविक दुनिया के सामान्य-उद्देश्य वाले कंप्यूटर या कंप्यूटर भाषा किसी भी अन्य वास्तविक दुनिया के सामान्य-उद्देश्य वाले कंप्यूटर या कंप्यूटर भाषा के कम्प्यूटेशनल पहलुओं का अनुकरण कर सकती हैं।वास्तविक जीवन में यह कंप्यूटिंग वर्चुअलाइजेशन और एमुलेशन (कम्प्यूटिंग) की व्यावहारिक अवधारणाओं की ओर जाता है।^{[citation needed]} अब तक निर्मित वास्तविक कंप्यूटरों का कार्यात्मक रूप से एक एकल-टेप ट्यूरिंग मशीन (उनकी मेमोरी के अनुरूप टेप) की तरह कार्यात्मक रूप से विश्लेषण किया जा सकता है;इस प्रकार संबद्ध गणित उनके संचालन को काफी दूर तक लागू कर सकता है।हालांकि, वास्तविक कंप्यूटरों में सीमित भौतिक संसाधन हैं, इसलिए वे केवल रैखिक बाउंड ऑटोमेटन पूर्ण हैं।इसके विपरीत, एक सार्वभौमिक कंप्यूटर को एक ट्यूरिंग-पूर्ण निर्देश सेट, अनंत मेमोरी और अनंत उपलब्ध समय के साथ एक उपकरण के रूप में परिभाषित किया गया है।

औपचारिक परिभाषाएँ

कम्प्यूटिबिलिटी थ्योरी (कम्प्यूटेशन) में, कई बारीकी से संबंधित शब्दों का उपयोग एक कम्प्यूटेशनल सिस्टम की कम्प्यूटेशनल शक्ति का वर्णन करने के लिए किया जाता है (जैसे कि एक अमूर्त मशीन या प्रोग्रामिंग भाषा):

ट्यूरिंग पूर्णता: एक कम्प्यूटेशनल सिस्टम जो प्रत्येक ट्यूरिंग-कम्प्यूटेबल फ़ंक्शन की गणना कर सकता है, उसे ट्यूरिंग-पूर्ण (या ट्यूरिंग-पॉवरफुल) कहा जाता है।वैकल्पिक रूप से, इस तरह की प्रणाली वह है जो एक सार्वभौमिक ट्यूरिंग मशीन का अनुकरण कर सकती है।
ट्यूरिंग तुल्यता: एक ट्यूरिंग-पूर्ण प्रणाली को ट्यूरिंग-समतुल्य कहा जाता है यदि प्रत्येक फ़ंक्शन यह गणना कर सकता है तो ट्यूरिंग-कम्प्यूट्यबल भी है;यानी, यह ठीक से कार्यों के एक ही वर्ग की गणना करता है जैसे कि ट्यूरिंग मशीनें करते हैं।वैकल्पिक रूप से, एक ट्यूरिंग-समतुल्य प्रणाली वह है जो एक सार्वभौमिक ट्यूरिंग मशीन द्वारा अनुकरण कर सकती है, और अनुकरण कर सकती है।(सभी ज्ञात शारीरिक रूप से काम करने योग्य ट्यूरिंग-पूर्ण प्रणाली ट्यूरिंग-समतुल्य हैं, जो चर्च-ट्राईिंग थीसिस के लिए समर्थन जोड़ता है।^{[citation needed]})
(कम्प्यूटेशनल) सार्वभौमिकता: एक प्रणाली को सिस्टम के एक वर्ग के संबंध में यूनिवर्सल कहा जाता है यदि वह उस वर्ग में सिस्टम द्वारा कम्प्यूटेशनल प्रत्येक फ़ंक्शन की गणना कर सकता है (या उन सिस्टम में से प्रत्येक को अनुकरण कर सकता है)।आमतौर पर, 'सार्वभौमिकता' शब्द का उपयोग सिस्टम के ट्यूरिंग-पूर्ण वर्ग के संबंध में किया जाता है।कमजोर रूप से सार्वभौमिक शब्द का उपयोग कभी -कभी एक प्रणाली (जैसे एक सेलुलर ऑटोमेटन) को अलग करने के लिए किया जाता है, जिसकी सार्वभौमिकता केवल ट्यूरिंग मशीन की मानक परिभाषा को संशोधित करके प्राप्त की जाती है ताकि इनपुट धाराओं को असीम रूप से कई 1s के साथ शामिल किया जा सके।

इतिहास

ट्यूरिंग पूर्णता महत्वपूर्ण है कि कंप्यूटिंग डिवाइस के लिए प्रत्येक वास्तविक दुनिया के डिजाइन को एक सार्वभौमिक ट्यूरिंग मशीन द्वारा अनुकरण किया जा सकता है।चर्च -ट्र्यूरिंग थीसिस में कहा गया है कि यह गणित का एक कानून है – यह एक सार्वभौमिक ट्यूरिंग मशीन, सिद्धांत रूप में, कोई भी गणना कर सकती है जो किसी भी अन्य प्रोग्राम करने योग्य कंप्यूटर कर सकती है।यह कंप्यूटर प्रोग्राम को लिखने के लिए आवश्यक प्रयास के बारे में कुछ भी नहीं कहता है, या मशीन को गणना करने में लगने वाला समय हो सकता है, या मशीन के पास कोई भी क्षमता हो सकती है जिसका गणना से कोई लेना -देना नहीं है।

चार्ल्स बैबेज का विश्लेषणात्मक इंजन (1830 का दशक) पहली ट्यूरिंग-पूर्ण मशीन होती अगर यह उस समय बनाया गया था जब इसे डिज़ाइन किया गया था।बैबेज ने सराहना की कि मशीन गणना के महान करतबों में सक्षम थी, जिसमें आदिम तार्किक तर्क भी शामिल था, लेकिन उन्होंने सराहना नहीं की कि कोई अन्य मशीन बेहतर नहीं कर सकती है।^{[citation needed]} 1830 के दशक से 1940 के दशक तक, यांत्रिक गणना मशीनों जैसे कि एडर्स और मल्टीप्लायरों को बनाया गया और बेहतर बनाया गया, लेकिन वे एक सशर्त शाखा नहीं कर सके और इसलिए ट्यूरिंग-पूर्ण नहीं थे।

19 वीं शताब्दी के उत्तरार्ध में, लियोपोल्ड क्रोनकर ने आदिम पुनरावर्ती कार्यों को परिभाषित करते हुए, कम्प्यूटिबिलिटी की धारणाओं को तैयार किया। इन कार्यों की गणना ROTE कम्प्यूटेशन द्वारा की जा सकती है, लेकिन वे एक सार्वभौमिक कंप्यूटर बनाने के लिए पर्याप्त नहीं हैं, क्योंकि निर्देश जो उनकी गणना करते हैं, वे अनंत लूप के लिए अनुमति नहीं देते हैं। 20 वीं शताब्दी की शुरुआत में, डेविड हिल्बर्ट ने सटीक स्वयंसिद्धों और कटौती के सटीक तार्किक नियमों के साथ गणित के सभी को स्वयंसिद्ध करने के लिए एक कार्यक्रम का नेतृत्व किया जो एक मशीन द्वारा किया जा सकता है। जल्द ही यह स्पष्ट हो गया कि कटौती के नियमों का एक छोटा सेट स्वयंसिद्धों के किसी भी सेट के परिणामों का उत्पादन करने के लिए पर्याप्त है। ये नियम 1930 में कर्ट गोडेल द्वारा साबित किए गए थे कि वे हर प्रमेय का उत्पादन करने के लिए पर्याप्त हों।

गणना की वास्तविक धारणा को जल्द ही अलग कर दिया गया था, जो गोडेल की अपूर्णता प्रमेय के साथ शुरू हुआ था। इस प्रमेय ने दिखाया कि AXIOM सिस्टम सीमित थे जब गणना के बारे में तर्क करते हैं जो उनके प्रमेयों को कम करता है। चर्च और ट्यूरिंग ने स्वतंत्र रूप से प्रदर्शित किया कि हिल्बर्ट का Entscheidungsproblem (निर्णय की समस्या) अस्वाभाविक था,^[1] इस प्रकार अपूर्णता प्रमेय के कम्प्यूटेशनल कोर की पहचान करना।यह काम, सामान्य पुनरावर्ती कार्यों पर गोडेल के काम के साथ, स्थापित किया गया है कि सरल निर्देशों के सेट हैं, जो एक साथ डालने पर, किसी भी गणना का उत्पादन करने में सक्षम होते हैं।गोडेल के काम से पता चला कि गणना की धारणा अनिवार्य रूप से अद्वितीय है।

1941 में कोनराड Zuse ने Z3 (कंप्यूटर) कंप्यूटर पूरा किया।Zuse उस समय ट्यूरिंग के काम से परिचित नहीं था।विशेष रूप से, Z3 में एक सशर्त कूद के लिए समर्पित सुविधाओं का अभाव था, जिससे इसे पूरा होने से रोक दिया गया।हालांकि, 1998 में, यह Rojas द्वारा दिखाया गया था कि Z3 सशर्त कूद का अनुकरण करने में सक्षम है, और इसलिए सिद्धांत में पूरा हो रहा है।ऐसा करने के लिए, इसका टेप कार्यक्रम हर शाखा के दोनों किनारों के माध्यम से हर संभव पथ को निष्पादित करने के लिए काफी लंबा होगा।^[2] अभ्यास में सशर्त शाखाओं में सक्षम पहला कंप्यूटर, और इसलिए अभ्यास में पूरा होने वाला, 1946 में ENIAC था। Zuse का Z4 (कंप्यूटर) कंप्यूटर 1945 में चालू था, लेकिन यह 1950 तक सशर्त शाखाओं का समर्थन नहीं करता था।^[3]

कम्प्यूटिबिलिटी थ्योरी

कम्प्यूटिबिलिटी सिद्धांत समस्याओं का विश्लेषण करने और यह निर्धारित करने के लिए गणना के मॉडल का उपयोग करता है कि क्या वे कम्प्यूटिबिलिटी और किन परिस्थितियों में हैं। कम्प्यूटिबिलिटी सिद्धांत का पहला परिणाम यह है कि ऐसी समस्याएं मौजूद हैं जिनके लिए यह अनुमान लगाना असंभव है कि एक (ट्यूरिंग-पूर्ण) प्रणाली एक मनमाने ढंग से लंबे समय से क्या करेगी।

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

यह असंभवता वास्तविक दुनिया के कंप्यूटर प्रोग्रामों का विश्लेषण करते समय समस्याएं पैदा करती है। उदाहरण के लिए, कोई भी ऐसा उपकरण नहीं लिख सकता है जो प्रोग्रामर को अनंत छोरों को लिखने से बचाता है या उपयोगकर्ताओं को इनपुट की आपूर्ति से बचाता है जो अनंत छोरों का कारण होगा।

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

turing oracles

डेटा के अनंत टेप तक पहुंच वाला कंप्यूटर एक ट्यूरिंग मशीन की तुलना में अधिक शक्तिशाली हो सकता है: उदाहरण के लिए, टेप में रुकने की समस्या या कुछ अन्य ट्यूरिंग-आउटकम समस्या का समाधान हो सकता है।डेटा के इस तरह के अनंत टेप को ट्यूरिंग ओरेकल कहा जाता है।यहां तक कि यादृच्छिक डेटा के साथ एक ट्यूरिंग ओरेकल कम्प्यूटेशनल (लगभग निश्चित रूप से) नहीं है, क्योंकि केवल कई गणनाएं हैं, लेकिन बेशुमार से कई oracles हैं।तो एक यादृच्छिक ट्यूरिंग ओरेकल के साथ एक कंप्यूटर उन चीजों की गणना कर सकता है जो एक ट्यूरिंग मशीन नहीं कर सकती हैं।

डिजिटल भौतिकी

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

उदाहरण

कम्प्यूटेशनल सिस्टम (बीजगणित, कैलकुली) जिन पर ट्यूरिंग-पूर्ण प्रणालियों के रूप में चर्चा की जाती है, वे सैद्धांतिक कंप्यूटर विज्ञान का अध्ययन करने के लिए अभिप्रेत हैं। वे यथासंभव सरल होने का इरादा रखते हैं, ताकि गणना की सीमाओं को समझना आसान हो। यहाँ कुछ है:

ऑटोमेटा सिद्धांत
औपचारिक व्याकरण (भाषा जनरेटर)
औपचारिक भाषा (भाषा पहचानकर्ता)
लैम्ब्डा कैलकुलस
पोस्ट -ट्र्यूरिंग मशीनें
प्रक्रिया कैलकुलस

अधिकांश प्रोग्रामिंग भाषाएं (उनके अमूर्त मॉडल, शायद कुछ विशेष निर्माणों के साथ जो परिमित स्मृति को छोड़ देते हैं), पारंपरिक और अपरंपरागत, ट्यूरिंग-पूर्ण हैं। यह भी शामिल है:

व्यापक उपयोग में सभी सामान्य-उद्देश्य भाषाएं।
- प्रक्रियात्मक प्रोग्रामिंग भाषाएं जैसे कि C (प्रोग्रामिंग भाषा), पास्कल (प्रोग्रामिंग भाषा)।
- ऑब्जेक्ट-ओरिएंटेड प्रोग्रामिंग लैंग्वेज | ऑब्जेक्ट-ओरिएंटेड लैंग्वेज जैसे जावा (प्रोग्रामिंग लैंग्वेज), स्मॉलटॉक या सी शार्प (प्रोग्रामिंग लैंग्वेज) | C#|
- मल्टी-पैराडिग्म प्रोग्रामिंग लैंग्वेज | मल्टी-पैराडिग्म लैंग्वेज जैसे कि एडीए (प्रोग्रामिंग लैंग्वेज), सी ++, कॉमन लिस्प, फोरट्रान, जावास्क्रिप्ट, ऑब्जेक्ट पास्कल, पर्ल, पायथन (प्रोग्रामिंग लैंग्वेज), आर (प्रोग्रामिंग लैंग्वेज)।
कम सामान्य प्रतिमानों का उपयोग करने वाली अधिकांश भाषाएँ:
- LISP (प्रोग्रामिंग भाषा) और हास्केल (प्रोग्रामिंग भाषा) जैसे कार्यात्मक प्रोग्रामिंग भाषाएं।
- लॉजिक प्रोग्रामिंग भाषाएं जैसे कि प्रोलॉग।
- सामान्य-उद्देश्य मैक्रो प्रोसेसर जैसे कि M4 (कंप्यूटर भाषा)।
- XSLT जैसी घोषणात्मक प्रोग्रामिंग भाषाएं।^[4]
- VHDL और अन्य हार्डवेयर विवरण भाषाएँ।
- टेक्स, एक टाइपसेटिंग सिस्टम।
- गूढ़ प्रोग्रामिंग भाषाएं, गणितीय मनोरंजन का एक रूप जिसमें प्रोग्रामर काम करते हैं कि कैसे एक अत्यंत कठिन लेकिन गणितीय रूप से ट्यूरिंग-समतुल्य भाषा में बुनियादी प्रोग्रामिंग निर्माणों को प्राप्त किया जाए।

कुछ पुनर्लेखन प्रणालियां ट्यूरिंग-पूर्ण हैं।

ट्यूरिंग पूर्णता क्षमता का एक सार बयान है, बजाय उस क्षमता को लागू करने के लिए उपयोग की जाने वाली विशिष्ट भाषा सुविधाओं के पर्चे के।ट्यूरिंग पूर्णता प्राप्त करने के लिए उपयोग की जाने वाली विशेषताएं काफी अलग हो सकती हैं;Fortran सिस्टम लूप निर्माण या संभवतः दोहराव प्राप्त करने के लिए गोटो स्टेटमेंट का उपयोग करेंगे;हास्केल और प्रोलॉग, लगभग पूरी तरह से लूपिंग की कमी, पुनरावर्ती का उपयोग करेंगे।अधिकांश प्रोग्रामिंग भाषाएं वॉन न्यूमैन आर्किटेक्चर पर गणना का वर्णन कर रही हैं, जिनमें मेमोरी (रैम और रजिस्टर) और एक नियंत्रण इकाई है।ये दो तत्व इस वास्तुकला को पूरा करते हैं।यहां तक कि शुद्ध कार्यात्मक भाषाएं भी-पूर्ण हैं।^[5]^{[NB 2]} घोषणात्मक SQL में ट्यूरिंग पूर्णता SQL में पदानुक्रमित और पुनरावर्ती प्रश्नों के माध्यम से लागू की जाती है।^[6] अप्रत्याशित रूप से, SQL (PLSQL, आदि) के लिए प्रक्रियात्मक एक्सटेंशन भी ट्यूरिंग-पूर्ण हैं।यह एक कारण दिखाता है कि अपेक्षाकृत शक्तिशाली गैर-ट्यूरिंग-पूर्ण भाषाएं दुर्लभ क्यों हैं: जितनी अधिक शक्तिशाली भाषा शुरू में होती है, उतने ही जटिल वे कार्य होते हैं जिनके लिए इसे लागू किया जाता है और जितनी जल्दी इसकी पूर्णता की कमी एक दोष के रूप में माना जाता है, इसे प्रोत्साहित करता है।जब तक यह turing- पूर्ण नहीं है।

अनटिप्ड लैम्ब्डा कैलकुलस ट्यूरिंग-पूर्ण है, लेकिन सिस्टम एफ सहित कई टाइप किए गए लैम्ब्डा कैलकुली नहीं हैं।टाइप किए गए सिस्टम का मूल्य अधिक त्रुटियों का पता लगाते हुए अधिकांश विशिष्ट कंप्यूटर प्रोग्रामों का प्रतिनिधित्व करने की उनकी क्षमता पर आधारित है।

नियम 110 और कॉनवे के जीवन का खेल, दोनों सेलुलर ऑटोमेटन, ट्यूरिंग-पूर्ण हैं।

अनजाने में ट्यूरिंग पूर्णता

कुछ गेम और अन्य सॉफ्टवेयर दुर्घटना से पूर्ण हैं, अर्थात् डिजाइन द्वारा नहीं।

सॉफ़्टवेयर:

माइक्रोसॉफ्ट एक्सेल^[7]
माइक्रोसॉफ्ट पावरप्वाइंट^[8]

वीडियो गेम:

बौना किले^[9]
शहर: स्काईलाइन^[10]
ओपस मैग्नम (वीडियो गेम)^[11]
माइनक्राफ्ट^[12]

सामाजिक मीडिया:

हब्बो होटल^[13]

कम्प्यूटेशनल भाषाएँ:

टेम्पलेट (C ++) | C ++ टेम्प्लेट^[14]
प्रिंटफ प्रारूप स्ट्रिंग^[15]

संगणक धातु सामग्री:

x86 MOV निर्देश^[16]

जीव विज्ञान:

रासायनिक कंप्यूटर^[17]^[18]^[19]^[20] और डीएनए कंप्यूटिंग | एंजाइम-आधारित डीएनए कंप्यूटर ref>Shapiro, Ehud (7 December 1999). "A Mechanical Turing Machine: Blueprint for a Biomolecular Computer". Interface Focus. Weizmann Institute of Science. 2 (4): 497–503. doi:10.1098/rsfs.2011.0118. PMC 3363030. PMID 22649583. Archived from the original on 3 January 2009. Retrieved 13 August 2009.</ref> को ट्यूरिंग-समतुल्य दिखाया गया है

गैर-ट्यूरिंग-पूर्ण भाषाएं

कई कम्प्यूटेशनल भाषाएं मौजूद हैं जो ट्यूरिंग-पूर्ण नहीं हैं।ऐसा ही एक उदाहरण नियमित भाषाओं का सेट है, जो नियमित अभिव्यक्तियों द्वारा उत्पन्न होते हैं और जो परिमित-राज्य मशीन द्वारा मान्यता प्राप्त होते हैं।परिमित ऑटोमेटा का एक अधिक शक्तिशाली लेकिन अभी भी ट्यूरिंग-पूर्ण विस्तार नहीं है, जो पुशडाउन ऑटोमेटन और संदर्भ-मुक्त व्याकरण की श्रेणी है, जो आमतौर पर प्रोग्राम कंपाइलर के प्रारंभिक चरण में पार्स पेड़ों को उत्पन्न करने के लिए उपयोग किया जाता है।आगे के उदाहरणों में Direct3D और OpenGL एक्सटेंशन में एम्बेडेड पिक्सेल Shader भाषाओं के कुछ शुरुआती संस्करण शामिल हैं।^{[citation needed]} कुल कार्यात्मक प्रोग्रामिंग भाषाओं में, जैसे कि चैरिटी (प्रोग्रामिंग भाषा) और एपिग्राम (प्रोग्रामिंग भाषा), सभी कार्य कुल हैं और इसे समाप्त करना चाहिए।चैरिटी श्रेणी सिद्धांत के आधार पर एक प्रकार की प्रणाली और नियंत्रण प्रवाह का उपयोग करता है, जबकि एपिग्राम आश्रित प्रकारों का उपयोग करता है।लूप (प्रोग्रामिंग भाषा) भाषा को डिज़ाइन किया गया है ताकि यह केवल उन कार्यों की गणना करे जो आदिम पुनरावर्ती फ़ंक्शन हैं।ये सभी कुल कम्प्यूटेबल फ़ंक्शंस के उचित सबसेट की गणना करते हैं, क्योंकि कुल कम्प्यूटेबल फ़ंक्शंस का पूरा सेट पुनरावर्ती रूप से एन्यूमरेबल सेट नहीं है।इसके अलावा, चूंकि इन भाषाओं में सभी कार्य कुल हैं, इसलिए पुनरावर्ती रूप से enumerable सेट के लिए एल्गोरिदम इन भाषाओं में ट्यूरिंग मशीनों के विपरीत नहीं लिखा जा सकता है।

यद्यपि (अनटिप्ड) लैम्ब्डा कैलकुलस ट्यूरिंग-पूर्ण है, बस टाइप किया गया लैम्ब्डा कैलकुलस नहीं है।

यह भी देखें

एआई-पूर्णता
एल्गोरिथम सूचना सिद्धांत
चॉम्स्की पदानुक्रम
चर्च -ट्र्यूरिंग थीसिस
कम्प्यूटिबिलिटी थ्योरी
आंतरिक फंदे
लूप (कंप्यूटिंग)
मशीन जो हमेशा रोकती है
चावल का प्रमेय
एसएमएन प्रमेय | एस_mnप्रमेय
संरचित कार्यक्रम प्रमेय
Turing tarpit
वर्चुअलाइजेशन
अनुकरण (कंप्यूटिंग)

संदर्भ

↑ Hodges, Andrew (1992) [1983], Alan Turing: The Enigma, London: Burnett Books, p. 111, ISBN 0-04-510060-8
↑ Rojas, Raul (1998). "How to make Zuse's Z3 a universal computer". Annals of the History of Computing. 20 (3): 51–54. doi:10.1109/85.707574.
↑ Rojas, Raúl (1 February 2014). Google translation, pdf is also translatable. "Konrad Zuse und der bedingte Sprung" [Konrad Zuse and the conditional jump]. Informatik-Spektrum (in Deutsch). 37 (1): 50–53. doi:10.1007/s00287-013-0717-9. ISSN 0170-6012. S2CID 1086397. {{cite journal}}: External link in |others= (help)
↑ Lyons, Bob (30 March 2001). "Universal Turing Machine in XSLT". B2B Integration Solutions from Unidex. Archived from the original on 17 July 2011. Retrieved 5 July 2010.
↑ Boyer, Robert S.; Moore, J. Strother (May 1983). A Mechanical Proof of the Turing Completeness of Pure Lisp (PDF) (Technical report). Institute for Computing Science, University of Texas at Austin. 37. Archived (PDF) from the original on 22 September 2017.
↑ Dfetter; Breinbaas (8 August 2011). "Cyclic Tag System". PostgreSQL wiki. Retrieved 10 September 2014.
↑ "Announcing LAMBDA: Turn Excel formulas into custom functions". TECHCOMMUNITY.MICROSOFT.COM. 3 December 2020. Retrieved 8 December 2020.
↑ Wildenhain, Tom (9 April 2020). "On Turing Completeness of MS PowerPoint" (PDF).^{[self-published source]}
↑ Cedotal, Andrew (16 April 2010). "Man Uses World's Most Difficult Computer Game to Create … A Working Turing Machine". The Mary Sue. Archived from the original on 27 June 2015. Retrieved 2 June 2015.
↑ Plunkett, Luke (16 July 2019). "Cities: Skylines Map Becomes A Poop-Powered Computer". Kotaku. Retrieved 16 July 2019.
↑ Caldwell, Brendan (20 November 2017). "Opus Magnum player makes an alchemical computer". Rock Paper Shotgun. Retrieved 23 September 2019.
↑ Writer, Staff. "This 8-bit processor built in Minecraft can run its own games". PCWorld. Retrieved 21 July 2022.
↑ "Habbo's Twitter thread on the implementation of a Turing machine inside the game". 9 November 2020. Retrieved 11 November 2020.
↑ Meyers, Scott (Scott Douglas) (2005). Effective C++ : 55 specific ways to improve your programs and designs (3rd ed.). Upper Saddle River, NJ: Addison-Wesley. ISBN 0321334876. OCLC 60425273.
↑ A 27th IOCCC Winner
Carlini, Nicolas; Barresi, Antonio; Payer, Mathias; Wagner, David; Gross, Thomas R. (August 2015). "Control-flow bending: on the effectiveness of control-flow integrity". Proceedings of the 24th USENIX Conference on Security Symposium. pp. 161–176. ISBN 9781931971232.
↑ Dolan, Stephen. "mov is Turing-complete" (PDF). stedolan.net. Archived from the original (PDF) on 14 February 2021. Retrieved 9 May 2019.
↑ Shah, Shalin; Wee, Jasmine; Song, Tianqi; Ceze, Luis; Strauss, Karin; Chen, Yuan-Jyue; Reif, John (4 May 2020). "Using Strand Displacing Polymerase To Program Chemical Reaction Networks". Journal of the American Chemical Society. 142 (21): 9587–9593. doi:10.1021/jacs.0c02240. ISSN 0002-7863. PMID 32364723. S2CID 218504535.
↑ Chen, Yuan-Jyue; Dalchau, Neil; Srinivas, Niranjan; Phillips, Andrew; Cardelli, Luca; Soloveichik, David; Seelig, Georg (October 2013). "Programmable chemical controllers made from DNA". Nature Nanotechnology. 8 (10): 755–762. Bibcode:2013NatNa...8..755C. doi:10.1038/nnano.2013.189. ISSN 1748-3395. PMC 4150546. PMID 24077029.
↑ Srinivas, Niranjan; Parkin, James; Seelig, Georg; Winfree, Erik; Soloveichik, David (15 December 2017). "Enzyme-free nucleic acid dynamical systems". Science. 358 (6369): eaal2052. doi:10.1126/science.aal2052. ISSN 0036-8075. PMID 29242317.
↑ Soloveichik, David; Seelig, Georg; Winfree, Erik (23 March 2010). "DNA as a universal substrate for chemical kinetics". Proceedings of the National Academy of Sciences. 107 (12): 5393–5398. Bibcode:2010PNAS..107.5393S. doi:10.1073/pnas.0909380107. ISSN 0027-8424. PMC 2851759. PMID 20203007.

इस पृष्ठ में गुम आंतरिक लिंक की सूची

अंकगणितीय तर्क इकाई
कोनराड ज़ूस
रेखीय समीकरण
द्विआधारी अंकगणित
IEEE मील के पत्थर की सूची
जॉन माउचली
पुनर्योजी संधारित्र स्मृति
अवधारणा का सबूत
संग्रहीत प्रोग्राम वास्तुकला
नियत बिंदु अंकगणित
प्रत्यावर्ती धारा
युगपत समीकरण
एकक अभिलेख उपस्कर
पूर्वानुमान (कम्प्यूटिंग)
धागा (कम्प्यूटिंग)
सॉफ़्टवेयर प्रलेखन
दुभाषिया (कम्प्यूटिंग)
सोर्स कोड
यादृच्छिक अभिगम स्मृति
सेंट्रल प्रोसेसिंग यूनिट
परिवर्तनीय विज्ञान (कंप्यूटर विज्ञान)
सॉफ्टवेयर डेवलपमेंट
बर्नौली नंबर
परिमित अवस्था मशीन
ट्यूरिंग पूर्णता
ट्यूरिंग पूरा
मुद्रा स्फ़ीति
आधार -10
एबरडीन प्रोविंग ग्राउंड
निर्देश समुच्चय
मरना (एकीकृत परिपथ)
एकीकृत परिपथ
एकीकृत परिपथ का आविष्कार
अर्धचालक उपकरण निर्माण
Czochralski विधि
एक बस से
अनुदेश सेट वास्तुकला
मशीन अनुदेश
पिछड़ा संगत
x86 विधानसभा भाषा
शब्द (कंप्यूटर आर्किटेक्चर)
पूर्णांकों
सरणी आंकड़ा संरचना
अंकीय उपकरण निगम
समन्वित विकास पर्यावरण
प्रक्रियात्मक क्रमादेश
अभिप्राय विज्ञान
संप्रदाय (कम्प्यूटिंग)
बहाव को काबू करें
अभिलेख (कंप्यूटर विज्ञान)
पहली पीढ़ी प्रोग्रामिंग भाषा
प्रोग्रामिंग भाषा पीढ़ी
दूसरी पीढ़ी प्रोग्रामिंग भाषा
स्मृति पता
तीसरी पीढ़ी प्रोग्रामिंग भाषा
चौथी पीढ़ी प्रोग्रामिंग भाषा
अनिवार्य क्रमादेशन
घोषणाशील क्रमादेशन
परिवर्तनीय (प्रोग्रामिंग)
संकेतक
वाक्यविन्यास द्वारा निर्देशित अनुवाद
मॉड्यूल-2
एडीए (प्रोग्रामिंग भाषा)
जावा (प्रोग्रामिंग भाषा)
सी ++
माइक्रो-कंप्यूटरों
बी (प्रोग्रामिंग भाषा)
C और C ++ में ऑपरेटर
आंकड़ा खंड
इंटरफ़ेस (कम्प्यूटिंग)
रनटाइम (कार्यक्रम जीवनचक्र चरण)
दायरा विज्ञान
स्मृति से बाहर
सार और ठोस
अस्थायी बिंदु अंकगणित
पद्धति (कंप्यूटर प्रोग्रामिंग)
समुच्चय सिद्धान्त
निर्माणकर्ता
शब्दार्थ विज्ञान
समवर्ती अभिकलन
समानांतर अभिकलन
लिस्प (प्रोग्रामिंग भाषा)
वृक्ष संरचना)
सॉफ़्टवेयर विकास प्रक्रिया
कृत्रिम होशियारी
वस्तु (दर्शन)
बैक ट्रैकिंग
सबसे छोटा पथ समस्या
वंश - वृक्ष
तथ्य
अमूर्त आंकड़ा प्रकार
निंदा संबंधी शब्दार्थ
प्रणाली विश्लेषक
सॉफ़्टवेयर एजिंग
सामयिक विज्ञान
डेज़ी श्रृंखला (विद्युत इंजीनियरिंग)
आंकड़ा प्रवाह आरेख
उपयोगिता सॉफ़्टवेयर
व्यावसायिक बिकने वाला
आवेदन सेवा प्रदाता
परिधीय
समय बताना
प्रक्रिया नियंत्रण खंड
क्षेत्र-आधारित स्मृति प्रबंधन
भौतिक पता
मर्गदर्शक सारणी
अंतःप्रक्रम संचार
सिग्नल (आईपीसी)
डेटा पथ
तर्क -स्तरीय स्तर
नियंत्रण भंडार

अग्रिम पठन

Brainerd, W. S.; Landweber, L. H. (1974). Theory of Computation. Wiley. ISBN 0-471-09585-0.
Giles, Jim (24 October 2007). "Simplest 'universal computer' wins student $25,000". New Scientist.
Herken, Rolf, ed. (1995). The Universal Turing Machine: A Half-Century Survey. Springer Verlag. ISBN 3-211-82637-8.
Turing, A. M. (1936). "On Computable Numbers, with an Application to the Entscheidungsproblem" (PDF). Proceedings of the London Mathematical Society. 2. 42: 230–265. doi:10.1112/plms/s2-42.1.230. S2CID 73712.
Turing, A. M. (1938). "On Computable Numbers, with an Application to the Entscheidungsproblem: A correction". Proceedings of the London Mathematical Society. 2. 43: 544–546. doi:10.1112/plms/s2-43.6.544.

बाहरी संबंध

"Turing Complete". wiki.c2.com.

[1] A UTM cannot simulate non-computational aspects such as I/O.

[7] The following book provides an introduction for computation models: Rauber, Thomas; Rünger, Gudula (2013). Parallel programming: for multicore and cluster systems (2nd ed.). Springer. ISBN 9783642378010.

[2] Hodges, Andrew (1992) [1983], Alan Turing: The Enigma, London: Burnett Books, p. 111, ISBN 0-04-510060-8

[3] Rojas, Raul (1998). "How to make Zuse's Z3 a universal computer". Annals of the History of Computing. 20 (3): 51–54. doi:10.1109/85.707574.

[4] Rojas, Raúl (1 February 2014). Google translation, pdf is also translatable. "Konrad Zuse und der bedingte Sprung" [Konrad Zuse and the conditional jump]. Informatik-Spektrum (in Deutsch). 37 (1): 50–53. doi:10.1007/s00287-013-0717-9. ISSN 0170-6012. S2CID 1086397. {{cite journal}}: External link in |others= (help)

[5] Lyons, Bob (30 March 2001). "Universal Turing Machine in XSLT". B2B Integration Solutions from Unidex. Archived from the original on 17 July 2011. Retrieved 5 July 2010.

[6] Boyer, Robert S.; Moore, J. Strother (May 1983). A Mechanical Proof of the Turing Completeness of Pure Lisp (PDF) (Technical report). Institute for Computing Science, University of Texas at Austin. 37. Archived (PDF) from the original on 22 September 2017.

[8] Dfetter; Breinbaas (8 August 2011). "Cyclic Tag System". PostgreSQL wiki. Retrieved 10 September 2014.

[9] "Announcing LAMBDA: Turn Excel formulas into custom functions". TECHCOMMUNITY.MICROSOFT.COM. 3 December 2020. Retrieved 8 December 2020.

[10] Wildenhain, Tom (9 April 2020). "On Turing Completeness of MS PowerPoint" (PDF).^{[self-published source]}

[11] Cedotal, Andrew (16 April 2010). "Man Uses World's Most Difficult Computer Game to Create … A Working Turing Machine". The Mary Sue. Archived from the original on 27 June 2015. Retrieved 2 June 2015.

[12] Plunkett, Luke (16 July 2019). "Cities: Skylines Map Becomes A Poop-Powered Computer". Kotaku. Retrieved 16 July 2019.

[13] Caldwell, Brendan (20 November 2017). "Opus Magnum player makes an alchemical computer". Rock Paper Shotgun. Retrieved 23 September 2019.

[14] Writer, Staff. "This 8-bit processor built in Minecraft can run its own games". PCWorld. Retrieved 21 July 2022.

[15] "Habbo's Twitter thread on the implementation of a Turing machine inside the game". 9 November 2020. Retrieved 11 November 2020.

[16] Meyers, Scott (Scott Douglas) (2005). Effective C++ : 55 specific ways to improve your programs and designs (3rd ed.). Upper Saddle River, NJ: Addison-Wesley. ISBN 0321334876. OCLC 60425273.

[17] A 27th IOCCC Winner
Carlini, Nicolas; Barresi, Antonio; Payer, Mathias; Wagner, David; Gross, Thomas R. (August 2015). "Control-flow bending: on the effectiveness of control-flow integrity". Proceedings of the 24th USENIX Conference on Security Symposium. pp. 161–176. ISBN 9781931971232.

[18] Dolan, Stephen. "mov is Turing-complete" (PDF). stedolan.net. Archived from the original (PDF) on 14 February 2021. Retrieved 9 May 2019.

[:0-19] Shah, Shalin; Wee, Jasmine; Song, Tianqi; Ceze, Luis; Strauss, Karin; Chen, Yuan-Jyue; Reif, John (4 May 2020). "Using Strand Displacing Polymerase To Program Chemical Reaction Networks". Journal of the American Chemical Society. 142 (21): 9587–9593. doi:10.1021/jacs.0c02240. ISSN 0002-7863. PMID 32364723. S2CID 218504535.

[:1-20] Chen, Yuan-Jyue; Dalchau, Neil; Srinivas, Niranjan; Phillips, Andrew; Cardelli, Luca; Soloveichik, David; Seelig, Georg (October 2013). "Programmable chemical controllers made from DNA". Nature Nanotechnology. 8 (10): 755–762. Bibcode:2013NatNa...8..755C. doi:10.1038/nnano.2013.189. ISSN 1748-3395. PMC 4150546. PMID 24077029.

[:2-21] Srinivas, Niranjan; Parkin, James; Seelig, Georg; Winfree, Erik; Soloveichik, David (15 December 2017). "Enzyme-free nucleic acid dynamical systems". Science. 358 (6369): eaal2052. doi:10.1126/science.aal2052. ISSN 0036-8075. PMID 29242317.

[:3-22] Soloveichik, David; Seelig, Georg; Winfree, Erik (23 March 2010). "DNA as a universal substrate for chemical kinetics". Proceedings of the National Academy of Sciences. 107 (12): 5393–5398. Bibcode:2010PNAS..107.5393S. doi:10.1073/pnas.0909380107. ISSN 0027-8424. PMC 2851759. PMID 20203007.

[NB 1]

[1]

[2]

[3]

[4]

[5]

[NB 2]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]