ट्यूरिंग मशीन

एक भौतिक ट्यूरिंग मशीन मॉडल। सच्चे ट्यूरिंग मशीन में दोनों तरफ असीमित टेप होगा, चूंकि, भौतिक मॉडल में केवल सीमित मात्रा में टेप हो सकता है।

Classes of automata

(Clicking on each layer gets an article on that subject)

एक ट्यूरिंग मशीन एबसट्रक्ट मशीन का वर्णन करने वाली मैथमेटिकल मॉडल कंप्यूटर है^[1] जो की नियमों की टेबल के अनुसार टेप की मेनीपुलेट्स सिम्बल्स में परिवर्तन करता है।^[2] और मॉडल की सिम्प्लिसिटी के अतिरिक्त यह किसी भी कंप्यूटर एल्गोरिथ्म को प्रयुक्त करने में सक्षम होता है।^[3]

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

ट्यूरिंग मशीन का आविष्कार 1936 में एलन ट्यूरिंग ने किया था।^[7]^[8] जिन्होंने इसे ए-मशीन (स्वचालित मशीन) कहा।^[9] यह ट्यूरिंग के डॉक्टरेट सलाहकार अलोंजो चर्च थे, जिन्होंने बाद में समीक्षा में ट्यूरिंग मशीन शब्द गढ़ा है।^[10] इस मॉडल के साथ, ट्यूरिंग नकारात्मक में दो प्रश्नों का उत्तर देने में सक्षम था:

क्या कोई मशीन उपस्तिथ है जो यह निर्धारित कर सकती है कि उसके टेप पर कोई अर्बिटरी मशीन वृत्ताकार है (उदाहरण के लिए, फ्रीज, या उसके कम्प्यूटेशनल कार्य को प्रवाहित रखने में विफल)?
क्या कोई मशीन उपस्तिथ है जो यह निर्धारित कर सकती है कि उसके टेप पर कोई अर्बिटरी मशीन कभी किसी दिए गए सिम्बल्स को प्रिंट करती है या नहीं?^[11]^[12]

इस प्रकार इच्छानुसार कंप्यूटर करने में सक्षम अधिक ही सिंपल उपकरण का गणितीय विवरण प्रदान करके, वह सामान्य रूप से कंप्यूटर के गुणों को प्रमाणित करने में सक्षम था - और विशेष रूप से, एन्ट्सचीडुंग्सप्रोब्लेम ('निर्णय समस्या') की अकंप्यूटेबिलिटी सक्षम था।^[13]

ट्यूरिंग मशीनों ने यांत्रिक कंप्यूटर की शक्ति पर मौलिक सीमाओं के अस्तित्व को सिद्ध किया।^[14] जबकि वे इच्छानुसार कंप्यूटर व्यक्त कर सकते हैं, उनका न्यूनतम डिजाइन उन्हें व्यवहार में गणना के लिए अनुपयुक्त बनाता है: रियल संसार के कंप्यूटर विभिन्न डिजाइनों पर आधारित होते हैं, जो ट्यूरिंग मशीनों के विपरीत, रैंडम एक्सेस मेमोरी का उपयोग करते हैं।

ट्यूरिंग पूर्णता ट्यूरिंग मशीन का अनुकरण करने के लिए निर्देशों की प्रणाली की क्षमता है। प्रोग्रामिंग लैंग्वेज जो ट्यूरिंग पूर्ण है, सैद्धांतिक रूप से कंप्यूटर द्वारा पूर्ण किए जाने वाले सभी कार्यों को व्यक्त करने में सक्षम है; यदि परिमित मेमोरी की सीमाओं को अनदेखा कर दिया जाए तो लगभग सभी प्रोग्रामिंग लैंग्वेज ट्यूरिंग पूर्ण हैं।

अवलोकन

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

एक ब्लैक बॉक्स मानकर, ट्यूरिंग मशीन यह नहीं समझ सकती है कि क्या यह अंततः किसी दिए गए प्रोग्राम के साथ सबसेट के किसी विशिष्ट स्ट्रिंग की गणना करती है। यह इस तथ्य के कारण है कि हॉल्टिंग समस्या हल नहीं हो सकती है, जिसका कंप्यूटिंग की सैद्धांतिक सीमाओं के लिए प्रमुख निहितार्थ है।

इस प्रकार से ट्यूरिंग मशीन अनरेसट्रीक्टेड ग्रामर को संसाधित करने में सक्षम है, जिसका अर्थ है कि यह अनंत विधियों से पूर्व क्रम के लॉजिक का सशक्त से मूल्यांकन करने में सक्षम है। यह लैम्ब्डा कैलकुस के माध्यम से प्रसिद्ध रूप से प्रदर्शित होता है।

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

भौतिक विवरण

अपने 1948 के निबंध, इंटेलिजेंट मशीनरी में, ट्यूरिंग ने लिखा है कि उनकी मशीन में सम्मिलित हैं:

...वर्गों में चिह्नित एक अनंत टेप के रूप में प्राप्त असीमित मेमोरी क्षमता, जिनमें से प्रत्येक पर एक प्रतीक मुद्रित किया जा सकता है। किसी भी क्षण मशीन में एक प्रतीक होता है; इसे स्कैन किया गया प्रतीक कहा जाता है। मशीन स्कैन किए गए प्रतीक को परिवर्तन कर सकती है, और उसका व्यवहार आंशिक रूप से उस प्रतीक द्वारा निर्धारित होता है, किन्तु टेप पर अन्यत्र उपस्तिथ प्रतीक मशीन के व्यवहार को प्रभावित नहीं करते हैं। चूंकि, टेप को मशीन के माध्यम से आगे और पीछे ले जाया जा सकता है, यह मशीन के प्राथमिक कार्यों में से एक है। इसलिए टेप पर कोई भी प्रतीक अंततः एक पारी हो सकता है।.^[15]
— — ट्यूरिंग 1948, पृ. 3. 3^[16]

विवरण

ट्यूरिंग मशीन गणितीय रूप से मशीन का मॉडल बनाती है जो यांत्रिक रूप से टेप पर चलती है। इस टेप पर सिम्बल्स होते हैं, जिन्हें मशीन बार में टेप हेड का उपयोग करके पढ़ और लिख सकती है। ऑपरेशन पूर्ण रूप से प्राथमिक निर्देशों के परिमित सेट द्वारा निर्धारित किया जाता है जैसे कि स्टेट 42 में, यदि देखा गया सिम्बल्स 0 है, तो 1 लिखें; यदि देखा गया सिम्बल्स 1 है, तो स्थिति 17 में बदलें; स्थिति 17 में, यदि देखा गया सिम्बल्स 0 है, तो 1 लिखें और स्थिति 6 में बदलें; आदि मूल लेख में (संगणनीय संख्याओं पर, एन्ट्सचीडुंग्सप्रोब्लेम के लिए आवेदन के साथ, #The एन्ट्सचीडुंग्सप्रोब्लेम (निर्णय समस्या) भी देखें): हिल्बर्ट का 1900 का दसवां प्रश्न), ट्यूरिंग तंत्र की कल्पना नहीं करता है, किन्तु व्यक्ति जिसे वह कंप्यूटर कहता है , जो इन नियतात्मक यांत्रिक नियमों से निष्पादित (या जैसा कि ट्यूरिंग इसे कहते हैं, अपमानजनक विधि से) करता है।

हेड सदैव टेप के विशेष वर्ग के ऊपर होता है; वर्गों का केवल परिमित विस्तार दिखाया गया है। प्रदर्शन करने का निर्देश (q₄) स्कैन किए गए वर्ग पर दिखाया गया है। (ड्राइंग आफ्टर क्लेन (1952) पृष्ठ 375।)

यहाँ, आंतरिक स्थिति (q₁) हेड के अंदर दिखाया गया है, और चित्रण टेप को अनंत और 0 से पहले से भरे हुए के रूप में वर्णित करता है, सिम्बल्स रिक्त के रूप में कार्य करता है। सिस्टम की पूर्ण स्थिति (इसकी पूर्ण कॉन्फ़िगरेशन) में आंतरिक स्थिति, टेप पर कोई भी गैर-रिक्त सिम्बल्स (इस चित्रण 11B में), और रिक्त स्थान सहित उन सिम्बल्सों के सापेक्ष हेड की स्थिति, अर्थात 011B सम्मिलित हैं। (मिंस्की के बाद का चित्र (1967) पृष्ठ 121।)

अधिक स्पष्ट रूप से, ट्यूरिंग मशीन में निम्न सम्मिलित हैं:

एक टेप दूसरे के बगल में सेल्स में विभाजित है। प्रत्येक सेल्स में कुछ परिमित वर्णमाला से सिम्बल्स होता है। वर्णमाला में विशेष रिक्त सिम्बल्स (यहाँ '0' के रूप में लिखा गया है) और या अधिक अन्य सिम्बल्स हैं। यह माना जाता है कि टेप इच्छानुसार से बायीं ओर और दायीं ओर बढ़ाया जा सकता है, जिससे ट्यूरिंग मशीन को सदैव उतनी ही टेप की आपूर्ति की जा सके जितनी इसकी गणना के लिए आवश्यक है। जिन सेल्स को पहले नहीं लिखा गया है उन्हें रिक्त सिम्बल्स से भरा माना जाता है। कुछ मॉडलों में टेप का बायां हेड विशेष सिम्बल्स के साथ चिह्नित होता है; टेप फैली हुई है या अनिश्चित रूप से दाईं ओर फैली हुई है।
एक हेड जो टेप पर सिम्बल्सों को पढ़ और लिख सकता है और टेप को बार में (और केवल एक) सेल को बाएं और दाएं घुमा सकता है। कुछ मॉडलों में हेड मूव करता है और टेप स्थिर रहता है।
एक स्टेट रजिस्टर जो ट्यूरिंग मशीन की स्थिति को स्टोर्ड करता है, जो कि अनेक में से है। इनमें से स्पेशल स्टार्ट स्टेट है जिसके साथ स्टेट रजिस्टर को इनिशियलाइज़ किया जाता है। ये स्टेट, ट्यूरिंग लिखते हैं, मन की उस स्थिति को प्रतिस्थापित करते हैं जो गणना करने वाला व्यक्ति सामान्य रूप से होता है।
एक परिमित टेबल ^[17] निर्देशों का^[18] वह, दिया गया स्टेट (q_i) मशीन वर्तमान में है और सिम्बल्स (a_j) यह टेप पर पढ़ रहा है (सिम्बल्स वर्तमान में हेड के नीचे), मशीन को अनुक्रम में निम्नलिखित करने के लिए कहता है (5-ट्यूपल मॉडल के लिए):

या तो मिटा दें या सिम्बल्स लिखें (a_j को a_j1 से प्रतिस्थापित करना) है.
हेड को मूव (जिसे d_k द्वारा वर्णित किया गया है और इसमें मान हो सकते हैं: स्टेप बाएं के लिए 'L' या स्टेप दाएं के लिए 'R' या ही स्थान पर रहने के लिए 'N')।
निर्धारित के अनुसार समान या नवीन स्थिति मान लें (स्टेट q_i1 पर जाएं).

4-ट्यूपल मॉडल में, किसी सिम्बल्स को मिटाना या लिखना (a_j1) और हेड को बाएँ या दाएँ घुमाना (d_k) अलग निर्देशों के रूप में निर्दिष्ट हैं। टेबल मशीन को (ia) मिटाने या सिम्बल्स लिखने या (ib) हेड को बाएँ या दाएँ ले जाने के लिए कहती है, और फिर (ii) उसी या नवीन स्थिति को निर्धारित करती है, किन्तु दोनों क्रियाओं (ia) और (ib) को नहीं ) उसी निर्देश में कुछ मॉडलों में, यदि सिम्बल्स और स्थिति के वर्तमान संयोजन के लिए टेबल में कोई प्रविष्टि नहीं है, तो मशीन रुक जाएगी; अन्य मॉडलों को एकत्रित के लिए सभी प्रविष्टियों की आवश्यकता होती है।

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

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

अगले Hopcroft & Ullman (1979, p. 148), (एक-टेप) ट्यूरिंग मशीन को औपचारिक रूप से 7-टपल $M=\langle Q,\Gamma ,b,\Sigma ,\delta ,q_{0},F\rangle$ के रूप में परिभाषित किया जा सकता है जहाँ

$\Gamma$ टेप वर्णमाला सिम्बल्सों का परिमित, गैर-रिक्त सेट है;
$b\in \Gamma$ रिक्त सिम्बल्स है (गणना के समय किसी भी स्टेप में असीम रूप से प्रायः टेप पर होने की अनुमति देने वाला एकमात्र सिम्बल्स);
$\Sigma \subseteq \Gamma \setminus \{b\}$ इनपुट सिम्बल्सों का सेट है, अर्थात , प्रारंभिक टेप सामग्री में दिखाई देने वाले सिम्बल्सों का सेट;
$Q$ स्टेटों का परिमित, गैर-रिक्त सेट है;
$q_{0}\in Q$ प्रारंभिक अवस्था है;
$F\subseteq Q$ अंतिम स्टेटों या स्वीकार करने वाले स्टेटों का सेट है। कहा जाता है कि प्रारंभिक टेप की सामग्री $M$ के द्वारा स्वीकार की जाती है यदि यह अंततः स्टेट $F$ में रुकता है .
$\delta :(Q\setminus F)\times \Gamma \not \to Q\times \Gamma \times \{L,R\}$ आंशिक कार्य है जिसे स्टेट संक्रमण प्रणाली कहा जाता है, जहाँ L लेफ्ट शिफ्ट है, R राइट शिफ्ट है। यदि $\delta$ वर्तमान स्थिति और वर्तमान टेप सिम्बल्स पर परिभाषित नहीं है, तो मशीन रुक जाती है;^[19] सहजता से, संक्रमण फ़ंक्शन वर्तमान स्थिति से प्रेषित अगले स्टेट को निर्दिष्ट करता है, जो सिम्बल्स हेड और आंदोलन द्वारा इंगित वर्तमान सिम्बल्स को अधिलेखित करता है, ।

3-स्टेट व्यस्त ऊदबिलाव। ब्लैक आइकन स्थान और हेड की स्थिति का प्रतिनिधित्व करते हैं; वर्ग रंग 1s (नारंगी) और 0s (सफेद) का प्रतिनिधित्व करते हैं; समय नीचे की ओर एचएएलटी अवस्था तक ऊपर से लंबवत रूप से आगे बढ़ता है।

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

दिशाओं $\{L,R\}$ के सेट के तृतीय तत्व के रूप में अपेक्षाकृत असामान्य संस्करण कोई परिवर्तन की अनुमति नहीं देता है, यदि N दर्शाते हैं .

3-स्टेट व्यस्त बीवर के लिए 7-ट्यूपल इस तरह दिखता है (ट्यूरिंग मशीन के उदाहरण में इस व्यस्त बीवर के बारे में और देखें):

$Q=\{{\mbox{A}},{\mbox{B}},{\mbox{C}},{\mbox{HALT}}\}$ (स्टेट);
$\Gamma =\{0,1\}$ (टेप वर्णमाला सिम्बल्स);
$b=0$ (रिक्त सिम्बल्स);
$\Sigma =\{1\}$ (इनपुट सिम्बल्स);
$q_{0}={\mbox{A}}$ (प्रारम्भिक अवस्था);
$F=\{{\mbox{HALT}}\}$ (अंतिम स्थिति);
$\delta =$ नीचे स्टेट-टेबल देखें (संक्रमण फ़ंक्शन)।

प्रारंभ में सभी टेप सेल्स $0$ को चिह्नित किया जाता है .

3-स्टेट, 2-सिम्बल व्यस्त बीवर के लिए स्टेट टेबल
टेप सिम्बल	करंट स्टेट ए			करंट स्टेट B			करंट स्टेट C
टेप सिम्बल	राइट सिम्बल	मूव टेप	नेक्स्ट स्टेट	राइट सिम्बल	मूव टेप	नेक्स्ट स्टेट	राइट सिम्बल	मूव टेप	नेक्स्ट स्टेट
0	1	R	B	1	L	A	1	L	B
1	1	L	C	1	R	B	1	R	एचएएलटी

ट्यूरिंग मशीनों की कल्पना या कार्यान्वयन के लिए आवश्यक अतिरिक्त विवरण

वैन एम्डे बोस (1990) के शब्दों में, पी। 6: सेट-सैद्धांतिक वस्तु [उसका औपचारिक सात-टुपल विवरण ऊपर के समान है] केवल आंशिक जानकारी प्रदान करता है कि मशीन कैसे व्यवहार करेगी और इसकी कंप्यूटर कैसी दिखेगी।

उदाहरण के लिए,

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

वैकल्पिक परिभाषा

लॉजिक या प्रमाणों को आसान या स्पष्ट बनाने के लिए साहित्य में परिभाषाएँ कभी-कभी थोड़ी भिन्न होती हैं, किन्तु यह सदैव इस तरह से किया जाता है कि परिणामी मशीन में समान कम्प्यूटेशनल शक्ति हो। उदाहरण के लिए, सेट $\{L,R\}$ को $\{L,R,N\}$ , परिवर्तित किया जा सकता है जहाँ N (कोई नहीं या कोई ऑपरेशन नहीं) मशीन को बाएँ या दाएँ चलने के अतिरिक्त उसी टेप सेल पर रहने की अनुमति देता है। इससे मशीन की कम्प्यूटेशनल शक्ति में वृद्धि नहीं होती है।

ट्यूरिंग/डेविस के सम्मेलन के अनुसार, ट्यूरिंग टेबल में प्रत्येक ट्यूरिंग निर्देश को नौ 5-टुपल्स में से द्वारा अधिक समान परंपरा का प्रतिनिधित्व करता है (ट्यूरिंग (1936) द अनडिसिडेबल में, पृष्ठ 126–127 और डेविस (2000) पृष्ठ 152) :

(परिभाषा 1): ' (q_i, S_j, S_k/E/N, L/R/N, q_m)

( current state q_i , symbol scanned S_j , print symbol S_k/erase E/none N , move_tape_one_square left L/right R/none N , new state q_m

अन्य लेखक (मिंस्की (1967) पृष्ठ 119, होपक्रॉफ्ट और उल्मैन (1979) पृष्ठ 158, स्टोन (1972) पृष्ठ 9) नए स्टेट q_m के साथ अलग सम्मेलन को अपनाते हैंस्कैन किए गए सिम्बल्स S_j के शीघ्र बाद सूचीबद्ध:

(परिभाषा 2): (q_i, S_j, q_m, S_k/E/N, L/R/N)

( current state q_i , symbol scanned S_j , new state q_m , print symbol S_k/erase E/none N , move_tape_one_square left L/right R/none N )

इस लेख के शेष भाग के लिए परिभाषा 1 (ट्यूरिंग/डेविस सम्मेलन) का उपयोग किया जाता है।

उदाहरण: 3-स्टेट 2-सिम्बल्स व्यस्त बीवर के लिए स्टेट टेबल को घटाकर 5-टुपल्स कर दिया गया है
करंट स्टेट	स्कैन सिम्बल्स	प्रिंट सिम्बल	मूव टेप	फाइनल (i.e. नेक्स्ट) स्टेट	5-टूपल
A	0	1	R	B	(A, 0, 1, R, B)
A	1	1	L	C	(A, 1, 1, L, C)
B	0	1	L	A	(B, 0, 1, L, A)
B	1	1	R	B	(B, 1, 1, R, B)
C	0	1	L	B	(C, 0, 1, L, B)
C	1	1	N	H	(C, 1, 1, N, H)

निम्नलिखित टेबल में, ट्यूरिंग के मूल मॉडल ने केवल प्रथम तीन पंक्तियों की अनुमति दी जिसे उन्होंने N1, N2, N3 कहा (cf. ट्यूरिंग इन द अनडेकिडेबल, पृष्ठ 126)। उन्होंने 0वें सिम्बल्स S का नाम देकर स्कैन किए गए वर्ग को मिटाने की अनुमति S₀ = इरेज़ या ब्लैंक, आदि। चूंकि, उन्होंने गैर-मुद्रण की अनुमति नहीं दी, इसलिए प्रत्येक निर्देश-पंक्ति में प्रिंट सिम्बल्स S_k सम्मिलित है या मिटाना (cf. फुटनोट 12 इन पोस्ट (1947), द अनडिसीडेबल, पृष्ठ 300)। संक्षिप्ताक्षर ट्यूरिंग हैं (द अनडिसिडेबल, पृष्ठ 119)। 1936-1937 में ट्यूरिंग के मूल पेपर के पश्चात, मशीन-मॉडल ने सभी नौ संभावित प्रकार के पांच-टुपल्स की अनुमति दी है:

	करंट एम-कॉन्फिगरेशन (ट्यूरिंग स्टेट)	टेप सिम्बल	प्रिंट-ऑपरेशन	टेप-मोशन	फाइनल एम-कॉन्फिगरेशन (ट्यूरिंग स्टेट)	5-टूपल	5-टूपल कमेंट्स	4-टूपल
N1	q_i	S_j	प्रिंट(S_k)	लेफ्ट L	q_m	(q_i, S_j, S_k, L, q_m)	"blank" = S₀, 1=S₁, etc.
N2	q_i	S_j	प्रिंट(S_k)	राइट R	q_m	(q_i, S_j, S_k, R, q_m)	"blank" = S₀, 1=S₁, etc.
N3	q_i	S_j	प्रिंट(S_k)	None N	q_m	(q_i, S_j, S_k, N, q_m)	"blank" = S₀, 1=S₁, etc.	(q_i, S_j, S_k, q_m)
4	q_i	S_j	None N	लेफ्ट L	q_m	(q_i, S_j, N, L, q_m)		(q_i, S_j, L, q_m)
5	q_i	S_j	None N	राइट R	q_m	(q_i, S_j, N, R, q_m)		(q_i, S_j, R, q_m)
6	q_i	S_j	None N	None N	q_m	(q_i, S_j, N, N, q_m)	डायरेक्ट ''जम्प''	(q_i, S_j, N, q_m)
7	q_i	S_j	इरेज़	लेफ्ट L	q_m	(q_i, S_j, E, L, q_m)
8	q_i	S_j	इरेज़	राइट R	q_m	(q_i, S_j, E, R, q_m)
9	q_i	S_j	इरेज़	None N	q_m	(q_i, S_j, E, N, q_m)		(q_i, S_j, E, q_m)

किसी भी ट्यूरिंग टेबल (निर्देशों की सूची) का निर्माण उपरोक्त नौ 5-टुपल्स से किया जा सकता है। तकनीकी कारणों से, तीन गैर-मुद्रण या एन निर्देश (4, 5, 6) को सामान्यतः समाप्त किया जा सकता है। उदाहरण के लिए ट्यूरिंग मशीन के उदाहरण देखें।

इस प्रकार से कम प्रायः 4-ट्यूपल्स का उपयोग होता है: ये ट्यूरिंग निर्देशों (cf. पोस्ट (1947), बूलोस और जेफरी (1974, 1999), डेविस-सिगल-वेयुकर (1994)) के और परमाणुकरण का प्रतिनिधित्व करते हैं; पोस्ट-ट्यूरिंग मशीन पर और देखें।

स्टेट

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

इस प्रकार किसी भी स्तर पर गणना की प्रगति की स्थिति पूर्ण रूप से टेप पर दिए गए निर्देशों और प्रतीकों के नोट द्वारा निर्धारित होती है। अर्थात्, सिस्टम की स्थिति को एक एकल अभिव्यक्ति (सिम्बल का अनुक्रम) द्वारा वर्णित किया जा सकता है जिसमें टेप पर प्रतीकों के पश्चात Δ (जो अन्यत्र प्रकट नहीं होना चाहिए) और फिर निर्देशों के नोट द्वारा वर्णित किया जा सकता है। इस अभिव्यक्ति को "स्टेट सूत्र" कहा जाता है।
— — द अनडिसीडेबल, पृ. 139-140, से जोड़ा गया है।

इससे पूर्व अपने पेपर में ट्यूरिंग ने इसे और भी आगे बढ़ाया: वह उदाहरण देता है जहां उसने वर्तमान एम-कॉन्फ़िगरेशन का सिम्बल्स रखा है - निर्देश का लेबल - स्कैन किए गए वर्ग के नीचे, टेप पर सभी सिम्बल्सों के साथ (अनिर्णायक, पृष्ठ 121) ); इसे वह पूर्ण विन्यास कहते हैं (अनिर्णायक, पृ. 118)। पूर्ण कॉन्फ़िगरेशन को लाइन पर प्रिंट करने के लिए, वह स्कैन किए गए सिम्बल्स के बाईं ओर स्थिति-लेबल/एम-कॉन्फ़िगरेशन रखता है।

इसका रूप क्लेन (1952) में देखा गया है जहां स्टीफन कोल क्लेन दिखाता है कि मशीन की स्थिति का गोडेल नंबर कैसे लिखा जाता है: वह एम-कॉन्फ़िगरेशन सिम्बल्स "q₄" रखता है। स्कैन किए गए वर्ग के ऊपर सामान्य रूप से टेप पर 6 गैर-रिक्त वर्गों के केंद्र में (इस लेख में ट्यूरिंग-टेप का आंकड़ा देखें) और इसे स्कैन किए गए वर्ग के दाईं ओर रखता है। किन्तु क्लेन "q₄" को संदर्भित करता है मशीन स्थिति के रूप में ही (क्लीन, पृष्ठ 374-375)। हॉपक्रॉफ्ट और उलमैन इस संयोजन को तात्कालिक विवरण कहते हैं और वर्तमान स्थिति (निर्देश-लेबल, एम-कॉन्फ़िगरेशन) को स्कैन किए गए सिम्बल्स (पृष्ठ 149) के बाईं ओर रखने के ट्यूरिंग सम्मेलन का पालन करते हैं, अर्थात , तात्कालिक विवरण समग्र है बाईं ओर गैर-रिक्त सिम्बल्सों की संख्या, मशीन की स्थिति, हेड द्वारा स्कैन किया गया वर्तमान सिम्बल्स और दाईं ओर गैर-रिक्त सिम्बल्स है।

उदाहरण: 3 "मूव" के पश्चात 3-स्टेट 2-प्रतीक व्यस्त बीवर की कुल स्थिति (नीचे दिए गए चित्र में "रन" उदाहरण से ली गई है):

1A1

इसका अर्थ यह है: कि तीन मूव के पश्चात टेप में ... 000110000 ... होता है, हेड अधिक दाहिनी ओर 1 स्कैन कर रहा है, और स्थिति ए है। कुल स्टेट जैसा कि यहाँ दिखाया गया है: B01; टेप पर केवल 1 है, किन्तु हेड 0 (रिक्त) को उसके बाईं ओर स्कैन कर रहा है और स्थिति B है।

ट्यूरिंग मशीनों के संदर्भ में "स्टेट" को स्पष्ट किया जाना चाहिए कि किसका वर्णन किया जा रहा है: वर्तमान निर्देश, या वर्तमान निर्देश के साथ टेप पर प्रतीकों की सूची, या वर्तमान निर्देश के साथ टेप पर प्रतीकों की सूची स्कैन किए गए प्रतीक के बाईं ओर या स्कैन किए गए प्रतीक के दाईं ओर रखा जाता है।

ट्यूरिंग के जीवनी लेखक एंड्रयू होजेस (1983: 107) ने इस अस्पष्ट को नोट किया और उस पर चर्चा की है।

स्टेट आरेख

3-स्टेट बिजी बीवर के लिए तालिका ("पी" = "1" प्रिंट/लिखें)
टेप सिम्बल	करंट स्टेट A			करंट स्टेट B			करंट स्टेट C
	राइट सिम्बल	मूव टेप	नेक्स्ट स्टेट	राइट सिम्बल	मूव टेप	नेक्स्ट स्टेट	राइट सिम्बल	मूव टेप	नेक्स्ट स्टेट
0	P	R	B	P	L	A	P	L	B
1	P	L	C	P	R	B	P	R	एचएएलटी

3-स्टेट व्यस्त ऊदबिलाव ट्यूरिंग मशीन परिमित-स्टेट मशीन में परिमित-स्टेट प्रतिनिधित्व। प्रत्येक वृत्त टेबल की स्थिति का प्रतिनिधित्व करता है - एम-कॉन्फ़िगरेशन या निर्देश। स्टेट संक्रमण की दिशा तीर द्वारा दर्शाई गई है। आउटगोइंग स्थिति (तीर के अंत में) के पास लेबल (जैसे 0/P, R) स्कैन किए गए सिम्बल्स को निर्दिष्ट करता है जो विशेष संक्रमण (जैसे 0) के बाद स्लैश / का कारण बनता है, जिसके बाद मशीन के बाद के व्यवहार होते हैं, उदा. P प्रिंट करें फिर टेप R को दाएँ ले जाएँ। कोई सामान्य स्वीकृत प्रारूप उपस्तिथ नहीं है। दिखाया गया सम्मेलन मैकक्लस्की (1965), बूथ (1967), हिल और पीटरसन (1974) के बाद है।

दाईं ओर: ऊपर दी गई टेबल को स्टेट संक्रमण आरेख के रूप में व्यक्त किया गया है।

सामान्यतः उच्च टेबल को टेबल के रूप में छोड़ देना उत्तम होता है (बूथ, पृ. 74)। वे कंप्यूटर द्वारा सारणीबद्ध रूप में अधिक सरलता से सिम्युलेट किए जाते हैं (बूथ, पृ. 74)। चूंकि , कुछ अवधारणाएँ- उदाहरण के लिए रीसेट स्थिति वाली मशीनें और दोहराए जाने वाले पैटर्न वाली मशीनें (cf. हिल और पीटरसन पृष्ठ 244ff)—चित्रकारी के रूप में देखे जाने पर अधिक सरलता से देखी जा सकती हैं।

इस प्रकार से क्या चित्र अपनी टेबल में सुधार का प्रतिनिधित्व करता है, यह पाठक द्वारा विशेष संदर्भ के लिए तय किया जाना चाहिए।

व्यस्त ऊदबिलाव की कंप्यूटर का विकास शीर्ष पर प्रारंभ होता है और नीचे की ओर बढ़ता है।

पाठक को फिर से सावधान किया जाना चाहिए कि इस तरह के चित्र समय और स्थान के माध्यम से गणना के पाठ्यक्रम (प्रक्षेपवक्र) नहीं, समय में एकत्रित हुए उनकी टेबल के स्नैपशॉट का प्रतिनिधित्व करते हैं। जबकि हर बार व्यस्त बीवर मशीन चलती है, यह सदैव ही स्टेट-प्रक्षेपवक्र का पालन करेगी, यह कॉपी मशीन के लिए सही नहीं है जिसे चर इनपुट मापदंडों के साथ प्रदान किया जा सकता है।

गणना की आरेख प्रगति प्रारंभ से अंत तक इसकी गणना के माध्यम से तीन-स्टेट व्यस्त बीवर की स्थिति (निर्देश) की प्रगति को दर्शाती है। दायीं ओर ट्यूरिंग पूर्ण विन्यास है (क्लीन स्थिति, होपक्रॉफ्ट-उलमैन तात्कालिक विवरण ) प्रत्येक स्टेप पर है। यदि मशीन को रोका जाना था और स्टेट रजिस्टर और पूर्ण टेप दोनों को रिक्त करने के लिए क्लीन किया जाना था, तो इन कॉन्फ़िगरेशन का उपयोग इसकी प्रगति में कहीं भी कंप्यूटर को फिर से प्रारंभ करने के लिए (cf. ट्यूरिंग (1936) द अनडेसिडेबल, पीपी। 139-140) किया जा सकता है।

इक्विवैलेंट मॉडल

इस प्रकार से अनेक मशीनें जिनके बारे में सोचा जा सकता है कि साधारण यूनिवर्सल ट्यूरिंग मशीन की तुलना में अधिक कम्प्यूटेशनल क्षमता है, उन्हें और अधिक शक्ति नहीं दिखाया जा सकता है (हॉपक्रॉफ्ट और उल्मैन पृष्ठ 159, cf. Minsky (1967))। वे तीव्र से गणना कर सकते हैं, इसके अतिरिक्त, या कम मेमोरी का उपयोग कर सकते हैं, या उनका निर्देश सेट छोटा हो सकता है, किन्तु वे अधिक शक्तिशाली रूप से गणना नहीं कर सकते (अर्थात अधिक गणितीय कार्य)। (चर्च-ट्यूरिंग थीसिस किसी भी प्रकार की मशीन के लिए इसे सत्य मानती है: कि किसी भी वस्तु की गणना किसी ट्यूरिंग मशीन द्वारा की जा सकती है।)

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

द्वतीय चरम पर, कुछ अधिक ही सरल मॉडल ट्यूरिंग पूर्णता के रूप में सामने आते हैं | ट्यूरिंग-समतुल्य, अर्थात ट्यूरिंग मशीन मॉडल के समान कम्प्यूटेशनल शक्ति रखने के लिए है।

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

रीड-ओनली, दाहिनी ओर चलने वाली ट्यूरिंग मशीनें डीएफए (साथ ही एनडीएफए से डीएफए रूपांतरण एल्गोरिदम का उपयोग करके रूपांतरण द्वारा एनएफए) के समान हैं।

व्यावहारिक और व्यावहारिक उद्देश्यों के लिए समतुल्य रजिस्टर मशीन का उपयोग सामान्य असेंबली लैंग्वेज प्रोग्रामिंग लैंग्वेज के रूप में किया जा सकता है।

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

सिद्धांत रूप में यह केवल ट्यूरिंग पूर्ण है, क्योंकि प्रोग्रामिंग लैंग्वेज में मेमोरी आवंटन को विफल होने दिया जाता है, जिसका अर्थ है कि विफल मेमोरी आवंटन की अनदेखी करते समय प्रोग्रामिंग लैंग्वेज ट्यूरिंग पूर्ण हो सकती है, किन्तु रियल कंप्यूटर पर निष्पादन योग्य कम्पाइल्ड प्रोग्राम नहीं हो सकते है।

च्वाइस सी-मशीन, ऑरेकल ओ-मशीन

अपने पेपर के आरंभ में (1936) ट्यूरिंग स्वचालित मशीन के मध्य अंतर करता है - इसकी गति ... पूर्ण रूप से कॉन्फ़िगरेशन और पसंद मशीन द्वारा निर्धारित:

...जिसकी गति केवल आंशिक रूप से कॉन्फ़िगरेशन द्वारा निर्धारित की जाती है ... जब ऐसी मशीन इन अस्पष्ट कॉन्फ़िगरेशन में से एक तक पहुंचती है, तो यह तब तक नहीं चल सकती जब तक कि बाहरी ऑपरेटर द्वारा कुछ इच्छानुसार विकल्प नहीं चुना जाता है। यदि हम स्वयंसिद्ध प्रणालियों से निपटने के लिए मशीनों का उपयोग कर रहे होते तो यही स्थिति होती है।
— — द अनडिसीडेबल, पृ. 118

ट्यूरिंग (1936) ने फ़ुटनोट को छोड़कर और अधिक विस्तार से नहीं बताया है जिसमें उन्होंने वर्णन किया है कि चॉइस मशीन का उपयोग करने के अतिरिक्त "[हिल्बर्ट] कैलकुलस के सभी सिद्ध सूत्रों को खोजने" के लिए ए-मशीन का उपयोग कैसे किया जाए। उनका मानना है कि विकल्प सदैव दो संभावनाओं 0 और 1 के बीच होते हैं। प्रत्येक प्रमाण तब विकल्पों के अनुक्रम i₁, i₂, ..., i_n (i₁ = 0 या 1, i₂ = 0 या 1 , ..., 1, ..., i_n = 0 या 1) द्वारा निर्धारित किया जाएगा।, और इसलिए संख्या 2ⁿ + i₁2^n-1 + i₂2^n-2 + ... +i_n पूर्ण रूप से प्रमाण को निर्धारित करता है। स्वचालित मशीन क्रमिक रूप से प्रमाण 1, प्रमाण 2, प्रमाण 3 को पूर्ण करती है , ..." (फुटनोट ‡, द अनडिसीडेबल, पृष्ठ 138) करती है।

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

अतः ओरेकल मशीन या ओ-मशीन ट्यूरिंग मशीन है जो अपनी गणना को स्थिति "o"' पर रोक देती है, जबकि अपनी गणना पूर्ण करने के लिए, यह ऑरेकल के निर्णय की सिम्बल्स्षा करती है - अनिर्दिष्ट इकाई यह कहने के अतिरिक्त कि यह मशीन नहीं हो सकती ( ट्यूरिंग (1939), द अनडिसीडेबल, पृष्ठ 166-168) है।

यूनिवर्सल ट्यूरिंग मशीन

ट्यूरिंग मशीन का कार्यान्वयन

जैसा कि ट्यूरिंग ने द अनडिसीडेबल में लिखा है, पृ. 128 (इटैलिक जोड़े गए):

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

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

ट्यूरिंग का पेपर... संक्षेप में, आधुनिक कंप्यूटर का आविष्कार और उसके साथ जुड़ी कुछ प्रोग्रामिंग तकनीकों को सम्मिलित करता है।.
— — मिन्स्की (1967), पृ. 104

कम्प्यूटेशनल सम्मिश्र सिद्धांत के संदर्भ में, मल्टी-टेप यूनिवर्सल ट्यूरिंग मशीन को केवल उन मशीनों की तुलना में लॉगरिदमिक फैक्टर द्वारा धीमा होना चाहिए जो इसे अनुकरण करती हैं। यह परिणाम 1966 में F. C. हेनी और R. E. स्टर्न्स द्वारा प्राप्त किया गया था। (अरोड़ा और बराक, 2009, प्रमेय 1.9)

रियल मशीनों के साथ तुलना

लेगो टुकड़ों का उपयोग करके ट्यूरिंग मशीन की प्राप्ति

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

यह समझाने के अनेक विधि हैं कि ट्यूरिंग मशीन रियल कंप्यूटर के उपयोगी मॉडल क्यों हैं:

एक रियल कंप्यूटर कुछ भी गणना कर सकता है, ट्यूरिंग मशीन भी गणना कर सकती है। उदाहरण के लिए: ट्यूरिंग मशीन प्रोग्रामिंग लैंग्वेज में पाए जाने वाले किसी भी प्रकार के सबरूटीन का अनुकरण कर सकती है, जिसमें पुनरावर्ती प्रक्रियाएं और ज्ञात पैरामीटर-पासिंग मैकेनिज्म (हॉपक्रॉफ्ट और उल्मैन पृष्ठ 157) सम्मिलित हैं। बड़ा पर्याप्त एफएसए IO की अवहेलना करते हुए किसी भी रियल कंप्यूटर को भी मॉडल कर सकता है। इस प्रकार, ट्यूरिंग मशीनों की सीमाओं के बारे में स्टेटमेंट रियल कंप्यूटरों पर भी प्रयुक्त होता है।
अंतर केवल ट्यूरिंग मशीन की असीमित मात्रा में डेटा में परिवर्तन करने की क्षमता के साथ है। चूंकि, सीमित समय दिया गया है, ट्यूरिंग मशीन (एक रियल मशीन की तरह) केवल डेटा की सीमित मात्रा में परिवर्तन कर सकती है।
एक ट्यूरिंग मशीन की तरह, रियल मशीन में अधिक डिस्क या अन्य स्टोरेज मीडिया प्राप्त करके, इसकी स्टोरेज स्पेस को आवश्यकतानुसार बढ़ाया जा सकता है।
ट्यूरिंग मशीनों का उपयोग करने वाले विवरणों की तुलना में सरल अमूर्त मॉडल का उपयोग करने वाले रियल मशीन प्रोग्राम के विवरण प्रायः अधिक सम्मिश्र होते हैं। उदाहरण के लिए, एल्गोरिथ्म का वर्णन करने वाली ट्यूरिंग मशीन में कुछ सौ अवस्थाएँ हो सकती हैं, जबकि किसी रियल मशीन पर समतुल्य नियतात्मक परिमित ऑटोमेटन (डीएफए) में क्वाड्रिलियन होते हैं। यह डीएफए प्रतिनिधित्व का विश्लेषण करने के लिए अक्षम बनाता है।
ट्यूरिंग मशीनें एल्गोरिदम का वर्णन करती हैं जो इस बात से स्वतंत्र हैं कि वे कितनी मेमोरी का उपयोग करते हैं। किसी भी उपस्तिथ मशीन के समीप मेमोरी की सीमा होती है, किन्तु यह सीमा समय के साथ इच्छानुसार से बढ़ सकती है। ट्यूरिंग मशीन हमें एल्गोरिदम के बारे में स्टेटमेंट देने की अनुमति देती है जो (सैद्धांतिक रूप से) पारंपरिक कंप्यूटिंग मशीन आर्किटेक्चर में प्रगति की परवाह किए बिना सदैव के लिए बनी रहती है।
ट्यूरिंग मशीन एल्गोरिदम के कथन को सरल बनाती है। ट्यूरिंग-समतुल्य अमूर्त मशीनों पर चलने वाले एल्गोरिदम सामान्यतः रियल मशीनों पर चलने वाले उनके समसेल्स की तुलना में अधिक सामान्य होते हैं, क्योंकि उनके पास इच्छानुसार से स्पष्ट डेटा प्रकार उपलब्ध होते हैं और उन्हें कभी भी अप्रत्याशित परिस्थितियों से सामना नहीं करना पड़ता है (मेमोरी से बाहर चलने सहित, किन्तु सीमित नहीं) .

एक और ट्यूरिंग मशीन की प्राप्ति

सीमाएं

कम्प्यूटेशनल सम्मिश्र सिद्धांत

ट्यूरिंग मशीनों की सीमा यह है कि वे किसी विशेष व्यवस्था की शक्ति को सही प्रकार से मॉडल नहीं करते हैं। उदाहरण के लिए, आधुनिक स्टोर्ड प्रोग्राम कंप्यूटर वास्तव में अमूर्त मशीन के अधिक विशिष्ट रूप के उदाहरण हैं जिन्हें रैंडम-एक्सेस स्टोर्ड प्रोग्राम मशीन या आरएएसपी मशीन मॉडल के रूप में जाना जाता है। यूनिवर्सल ट्यूरिंग मशीन की तरह, आरएएसपी अपने कार्यक्रम को अपनी परिमित-स्टेट मशीन के निर्देशों के बाहर मेमोरी में स्टोर्ड करता है। यूनिवर्सल ट्यूरिंग मशीन के विपरीत, आरएएसपी में भिन्न-भिन्न, क्रमांकित किन्तु असीमित रजिस्टरों की अनंत संख्या होती है - मेमोरी सेल जिसमें कोई भी पूर्णांक हो सकता है (cf. एल्गोट और रॉबिन्सन (1964), हार्टमैनिस (1971), और विशेष रूप से कुक-रेचो (1973) ); रैंडम-एक्सेस मशीन पर संदर्भ)। आरएएसपी की परिमित-स्टेट मशीन अप्रत्यक्ष पते की क्षमता से लैस है (उदाहरण के लिए, रजिस्टर की सामग्री को दूसरे रजिस्टर को निर्दिष्ट करने के लिए पते के रूप में उपयोग किया जा सकता है); इस प्रकार आरएएसपी का कार्यक्रम रजिस्टर-अनुक्रम में किसी भी रजिस्टर को संबोधित कर सकता है। इस अंतर का परिणाम यह है कि ऐसे कम्प्यूटेशनल ऑप्टिमाइजेशन हैं जो मेमोरी इंडेक्स के आधार पर किए जा सकते हैं, जो सामान्य ट्यूरिंग मशीन में संभव नहीं हैं; इस प्रकार जब ट्यूरिंग मशीनों को बाउंडिंग रनिंग टाइम के आधार के रूप में उपयोग किया जाता है, तो कुछ एल्गोरिदम के चलने के समय (ट्यूरिंग मशीन की गलत सरलीकृत धारणा के कारण) पर असत्य निचली सीमा सिद्ध की जा सकती है। इसका उदाहरण बाइनरी सर्च है, एल्गोरिदम जिसे ट्यूरिंग मशीन मॉडल के अतिरिक्त गणना के आरएएसपी मॉडल का उपयोग करते समय अधिक तीव्र से प्रदर्शन करने के लिए दिखाया जा सकता है।

समवर्ती

ट्यूरिंग मशीनों की और सीमा यह है कि वे समवर्ती (कंप्यूटर_साइंस) को पूर्ण रूप से मॉडल नहीं करती हैं। उदाहरण के लिए, पूर्णांक के आकार पर सीमा होती है जिसकी गणना रिक्त टेप पर प्रारंभ होने वाली सदैव रुकने वाली गैर-नियतात्मक ट्यूरिंग मशीन द्वारा की जा सकती है। (असीमित नॉनडेटरमिनिस्म पर लेख देखें।) इसके विपरीत, बिना किसी इनपुट के सदैव रुकने वाली समवर्ती प्रणालियाँ होती हैं जो असीमित आकार के पूर्णांक की गणना कर सकती हैं। (स्थानीय स्टोरेज के साथ प्रक्रिया बनाई जा सकती है जिसे 0 की गिनती के साथ आरंभ किया जाता है जो समवर्ती रूप से स्टॉप और गो संदेश दोनों भेजता है। जब इसे गो संदेश प्राप्त होता है, तो यह 1 से अपनी गिनती बढ़ाता है और स्वयं को संदेश भेजता है। जब यह स्टॉप संदेश प्राप्त करता है, यह अपने स्थानीय स्टोरेज में असीमित संख्या के साथ बंद हो जाता है।)

इंटरेक्शन

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

1970 के दशक के बाद से, कंप्यूटरों का इंटरैक्टिव उपयोग बहुत अधिक सामान्य हो गया। सिद्धांत रूप में, बाहरी एजेंट को टेप से पढ़ने और ट्यूरिंग मशीन के रूप में ही समय में लिखने के द्वारा इसे मॉडल करना संभव है, किन्तु यह संभवतः ही कभी मेल खाता है कि इंटरैक्टिव वास्तव में कैसे होती है; इसलिए, अन्तरक्रियाशीलता का वर्णन करते समय, इनपुट/आउटपुट ऑटोमेटन I/O ऑटोमेटा जैसे विकल्प सामान्यतः प्राथमिकता दी जाती है।

इतिहास

ऐतिहासिक पृष्ठभूमि: कम्प्यूटेशनल मशीनरी

रॉबिन गैंडी (1919-1995) - एलन ट्यूरिंग (1912-1954) के छात्र, और उनके आजीवन दोस्त - चार्ल्स बैबेज (लगभग 1834) में गणना मशीन की धारणा के वंश का पता लगाते हैं और वास्तव में बैबेज की थीसिस का प्रस्ताव देते हैं:

विश्लेषण का संपूर्ण विकास और संचालन अब मशीनरी द्वारा निष्पादित करने में सक्षम है.
— — (गैंडी द्वारा उद्धृत बैबेज में इटैलिक, पृष्ठ 54)

बैबेज के विश्लेषणात्मक इंजन का गैंडी का विश्लेषण निम्नलिखित पांच कार्यों का वर्णन करता है (cf. p. 52–53):

अंकगणितीय फलन +, -, ×, जहां - "उचित" घटाव x - y = 0 को निरुपित करता है यदि y ≥ x।
संचालन का कोई भी क्रम ऑपरेशन है।
एक ऑपरेशन का पुनरावृत्ति (एन बार ऑपरेशन P दोहराना)।
कंडीशनल इटेरेसन (परीक्षण t की सफलता पर एन बार ऑपरेशन p नियमित दोहराना)।
कंडीशनल ट्रान्सफर (अर्थात , नियमित "goto")।

गैंडी का कहना है कि जिन कार्यों की गणना (1), (2), और (4) द्वारा की जा सकती है, वे ठीक वही हैं जो ट्यूरिंग संगणनीय हैं। (पृष्ठ 53)। वह पर्सी लुडगेट (1909), लियोनार्डो टोरेस और क्यूवेदो (1914), मौरिस डी'ओकग्ने (1922), लुइस कॉफिग्नल (1933), वन्नेवर बुश (1936), हावर्ड ऐकेन (1937) सहित यूनिवर्सल कैलकुलेटिंग मशीनों के लिए अन्य प्रस्तावों का मिसाल देते हैं। . चूंकि :

... अंकगणितीय संक्रियाओं के एक निश्चित पुनरावर्तनीय अनुक्रम की प्रोग्रामिंग पर जोर दिया गया है। गणना मशीनों के सामान्य सिद्धांत के लिए सशर्त पुनरावृत्ति और कंडीशनल इटेरेसन के मौलिक महत्व को मान्यता नहीं दी गई है...…
— — गैंडी पी. 55

एन्ट्सचीडुंग्सप्रोब्लेम (निर्णय समस्या): हिल्बर्ट का 1900 का दसवां प्रश्न

इस प्रकार से 1900 में प्रसिद्ध गणितज्ञ डेविड हिल्बर्ट द्वारा प्रस्तुत की गई हिल्बर्ट की समस्याओं के संबंध में, समस्या #10 का भाग लगभग 30 वर्षों से चल रहा था, जब तक कि इसे स्पष्ट रूप से तैयार नहीं किया गया था। नंबर 10 के लिए हिल्बर्ट की मूल अभिव्यक्ति इस प्रकार है:

10. डायोफैंटाइन समीकरण की सॉल्वेबिलिटी का निर्धारण। अज्ञात मात्राओं की किसी भी संख्या और तर्कसंगत अभिन्न गुणांक के साथ एक डायोफैंटाइन समीकरण दिया गया: एक प्रक्रिया तैयार करने के लिए जिसके अनुसार यह सीमित संख्या में संचालन में निर्धारित किया जा सकता है कि समीकरण तर्कसंगत पूर्णांक में हल करने योग्य है या नहीं। एन्ट्सचीडुंग्सप्रोब्लेम [प्रथम-क्रम तर्क के लिए निर्णय समस्या] तब हल हो जाती है जब हम एक ऐसी प्रक्रिया जानते हैं जो किसी भी तार्किक अभिव्यक्ति को सीमित रूप से कई परिचालनों द्वारा इसकी वैधता या संतुष्टि का निर्णय लेने की अनुमति देती है ... एन्ट्सचीडुंग्सप्रोब्लेम को गणितीय तर्क की मुख्य समस्या माना जाना चाहिए।.
— — उद्धृत, इस अनुवाद और मूल जर्मन के साथ, डर्शोविट्ज़ और गुरेविच में, 2008

1922 तक, एन्ट्सचीडुंग्सप्रोब्लेम की यह धारणा थोड़ी विकसित हो गई थी, और हेनरिक बेहमन | एच। बेहमन ने कहा

... ...एंट्सचीडुंग्सप्रॉब्लम का सबसे सामान्य रूप [है] इस प्रकार है:
सामान्यतः प्रयुक्त होने वाले एक बिल्कुल निश्चित उपाय की आवश्यकता होती है जो किसी दिए गए विशुद्ध तार्किक अधिकार की सत्य या असत्य को सीमित संख्या में चरणों में तय करने की अनुमति देगा। ...
— गैंडी पी. 57, बेहमन को उद्धृत करते हुए

बेहमैन की टिप्पणी है कि... सामान्य समस्या यह तय करने की समस्या के समान है कि कौन से गणितीय प्रस्ताव सत्य हैं।
— ibid.

यदि कोई एन्ट्सचीडुंग्सप्रोब्लेम को हल करने में सक्षम होता तो उसके पास "अनेक (या यहां तक कि सभी) गणितीय समस्याओं को हल करने की प्रक्रिया होती"".
— ibid., p. 92

अतः 1928 में गणितज्ञों की अंतर्राष्ट्रीय कांग्रेस द्वारा, हिल्बर्ट ने अपने प्रश्नों को अधिक स्पष्ट बनाया। प्रथम , गणित पूर्णता (लॉजिक ) था ... द्वतीय, गणित संगति प्रमाण था ... और तृतीय, गणित निर्णायकता (लॉजिक ) था? (होजेस पृष्ठ 91, हॉकिंग पृष्ठ 1121)। पहले दो सवालों का उत्तर 1930 में कर्ट गोडेल ने उसी बैठक में दिया था, जहां हिल्बर्ट ने अपना सेवानिवृत्ति भाषण दिया था (हिल्बर्ट को बहुत दुख हुआ था); तीसरी- एन्ट्सचीडुंग्सप्रोब्लेम- को 1930 के दशक के मध्य तक सिम्बल्स्षा करनी पड़ी है।

समस्या यह थी कि उत्तर के लिए पहले निश्चित सामान्य प्रयुक्त उपाय की स्पष्ट परिभाषा की आवश्यकता होती थी, जिसे प्रिंसटन के प्रोफेसर अलोंजो चर्च प्रभावी गणनात्मकता कहते थे, और 1928 में ऐसी कोई परिभाषा उपस्तिथ नहीं थी। किन्तु अगले 6-7 वर्षों में एमिल पोस्ट ने निर्देशों की सूची (1936 के बाद) के अनुसार कमरे से दूसरे कमरे में लिखने और चिन्ह मिटाने वाले कार्यकर्ता की अपनी परिभाषा विकसित की, जैसा कि चर्च और उनके दो छात्रों स्टीफन क्लेन और जे.बी. रोसेर ने किया था। चर्च का लैम्ब्डा-कैलकुलस और गोडेल का पुनरावर्तन सिद्धांत (1934)। चर्च के पेपर (15 अप्रैल 1936 को प्रकाशित) ने दिखाया कि एंट्सचेइडुंग्सप्रोब्लेम वास्तव में अनिर्णीत था और ट्यूरिंग को लगभग साल तक हरा दिया (ट्यूरिंग का पेपर 28 मई 1936 को प्रस्तुत किया गया, जनवरी 1937 को प्रकाशित हुआ)। इस मध्य , एमिल पोस्ट ने 1936 के पतन में संक्षिप्त पत्र प्रस्तुत किया, इसलिए ट्यूरिंग को कम से कम पोस्ट पर प्राथमिकता मिली। जबकि चर्च ने ट्यूरिंग के पेपर को रेफर किया था, ट्यूरिंग के समीप चर्च के पेपर का अध्ययन करने और परिशिष्ट जोड़ने का समय था जहां उन्होंने प्रमाण को स्केच किया कि चर्च का लैम्ब्डा-कैलकुलस और उनकी मशीनें समान कार्यों की गणना करेंगी।

किन्तु चर्च ने जो किया वह कुछ अलग था, और एक निश्चित अर्थ में निर्बल था। ... ट्यूरिंग निर्माण अधिक प्रत्यक्ष था, और चर्च के प्रदर्शन में अंतर को बंद करते हुए, पूर्व के सिद्धांतों से एक तर्क प्रदान किया है।.
— होजेस पी. 112

और पोस्ट ने केवल चर्च-ट्यूरिंग थीसिस की परिभाषा प्रस्तावित की थी और चर्च की परिभाषा की आलोचना की थी, किन्तु कुछ भी प्रमाणित नहीं किया था।

एलन ट्यूरिंग की ए-मशीन

चूंकि 1935 के वसंत में, कैम्ब्रिज के किंग्स कॉलेज में मास्टर के युवा छात्र के रूप में ट्यूरिंग ने चुनौती ली; वह लॉजिक शास्त्री एम. एच. ए. न्यूमैन के व्याख्यानों से प्रेरित हुए थे और उनसे गोडेल के कार्य और एंट्सचेइडुंग्सप्रोब्लेम के बारे में सीखा ... न्यूमैन ने 'मैकेनिकल' शब्द का उपयोग किया ... ट्यूरिंग 1955 के अपने मृत्युलेख में न्यूमैन लिखते हैं:

इस प्रश्न पर कि 'एक "यांत्रिक" प्रक्रिया क्या है?' ट्यूरिंग ने विशिष्ट उत्तर दिया 'कुछ ऐसा जो एक मशीन द्वारा किया जा सकता है' और उन्होंने एक कंप्यूटिंग मशीन की सामान्य धारणा का विश्लेषण करने के अत्यधिक अनुकूल कार्य को प्रारंभ किया।गैंडी कहते हैं कि:.
— गैंडी, पी. 74

मैं मानता हूं, किन्तु नहीं जानता, कि ट्यूरिंग ने, अपने कार्य के प्रारंभ से ही, अपने लक्ष्य के रूप में एन्ट्सचीडुंग्सप्रॉब्लम की अनिर्णयता का प्रमाण रखा था। उन्होंने मुझे बताया कि पेपर का 'मुख्य विचार' उन्हें तब आया जब वह 1935 की गर्मियों में ग्रांटचेस्टर घास के मैदान में लेटे हुए थे। 'मुख्य विचार' या तो गणना का उनका विश्लेषण रहा होगा या उनका यह अहसास रहा होगा कि एक सार्वभौमिक मशीन थी , और इसलिए एक कैंटर का विकर्ण तर्क विकर्ण तर्क अघुलनशील प्रमाणित करने के लिए।
— ibid., p. 76

जबकि गैंडी का मानना था कि ऊपर न्यूमैन का स्टेटमेंट भ्रामक है, यह राय सभी के द्वारा साझा नहीं की जाती है। मशीनों में ट्यूरिंग की आजीवन रुचि थी: एलन ने लड़के के रूप में टाइपराइटर का आविष्कार करने का सपना देखा था; [उनकी मां] श्रीमती ट्यूरिंग के पास टाइपराइटर था; और वह अच्छी तरह से स्वयं से पूछकर प्रारंभ कर सकता था कि टाइपराइटर को 'मैकेनिकल' कहने का क्या अर्थ है (होजेस पी. 96)। प्रिंसटन में अपनी पीएचडी की पढ़ाई के समय , ट्यूरिंग ने बूलियन-लॉजिक मल्टीप्लायर बनाया (नीचे देखें)। उनकी पीएचडी थीसिस, जिसका शीर्षक ऑर्डिनल्स पर आधारित लॉजिक सिस्टम्स है, में संगणनीय कार्य की निम्नलिखित परिभाषा सम्मिलित है:

ऊपर कहा गया था कि 'कोई फ़ंक्शन प्रभावी रूप से गणना योग्य होता है यदि उसके मान किसी विशुद्ध यांत्रिक प्रक्रिया द्वारा पाए जा सकते हैं।' हम इस कथन को शाब्दिक रूप से ले सकते हैं, इसे पूर्ण रूप से यांत्रिक प्रक्रिया से समझ सकते हैं जिसे एक मशीन द्वारा किया जा सकता है। इन मशीनों की संरचनाओं का एक निश्चित सामान्य रूप में गणितीय विवरण देना संभव है। इन विचारों के विकास से लेखक को एक संगणनीय फ़ंक्शन की परिभाषा मिलती है, और प्रभावी गणना के साथ संगणनीयता की पहचान होती है। यह प्रमाणित करना कठिन नहीं है, चूंकि कुछ सीमा तक श्रमसाध्य है कि ये तीन परिभाषाएँ [तृतीय λ-कैलकुलस है] समतुल्य हैं.
— ट्यूरिंग (1939) द अनडिसीडेबल में, पृ. 160

एलन ट्यूरिंग ने 1936 में ए-मशीन (स्वचालित मशीन) का आविष्कार किया।^[7] ट्यूरिंग ने अपना पेपर 31 मई 1936 को लंदन मैथमेटिकल सोसाइटी फॉर इट्स प्रोसीडिंग्स (cf. हॉजेस 1983: 112) को प्रस्तुत किया, किन्तु यह 1937 की प्रारंभ में प्रकाशित हुआ था और ऑफप्रिंट फरवरी 1937 में उपलब्ध थे (cf. हॉजेस 1983: 129) यह ट्यूरिंग का था डॉक्टरेट सलाहकार, अलोंजो चर्च, जिन्होंने बाद में समीक्षा में ट्यूरिंग मशीन शब्द गढ़ा था।^[20] इस मॉडल के साथ, ट्यूरिंग नकारात्मक में दो प्रश्नों का उत्तर देने में सक्षम था:

क्या कोई मशीन उपस्तिथ है जो यह निर्धारित कर सकती है कि उसके टेप पर कोई अर्बिटरी मशीन वृत्ताकार है (उदाहरण के लिए, फ्रीज, या उसके कम्प्यूटेशनल कार्य को प्रवाहित रखने में विफल)?
क्या कोई मशीन उपस्तिथ है जो यह निर्धारित कर सकती है कि उसके टेप पर कोई अर्बिटरी मशीन कभी किसी दिए गए सिम्बल्स को प्रिंट करती है या नहीं?^[21]^[22]

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

जब ट्यूरिंग यूके लौटे तो अंततः वे एनिग्मा नामक एन्क्रिप्शन मशीनों द्वारा बनाए गए जर्मन गुप्त कोड को तोड़ने के लिए संयुक्त रूप से उत्तरदायी हो गए; वह एसीई (स्वचालित कंप्यूटिंग इंजन) के डिजाइन में भी सम्मिलित हो गया है, [ट्यूरिंग] एसीई प्रस्ताव प्रभावी रूप से आत्मनिर्भर था, और इसकी जड़ें ईडीवीएसी [यूएसए की पहल] में नहीं थीं, किन्तु अपनी सार्वभौमिक मशीन (होजेस पी) में थीं। . 318)। क्लेन (1952) ट्यूरिंग की थीसिस द्वारा जो नाम दिया गया है, उसकी उत्पत्ति और प्रकृति के संबंध में लॉजिक अभी भी प्रवाहित हैं। किन्तु ट्यूरिंग ने अपने कम्प्यूटेशनल-मशीन मॉडल के साथ जो प्रमाणित किया, वह उनके पेपर ऑन कंप्यूटेबल नंबर्स में एप्लीकेशन टू द एंट्सचिडंगस्प्रोब्लेम (1937) के साथ दिखाई देता है:

[कि] हिल्बर्ट एंट्सचीडुंग्सप्रॉब्लम का कोई समाधान नहीं हो सकता है... इसलिए मैं यह दिखाने का प्रस्ताव करता हूं कि यह निर्धारित करने के लिए कोई सामान्य प्रक्रिया नहीं हो सकती है कि क्या कार्यात्मक कैलकुलस K का दिया गया सूत्र U सिद्ध करने योग्य है, अर्थात कि ऐसी कोई मशीन नहीं हो सकती है, जो, इन सूत्रों में से किसी एक U के साथ प्रदान किया गया, अंततः बताएगा कि क्या U सिद्ध करने योग्य है.
— द अनडिसीडेबल में पुनर्मुद्रित ट्यूरिंग के पेपर से, पृ. 145

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

1937-1970: डिजिटल कंप्यूटर, कंप्यूटर विज्ञान का जन्म

इस प्रकार से 1937 में, प्रिंसटन में अपनी पीएचडी थीसिस पर कार्य करते हुए, ट्यूरिंग ने स्क्रैच से डिजिटल (बूलियन-लॉजिक) मल्टीप्लायर बनाया है, जिससे अपना स्वयं का इलेक्ट्रोमैकेनिकल रिले (होजेस पृष्ठ 138) बना है। एलन का कार्य रिले-संचालित स्विचों के नेटवर्क में ट्यूरिंग मशीन के तार्किक डिजाइन को मूर्त रूप देना था ... (होजेस पी। 138)। जबकि ट्यूरिंग प्रारंभ में जिज्ञासु और प्रयोग करने वाला हो सकता था, उसी दिशा में जर्मनी (कोनराड ज़्यूस (1938)), और संयुक्त स्टेट अमेरिका (हावर्ड ऐकेन) और जॉर्ज स्टिबिट्ज़ (1937) में अधिक निष्कपट से कार्य चल रहा था; द्वितीय विश्व युद्ध में एक्सिस और मित्र देशों की सेनाओं द्वारा उनके मजदूरों के फलों का उपयोग किया गया था (cf. हॉजेस पृष्ठ 298-299)। 1950 के दशक के मध्य में हाओ वांग (अकादमिक) और मार्विन मिंस्की ने ट्यूरिंग मशीन को सरल रूप में कम कर दिया (मार्टिन डेविस (गणितज्ञ) की पोस्ट-ट्यूरिंग मशीन का अग्रदूत); साथ ही साथ यूरोपीय शोधकर्ता नए-फंसे हुए इलेक्ट्रॉनिक कंप्यूटर को कंप्यूटर जैसी सैद्धांतिक वस्तु के समान बना रहे थे जिसे अब ट्यूरिंग मशीन कहा जा रहा है। और 1950 के दशक के अंत और 1960 के दशक के प्रारंभ में, संयोग से मेलज़क और लैम्बेक (1961), मिन्स्की (1961), और शेफर्डसन और स्टर्गिस (1961) के समानांतर विकास ने यूरोपीय कार्य को आगे बढ़ाया और ट्यूरिंग मशीन को अधिक अनुकूल, कंप्यूटर की तरह कम कर दिया। सार मॉडल जिसे काउंटर मशीन कहा जाता है; एलगोट और रॉबिन्सन (1964), हार्टमैनिस (1971), कुक और रेक्हो (1973) ने रजिस्टर मशीन और रैंडम-एक्सेस मशीन मॉडल के साथ इस कार्य को और आगे बढ़ाया- किन्तु मूल रूप से सभी अंकगणितीय निर्देश वाली मल्टी-टेप ट्यूरिंग मशीन तय करना हैं।

1970-वर्तमान: गणना के मॉडल के रूप में

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

वस्तुओं के आधार पर कोई व्यक्ति गणनाओं में परिवर्तन करना पसंद करता है (गैर-नकारात्मक पूर्णांक जैसी संख्याएँ)।या अल्फ़ान्यूमेरिक स्ट्रिंग्स), दो मॉडलों ने मशीन-आधारित सम्मिश्र सिद्धांत में एक प्रमुख स्थान प्राप्त किया है:
ऑफ-लाइन मल्टीटेप ट्यूरिंग मशीन..., जो स्ट्रिंग-उन्मुख गणना के लिए मानक मॉडल का प्रतिनिधित्व करती है, और रैंडम एक्सेस मशीन (रैम) जैसा कि कुक और रेकहो द्वारा प्रस्तुत किया गया..., जो आदर्श वॉन न्यूमैन-शैली के कंप्यूटर का मॉडल है.
— एम्डे बोस 1990:4 से

केवल एल्गोरिदम के विश्लेषण के संबंधित क्षेत्र में यह भूमिका रैम मॉडल द्वारा ली जाती है.
— एम्डे बोस 1990:16 से

यह भी देखें

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

↑ Minsky 1967:107 "In his 1936 paper, A. M. Turing defined the class of abstract machines that now bear his name. A Turing machine is a finite-state machine associated with a special kind of environment -- its tape -- in which it can store (and later recover) sequences of symbols," also Stone 1972:8 where the word "machine" is in quotation marks.
↑ Stone 1972:8 states "This "machine" is an abstract mathematical model", also cf. Sipser 2006:137ff that describes the "Turing machine model". Rogers 1987 (1967):13 refers to "Turing's characterization", Boolos Burgess and Jeffrey 2002:25 refers to a "specific kind of idealized machine".
↑ Sipser 2006:137 "A Turing machine can do everything that a real computer can do".
↑ Cf. Sipser 2002:137. Also, Rogers 1987 (1967):13 describes "a paper tape of infinite length in both directions". Minsky 1967:118 states "The tape is regarded as infinite in both directions". Boolos Burgess and Jeffrey 2002:25 include the possibility of "there is someone stationed at each end to add extra blank squares as needed".
↑ Cf. Rogers 1987 (1967):13. Other authors use the word "square" e.g. Boolos Burgess Jeffrey 2002:35, Minsky 1967:117, Penrose 1989:37.
↑ Boolos Burgess Jeffry 2002:25 illustrate the machine as moving along the tape. Penrose 1989:36-37 describes himself as "uncomfortable" with an infinite tape observing that it "might be hard to shift!"; he "prefer[s] to think of the tape as representing some external environment through which our finite device can move" and after observing that the " 'movement' is a convenient way of picturing things" and then suggests that "the device receives all its input from this environment. Some variations of the Turing machine model also allow the head to stay in the same position instead of moving or halting.
↑ ^7.0 ^7.1 Hodges, Andrew (2012). Alan Turing: The Enigma (The Centenary ed.). Princeton University Press. ISBN 978-0-691-15564-7.
↑ The idea came to him in mid-1935 (perhaps, see more in the History section) after a question posed by M. H. A. Newman in his lectures: "Was there a definite method, or as Newman put it, a "mechanical process" which could be applied to a mathematical statement, and which would come up with the answer as to whether it was provable" (Hodges 1983:93). Turing submitted his paper on 31 May 1936 to the London Mathematical Society for its Proceedings (cf. Hodges 1983:112), but it was published in early 1937 and offprints were available in February 1937 (cf. Hodges 1983:129).
↑ See footnote in Davis 2000:151.
↑ see note in forward to The Collected Works of Alonzo Church (Burge, Tyler; Enderton, Herbert, eds. (2019-04-23). The Collected Works of Alonzo Church (in English). Cambridge, MA, USA: MIT Press. ISBN 978-0-262-02564-5.)
↑ Turing 1936 in The Undecidable 1965:132-134; Turing's definition of "circular" is found on page 119.
↑ Turing, Alan Mathison (1937). "On Computable Numbers, with an Application to the Entscheidungsproblem". Proceedings of the London Mathematical Society. Series 2. 42 (1): 230–265. doi:10.1112/plms/s2-42.1.230. S2CID 73712. — Reprint at: Turing, Alan. "On computable numbers, with an application to the Entscheidungsproblem". The Turing Digital Archive. Retrieved 9 July 2020.
↑ Turing 1936 in The Undecidable 1965:145
↑ Sipser 2006:137 observes that "A Turing machine can do everything that a real computer can do. Nevertheless, even a Turing machine cannot solve certain problems. In a very real sense, these problems are beyond the theoretical limits of computation."
↑ See the definition of "innings" on Wiktionary
↑ A.M. Turing (Jul 1948). Intelligent Machinery (Report). National Physical Laboratory. Here: p.3-4
↑ Occasionally called an action table or transition function.
↑ Usually quintuples [5-tuples]: q_ia_j→q_i1a_j1d_k, but sometimes quadruples [4-tuples].
↑ p.149; in particular, Hopcroft and Ullman assume that $\delta$ is undefined on all states from $F$
↑ see note in forward to The Collected Works of Alonzo Church (Burge, Tyler; Enderton, Herbert, eds. (2019-04-23). The Collected Works of Alonzo Church (in English). Cambridge, MA, USA: MIT Press. ISBN 978-0-262-02564-5.)
↑ Turing 1936 in The Undecidable 1965:132-134; Turing's definition of "circular" is found on page 119.
↑ Turing, Alan Mathison (1937). "On Computable Numbers, with an Application to the Entscheidungsproblem". Proceedings of the London Mathematical Society. Series 2. 42 (1): 230–265. doi:10.1112/plms/s2-42.1.230. S2CID 73712. — Reprint at: Turing, Alan. "On computable numbers, with an application to the Entscheidungsproblem". The Turing Digital Archive. Retrieved 9 July 2020.
↑ Turing 1936 in The Undecidable 1965:145

संदर्भ

प्राथमिक साहित्य, पुनर्मुद्रण और संकलन

बी जैक कोपलैंड एड। (2004), द एसेंशियल ट्यूरिंग: सेमिनल राइटिंग्स इन कम्प्यूटिंग, लॉजिक, फिलॉसफी, आर्टिफिशियल इंटेलिजेंस, एंड आर्टिफिशियल लाइफ प्लस द सीक्रेट्स ऑफ एनिग्मा, क्लेरेंडन प्रेस (ऑक्सफोर्ड यूनिवर्सिटी प्रेस), ऑक्सफोर्ड यूके, ISBN 0-19-825079-7. ट्यूरिंग पेपर्स के साथ-साथ एमिल पोस्ट को ट्यूरिंग के सम्मेलन की उनकी आलोचना, और ट्यूरिंग की यूनिवर्सल कंप्यूटिंग मशीन के लिए डोनाल्ड डब्ल्यू डेविस के सुधारों के लिए मसौदा पत्र सम्मिलित है
मार्टिन डेविस (गणितज्ञ) (संपा.) (1965), द अनडिसीडेबल, रेवेन प्रेस, हेवलेट, एनवाई।
एमिल पोस्ट (1936), फाइनाइट कॉम्बिनेटरी प्रोसेसेस-फॉर्मूलेशन 1, जर्नल ऑफ़ सिंबॉलिक लॉजिक, 1, 103-105, 1936।
एमिल पोस्ट (1947), रिकर्सिव अनसॉल्वेबिलिटी ऑफ़ ए प्रॉब्लम ऑफ़ थू, जर्नल ऑफ़ सिंबॉलिक लॉजिक, वॉल्यूम। 12, पीपी। 1-11। द अनडिसीडेबल में पुनर्मुद्रित, पीपी. 293ff। इस पेपर के परिशिष्ट में टिप्पणी पोस्ट करें और ट्यूरिंग के 1936-1937 के पेपर में सुधार करें। विशेष रूप से फ़ुटनोट्स 11 को यूनिवर्सल कंप्यूटिंग मशीन कोडिंग में सुधार के साथ और फ़ुटनोट 14 को ट्यूरिंग के प्रमाण पर टिप्पणी के साथ देखें। ट्यूरिंग का पहला और दूसरा प्रमाण।
Turing, A.M. (1936). "कम्प्यूटेबल नंबरों पर, Entscheidungsproblem के लिए एक एप्लिकेशन के साथ". Proceedings of the London Mathematical Society. 2 (published 1937). 42: 230–265. doi:10.1112/plms/s2-42.1.230. S2CID 73712. (और Turing, A.M. (1938). "Entscheidungsproblem के लिए एक आवेदन के साथ कम्प्यूटेबल नंबरों पर: एक सुधार". Proceedings of the London Mathematical Society. 2 (published 1937). 43 (6): 544–6. doi:10.1112/plms/s2-43.6.544.). अनेक संग्रहों में पुनर्मुद्रित, उदा। द अनडिसीडेबल में, पीपी. 115–154; वेब पर अनेक जगहों पर उपलब्ध है।
एलन ट्यूरिंग, 1948, इंटेलिजेंट मशीनरी। साइबरनेटिक्स में पुनर्मुद्रित: प्रमुख कागजात। ईडी। सी.आर. इवांस और ए.डी.जे. रॉबर्टसन। बाल्टीमोर: यूनिवर्सिटी पार्क प्रेस, 1968. पी। 31. में पुनर्मुद्रित Turing, A. M. (1996). "इंटेलिजेंट मशीनरी, ए हेरेटिकल थ्योरी". Philosophia Mathematica. 4 (3): 256–260. doi:10.1093/philmat/4.3.256.
एफ. सी. हेनी और आर. ई. स्टर्न्स। मल्टीटेप ट्यूरिंग मशीनों का दो-टेप सिमुलेशन। जेएसीएम, 13(4):533–546, 1966।

अकंप्यूटेबिलिटी सिद्धांत

Boolos, George; Richard Jeffrey (1999) [1989]. संगणना और तर्क (3rd ed.). Cambridge UK: Cambridge University Press. ISBN 0-521-20402-X.
Boolos, George; John Burgess; Richard Jeffrey (2002). संगणना और तर्क (4th ed.). Cambridge UK: Cambridge University Press. ISBN 0-521-00758-5. बर्गेस द्वारा कुछ हिस्सों को महत्वपूर्ण रूप से फिर से लिखा गया है। लैम्बेक अबैकस मशीन (cf. रजिस्टर मशीन) और संगणनीय समारोह के संदर्भ में ट्यूरिंग मशीनों की प्रस्तुति, उनकी समानता दर्शाती है।
टेलर एल बूथ (1967), अनुक्रमिक मशीनें और ऑटोमेटा थ्योरी, जॉन विली एंड संस, इंक, न्यूयॉर्क। स्नातक स्तर का इंजीनियरिंग पाठ; विषयों की विस्तृत विविधता से अधिक है, अध्याय IX ट्यूरिंग मशीन में कुछ पुनरावर्तन सिद्धांत सम्मिलित हैं।
Martin Davis (1958). संगणनीयता और अघुलनशीलता. McGraw-Hill Book Company, Inc, New York.. पृष्ठ 12-20 पर वह जोड़, उत्तरवर्ती फलन, घटाव (x ≥ y), उचित घटाव (0 यदि x < y), पहचान फलन और विभिन्न पहचान फलन, और गुणन के लिए 5-ट्यूपल टेबल ओं का उदाहरण देता है।
Davis, Martin; Ron Sigal; Elaine J. Weyuker (1994). संगणनीयता, जटिलता, और भाषाएँ और तर्क: सैद्धांतिक कंप्यूटर विज्ञान के मूल तत्व (2nd ed.). San Diego: Academic Press, Harcourt, Brace & Company. ISBN 0-12-206382-1.
Hennie, Fredrick (1977). कम्प्यूटेबिलिटी का परिचय. Addison–Wesley, Reading, Mass. QA248.5H4 1977.. 90-103 पृष्ठों पर हेनी उदाहरणों और प्रवाह-चार्ट के साथ यूटीएम की चर्चा करती है, किन्तु कोई रियल 'कोड' नहीं है।
John Hopcroft and Jeffrey Ullman (1979). ऑटोमेटा सिद्धांत, भाषाएं और संगणना का परिचय (1st ed.). Addison–Wesley, Reading Mass. ISBN 0-201-02988-X. लैंग्वेज की मशीन-व्याख्या, एनपी-पूर्णता, आदि के मुद्दों पर केंद्रित है।
Hopcroft, John E.; Rajeev Motwani; Jeffrey D. Ullman (2001). ऑटोमेटा सिद्धांत, भाषाएं और संगणना का परिचय (2nd ed.). Reading Mass: Addison–Wesley. ISBN 0-201-44124-1.
स्टीफन क्लेन (1952), मेटामैथमैटिक्स का परिचय, नॉर्थ-हॉलैंड पब्लिशिंग कंपनी, एम्स्टर्डम नीदरलैंड्स, 10वीं छाप (6वें पुनर्मुद्रण 1971 के सुधार के साथ)। स्नातक स्तर का पाठ; अध्याय XIII के अधिकांश संगणनीय कार्य पुनरावर्ती कार्यों की कंप्यूटर के ट्यूरिंग मशीन प्रमाणों आदि पर हैं।
Knuth, Donald E. (1973). खंड 1/मौलिक एल्गोरिदम: कंप्यूटर प्रोग्रामिंग की कला (2nd ed.). Reading, Mass.: Addison–Wesley Publishing Company.. कम्प्यूटेशन (हार्डवेयर और सॉफ्टवेयर दोनों) के विकास में ट्यूरिंग मशीनों की भूमिका के संदर्भ में 1.4.5 इतिहास और ग्रंथ सूची पीपी। 225ff और 2.6 इतिहास और ग्रंथ सूची पीपी देखें। 456फ।
जौहर मन्ना, 1974, कंप्यूटर का गणितीय सिद्धांत। पुनर्मुद्रित, डोवर, 2003। ISBN 978-0-486-43238-0
मार्विन मिन्स्की, कम्प्यूटेशन: परिमित और अनंत मशीनें, प्रेंटिस-हॉल, इंक।, एन.जे., 1967। अध्याय 8 देखें, खंड 8.2 रुकने की समस्या का समाधान नहीं।
Christos Papadimitriou (1993). अभिकलनात्मक जटिलता (1st ed.). Addison Wesley. ISBN 0-201-53082-1. अध्याय 2: ट्यूरिंग मशीन, पीपी। 19–56।
हार्टले रोजर्स, जूनियर, पुनरावर्ती कार्यों और प्रभावी अकंप्यूटेबिलिटी का सिद्धांत, एमआईटी प्रेस, कैम्ब्रिज एमए, पेपरबैक संस्करण 1987, मूल मैकग्रा-हिल संस्करण 1967, ISBN 0-262-68052-1 (पीबीके।)
Michael Sipser (1997). संगणना के सिद्धांत का परिचय. PWS Publishing. ISBN 0-534-94728-X. अध्याय 3: चर्च-ट्यूरिंग थीसिस, पीपी। 125-149।
Stone, Harold S. (1972). कंप्यूटर संगठन और डेटा संरचनाओं का परिचय (1st ed.). New York: McGraw–Hill Book Company. ISBN 0-07-061726-0.
पीटर वैन एम्डे बोस 1990, मशीन मॉडल और सिमुलेशन, पीपी। 3–66, जॉन वैन लीउवेन में, एड।, सैद्धांतिक कंप्यूटर विज्ञान की हैंडबुक, वॉल्यूम ए: एल्गोरिदम और सम्मिश्र , एमआईटी प्रेस/एल्सेवियर, [स्थान?], ISBN 0-444-88071-2 (वॉल्यूम ए)। QA76.H279 1990।

चर्च की थीसिस

Nachum Dershowitz; Yuri Gurevich (September 2008). "कम्प्यूटेबिलिटी और चर्च की थीसिस के प्रमाण का एक प्राकृतिक स्वयंसिद्ध" (PDF). Bulletin of Symbolic Logic. 14 (3). Retrieved 2008-10-15.
Roger Penrose (1990) [1989]. सम्राट का नया मन (2nd ed.). Oxford University Press, New York. ISBN 0-19-851973-7.

छोटी ट्यूरिंग मशीनें

रोगोज़िन, यूरी, 1998, 22 स्टेटों और 2 के साथ यूनिवर्सल ट्यूरिंग मशीन सिम्बल्सों, सूचना विज्ञान और प्रौद्योगिकी के रोमानियाई जर्नल, 1(3), 259–265, 1998. (छोटे सार्वभौमिक ट्यूरिंग मशीनों के बारे में ज्ञात परिणामों का सर्वेक्षण)
स्टीफन वोल्फ्राम, 2002, विज्ञान का नया प्रकार, वोल्फ्राम मीडिया, ISBN 1-57955-008-8
ब्रुनफिल, ज्योफ, स्टूडेंट स्नैग मैथ्स प्राइज, नेचर, 24 अक्टूबर 2007।
जिम जाइल्स (2007), सिंपलेस्ट 'यूनिवर्सल कंप्यूटर' ने छात्र को $25,000 जीता, न्यू साइंटिस्ट, 24 अक्टूबर , 2007.
एलेक्स स्मिथ, यूनिवर्सलिटी ऑफ वोल्फ्राम 2, 3 ट्यूरिंग मशीन, वोल्फ्राम 2, 3 ट्यूरिंग मशीन रिसर्च प्राइज के लिए सबमिशन।
वॉन प्रैट, 2007, सिंपल ट्यूरिंग मशीन, यूनिवर्सलिटी, एनकोडिंग आदि , FOM ईमेल लिस्ट। 29 अक्टूबर, 2007।
मार्टिन डेविस, 2007, स्मॉलेस्ट यूनिवर्सल मशीन, और -October/012145.html यूनिवर्सल ट्यूरिंग मशीन की परिभाषा FOM ईमेल सूची। अक्टूबर 26-27, 2007।
अलास्डेयर उर्कहार्ट, 2007 सबसे छोटी यूनिवर्सल मशीन, एफओएम ईमेल सूची। 26 अक्टूबर, 2007।
हेक्टर जेनिल (वोल्फ्राम रिसर्च), 2007 सबसे छोटी यूनिवर्सल मशीन, एफओएम ईमेल सूची। 29 अक्टूबर, 2007।
टोड रोलैंड, 2007, FOM पर भ्रम, वोल्फ्राम विज्ञान संदेश बोर्ड, 30 अक्टूबर, 2007।
ओलिवियर और मार्क रेनॉड, 2014, ट्यूरिंग मशीन हासिल करने के लिए प्रोग्रामेबल प्रोटोटाइप ब्लेज़ पास्कल यूनिवर्सिटी की लिमोस लेबोरेटरी (फ्रांस में क्लेरमोंट-फेरैंड)।

अन्य

Martin Davis (2000). तर्क के इंजन: गणितज्ञ और कंप्यूटर की उत्पत्ति (1st ed.). W. W. Norton & Company, New York. ISBN 978-0-393-32229-3.
रॉबिन गैंडी, द कंफ्लुएंस ऑफ आइडियाज इन 1936, पीपी. 51–102 रॉल्फ पहचानो में, नीचे देखें।
स्टीफन हॉकिंग (संपादक), 2005, गॉड क्रिएटेड द इंटीजर: द मैथमेटिकल ब्रेकथ्रूज़ दैट चेंज्ड हिस्ट्री, रनिंग प्रेस, फिलाडेल्फिया, ISBN 978-0-7624-1922-7. हॉकिंग द्वारा लिखित ट्यूरिंग की संक्षिप्त टिप्पणी और जीवनी के साथ ट्यूरिंग का 1936-1937 का पेपर सम्मिलित है।
Rolf Herken (1995). द यूनिवर्सल ट्यूरिंग मशीन-ए हाफ-सेंचुरी सर्वे. Springer Verlag. ISBN 978-3-211-82637-9.
एंड्रयू हॉजेस, एलन ट्यूरिंग: द एनिग्मा, साइमन और शूस्टर, न्यूयॉर्क। सी एफ अध्याय द स्पिरिट ऑफ ट्रूथ ऐसे इतिहास के लिए जो उसके प्रमाण की ओर ले जाता है और उसकी चर्चा करता है।
Ivars Peterson (1988). गणितीय पर्यटक: आधुनिक गणित का स्नैपशॉट (1st ed.). W. H. Freeman and Company, New York. ISBN 978-0-7167-2064-5.
रोजर पेनरोज़, द एम्परर्स न्यू माइंड: कन्सर्निंग कंप्यूटर्स, माइंड्स एंड द लॉज़ ऑफ़ फ़िज़िक्स, ऑक्सफोर्ड यूनिवरसिटि प्रेस, ऑक्सफोर्ड एंड न्यूयॉर्क, 1989 (1990 सुधार), ISBN 0-19-851973-7.
Paul Strathern (1997). ट्यूरिंग एंड द कंप्यूटर-द बिग आइडिया. Anchor Books/Doubleday. ISBN 978-0-385-49243-0.
हाओ वांग (अकादमिक), कंप्यूटिंग मशीनों के ट्यूरिंग के सिद्धांत का प्रकार, जर्नल ऑफ़ द एसोसिएशन फॉर कंप्यूटिंग मशीनरी (JACM) 4, 63–92 (1957)।
चार्ल्स पेटज़ोल्ड, पेटज़ोल्ड, चार्ल्स, द एनोटेटेड ट्यूरिंग, जॉन विले एंड संस, इंक। ISBN 0-470-22905-5
अरोड़ा, संजीव; बराक, बोअज़, कॉम्प्लेक्सिटी थ्योरी: ए मॉडर्न अप्रोच, कैम्ब्रिज यूनिवर्सिटी प्रेस, 2009, ISBN 978-0-521-42426-4, खंड 1.4, तार के रूप में मशीनें और सार्वभौमिक ट्यूरिंग मशीन और 1.7, प्रमेय 1.9 का प्रमाण
Kantorovitz, Isaiah Pinchas (December 1, 2005). "नियम संचालित प्रणालियों की ट्यूरिंग मशीन की संगणना पर एक नोट". SIGACT News. 36 (4): 109–110. doi:10.1145/1107523.1107525. S2CID 31117713.
किरनेर, रायमुंड; ज़िम्मरमैन, वुल्फ; रिक्टर, डिर्क: चालू रियल प्रोग्रामिंग लैंग्वेज के अनिर्णीत परिणाम, 15वीं कोलोक्वियम प्रोग्रामिंग लैंग्वेज एंड फंडामेंटल ऑफ प्रोग्रामिंग (केपीएस'09) में, मारिया टैफरल, ऑस्ट्रिया, अक्टूबर। 2009

बाहरी संबंध

"Turing machine", Encyclopedia of Mathematics, EMS Press, 2001 [1994]
Turing Machine – Stanford Encyclopedia of Philosophy
Turing Machine Causal Networks by Enrique Zeleny as part of the Wolfram Demonstrations Project.
Turing Machines at Curlie

[1] Minsky 1967:107 "In his 1936 paper, A. M. Turing defined the class of abstract machines that now bear his name. A Turing machine is a finite-state machine associated with a special kind of environment -- its tape -- in which it can store (and later recover) sequences of symbols," also Stone 1972:8 where the word "machine" is in quotation marks.

[2] Stone 1972:8 states "This "machine" is an abstract mathematical model", also cf. Sipser 2006:137ff that describes the "Turing machine model". Rogers 1987 (1967):13 refers to "Turing's characterization", Boolos Burgess and Jeffrey 2002:25 refers to a "specific kind of idealized machine".

[3] Sipser 2006:137 "A Turing machine can do everything that a real computer can do".

[4] Cf. Sipser 2002:137. Also, Rogers 1987 (1967):13 describes "a paper tape of infinite length in both directions". Minsky 1967:118 states "The tape is regarded as infinite in both directions". Boolos Burgess and Jeffrey 2002:25 include the possibility of "there is someone stationed at each end to add extra blank squares as needed".

[5] Cf. Rogers 1987 (1967):13. Other authors use the word "square" e.g. Boolos Burgess Jeffrey 2002:35, Minsky 1967:117, Penrose 1989:37.

[6] Boolos Burgess Jeffry 2002:25 illustrate the machine as moving along the tape. Penrose 1989:36-37 describes himself as "uncomfortable" with an infinite tape observing that it "might be hard to shift!"; he "prefer[s] to think of the tape as representing some external environment through which our finite device can move" and after observing that the " 'movement' is a convenient way of picturing things" and then suggests that "the device receives all its input from this environment. Some variations of the Turing machine model also allow the head to stay in the same position instead of moving or halting.

[Hodges-2012-7] 7.0 ^7.1 Hodges, Andrew (2012). Alan Turing: The Enigma (The Centenary ed.). Princeton University Press. ISBN 978-0-691-15564-7.

[8] The idea came to him in mid-1935 (perhaps, see more in the History section) after a question posed by M. H. A. Newman in his lectures: "Was there a definite method, or as Newman put it, a "mechanical process" which could be applied to a mathematical statement, and which would come up with the answer as to whether it was provable" (Hodges 1983:93). Turing submitted his paper on 31 May 1936 to the London Mathematical Society for its Proceedings (cf. Hodges 1983:112), but it was published in early 1937 and offprints were available in February 1937 (cf. Hodges 1983:129).

[9] See footnote in Davis 2000:151.

[10] see note in forward to The Collected Works of Alonzo Church (Burge, Tyler; Enderton, Herbert, eds. (2019-04-23). The Collected Works of Alonzo Church (in English). Cambridge, MA, USA: MIT Press. ISBN 978-0-262-02564-5.)

[11] Turing 1936 in The Undecidable 1965:132-134; Turing's definition of "circular" is found on page 119.

[12] Turing, Alan Mathison (1937). "On Computable Numbers, with an Application to the Entscheidungsproblem". Proceedings of the London Mathematical Society. Series 2. 42 (1): 230–265. doi:10.1112/plms/s2-42.1.230. S2CID 73712. — Reprint at: Turing, Alan. "On computable numbers, with an application to the Entscheidungsproblem". The Turing Digital Archive. Retrieved 9 July 2020.

[13] Turing 1936 in The Undecidable 1965:145

[14] Sipser 2006:137 observes that "A Turing machine can do everything that a real computer can do. Nevertheless, even a Turing machine cannot solve certain problems. In a very real sense, these problems are beyond the theoretical limits of computation."

[15] See the definition of "innings" on Wiktionary

[16] A.M. Turing (Jul 1948). Intelligent Machinery (Report). National Physical Laboratory. Here: p.3-4

[17] Occasionally called an action table or transition function.

[18] Usually quintuples [5-tuples]: q_ia_j→q_i1a_j1d_k, but sometimes quadruples [4-tuples].

[19] .149; in particular, Hopcroft and Ullman assume that $\delta$ is undefined on all states from $F$

[20] see note in forward to The Collected Works of Alonzo Church (Burge, Tyler; Enderton, Herbert, eds. (2019-04-23). The Collected Works of Alonzo Church (in English). Cambridge, MA, USA: MIT Press. ISBN 978-0-262-02564-5.)

[21] Turing 1936 in The Undecidable 1965:132-134; Turing's definition of "circular" is found on page 119.

[22] Turing, Alan Mathison (1937). "On Computable Numbers, with an Application to the Entscheidungsproblem". Proceedings of the London Mathematical Society. Series 2. 42 (1): 230–265. doi:10.1112/plms/s2-42.1.230. S2CID 73712. — Reprint at: Turing, Alan. "On computable numbers, with an application to the Entscheidungsproblem". The Turing Digital Archive. Retrieved 9 July 2020.

[23] Turing 1936 in The Undecidable 1965:145

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

Anonymous

Search