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

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

Definition

एक ट्यूरिंग मशीन में अवस्थाओं का एक सीमित सेट और कोशिकाओं का एक दो-तरफा अनंत टेप होता है; प्रत्येक चरण में यह अपने सिर के नीचे के प्रतीक को पढ़ता है, एक प्रतीक लिखता है, बाएं या दाएं चलता है, और एक संक्रमण फ़ंक्शन के अनुसार स्थिति बदलता है, जब यह एक स्वीकार्य या अस्वीकार्य स्थिति में प्रवेश करता है तो रुक जाता है।

Scope

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

Core questions

• एक साधारण रीड-राइट-मूव डिवाइस एल्गोरिथम की पूरी धारणा को कैसे दर्शाता है?
• मॉडल के कई प्रकार बिल्कुल समान कार्यों की गणना क्यों करते हैं?
• एक सार्वभौमिक मशीन क्या है, और इसके अस्तित्व का क्या महत्व है?
• स्ट्रिंग के रूप में मशीनों को एन्कोड करना उनके अपने व्यवहार के बारे में प्रमाणों को कैसे सक्षम बनाता है?

Key theories

सार्वभौमिकता

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

मॉडल की सुदृढ़ता

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

Clinical relevance

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

History

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

Key figures

• Alan Turing
• Emil Post
• John von Neumann

Seminal works

• turing1937
• sipser2013

Frequently asked questions

क्या ट्यूरिंग मशीन एक वास्तविक कंप्यूटर है?

नहीं, यह असीमित टेप के साथ एक गणितीय अमूर्तता है और गति या मेमोरी लागत के लिए कोई चिंता नहीं है। इसका मूल्य वैचारिक है: यह ठीक से बताता है कि सिद्धांत रूप में क्या गणना की जा सकती है, और कोई भी कार्य जो एक वास्तविक कंप्यूटर कर सकता है, एक ट्यूरिंग मशीन भी पर्याप्त टेप और समय दिए जाने पर कर सकती है।

सार्वभौमिक ट्यूरिंग मशीन क्यों महत्वपूर्ण है?

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