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

सबसे पहले, हम उस पृष्ठ पर पहुँचते हैं, जिसे वास्तव में "ट्यूरिंग मशीन" कहा जाता है।

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

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

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

ट्यूरिंग मशीन की संरचना में दोनों दिशाओं में अनंत शामिल हैं फीता, कोशिकाओं में विभाजित, और नियंत्रण उपकरणराज्यों की एक सीमित संख्या के साथ.

नियंत्रण उपकरण टेप के साथ बाएँ और दाएँ घूम सकता है, कोशिकाओं में कुछ परिमित वर्णमाला के वर्णों को पढ़ और लिख सकता है। एक विशेष खालीएक प्रतीक जो टेप की सभी कोशिकाओं को भरता है, उनमें से (एक सीमित संख्या) को छोड़कर, जिस पर इनपुट डेटा रिकॉर्ड किया जाता है।

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

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

तो, ट्यूरिंग मशीन एक गणितीय अमूर्तता है, मानव मस्तिष्क का एक सट्टा निर्माण है: यह प्रकृति में मौजूद नहीं है। या वहाँ है? तुरंत दिमाग में आता है कि एक जीवित कोशिका कैसे काम करती है। कम से कम दो उदाहरण.

1. एक जटिल एंजाइम - आरएनए पोलीमरेज़ - की मदद से कोशिका में प्रोटीन के उत्पादन के लिए डीएनए से जानकारी पढ़ी जाती है, जो ट्यूरिंग मशीन का एक प्रकार का सूचना टेप है। यहां, हालांकि, टेप की कोशिकाओं को ओवरराइट नहीं किया गया है, लेकिन अन्यथा प्रक्रिया बहुत समान है: आरएनए पोलीमरेज़ डीएनए पर बैठता है और इसके साथ एक दिशा में चलता है, जबकि यह आरएनए के एक स्ट्रैंड को संश्लेषित करता है - डीएनए के समान एक न्यूक्लिक एसिड। तैयार आरएनए, एंजाइम से अलग होकर, सेलुलर ऑर्गेनेल तक जानकारी पहुंचाता है जिसमें प्रोटीन का उत्पादन होता है।

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

ऐसी सादृश्यता कोई नई बात नहीं है, और विकिपीडिया पर इसका वर्णन "आणविक कंप्यूटर" लेख में भी किया गया है:

आणविक कंप्यूटर

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

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

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

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

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

राज्य मशीन

सार ऑटोमेटा अपने आप में एक मॉडल के रूप में और ट्यूरिंग मशीनों, पुश-डाउन ऑटोमेटा, परिमित ऑटोमेटा और अन्य सूचना कनवर्टर्स के मुख्य घटक के रूप में असतत मॉडल का एक मौलिक वर्ग बनाता है।

प्रत्येक परिभाषा के साथ, हम शुद्ध गणित के दायरे में अधिकाधिक प्रवेश करते हैं। भाषा सख्त हो जाती है, गणितीय प्रतीकों से युक्त औपचारिक परिभाषाएँ सामने आती हैं। यदि हम आगे बढ़ें, तो हम एल्गोरिदम के सिद्धांत और कम्प्यूटेबिलिटी के सिद्धांत पर आएंगे। आप लंबे समय तक विकिपीडिया के पन्नों पर यात्रा कर सकते हैं, लेकिन यदि आप सिद्धांतों और परिभाषाओं के रेगिस्तान में भटकते हैं, या कम से कम गणित की पाठ्यपुस्तकों के विश्वसनीय लिंक, उदाहरण के लिए http://, तो पानी और भोजन का स्टॉक करना बेहतर है। www.mccme.ru/free-books/, या पत्रिका "पोटेंशियल" के लेख;)

उम्मीद है, इस स्पष्टीकरण के बाद, यह आपके लिए थोड़ा स्पष्ट हो गया होगा कि ट्यूरिंग मशीन वास्तव में क्या है?

आइए इस शब्द के इतिहास पर वापस जाएं।

इसलिए, जैसा कि हमने पहले ही उल्लेख किया है, एलन ट्यूरिंग ने 1937 में तथाकथित चर्च-ट्यूरिंग थीसिस में दुनिया को अपनी मशीन के बारे में बताया। एलन ट्यूरिंग के बारे में - पहले हैकर और कंप्यूटर विज्ञान के अग्रणी, जैसा कि उस होटल के स्मारक पट्टिका पर लिखा गया है जहां उनका जन्म हुआ था, लेख "एलन ट्यूरिंग" हमें बताएगा। हम यहां लेख का पूरा पाठ नहीं देंगे, लेकिन यह अपने आप में बहुत विस्तृत नहीं है।

एलन ट्यूरिंग

ट्यूरिंग, एलन मैथिसन(23 जून, 1912 - 7 जून, 1954) - अंग्रेजी गणितज्ञ, तर्कशास्त्री, क्रिप्टोग्राफर, ट्यूरिंग मशीन के आविष्कारक।

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

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

ट्यूरिंग टेस्ट

ट्यूरिंग टेस्ट- 1950 में "कंप्यूटिंग मशीनरी और इंटेलिजेंस" लेख में एलन ट्यूरिंग द्वारा प्रस्तावित एक परीक्षण यह जांचने के लिए कि क्या कंप्यूटर शब्द के मानवीय अर्थ में बुद्धिमान है।

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

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

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

ट्यूरिंग ने अपनी राय में अर्थहीन प्रश्न "क्या कोई मशीन सोच सकती है?" को प्रतिस्थापित करने के लिए एक परीक्षण का प्रस्ताव रखा। एक और अधिक विशिष्ट के लिए.

ट्यूरिंग ने भविष्यवाणी की थी कि कंप्यूटर अंततः उनकी परीक्षा में उत्तीर्ण होंगे। उनका मानना ​​था कि वर्ष 2000 तक, 5 मिनट के परीक्षण में 1 बिलियन बिट्स (लगभग 119 एमबी) की मेमोरी वाला कंप्यूटर न्यायाधीशों को 30% समय बेवकूफ बना सकता था। यह भविष्यवाणी सच नहीं हुई. (सच है, पहली लोएबनेर प्रतियोगिता में, आईबीएम पीसी 386 पर कंप्यूटर प्रोग्राम "पीसी थेरेपिस्ट" 10 में से 5 जजों को मूर्ख बनाने में कामयाब रहा, लेकिन उसने परिणाम की गणना नहीं की, और 1994 में प्रतियोगिता को और अधिक कठिन बना दिया गया।) ट्यूरिंग यह भी भविष्यवाणी की गई कि संयोजन "थिंकिंग मशीन" को ऑक्सीमोरोन नहीं माना जाएगा, और कंप्यूटर प्रशिक्षण शक्तिशाली कंप्यूटर के निर्माण में महत्वपूर्ण भूमिका निभाएगा (जिससे अधिकांश आधुनिक शोधकर्ता सहमत हैं)।

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

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

ट्यूरिंग परीक्षण में सर्वोत्तम परिणाम A.L.I.C.E कार्यक्रम द्वारा दिखाया गया। 3 बार (2000, 2001 और 2004 में) टेस्ट जीता।

लिंक

• ट्यूरिंग ए.एम. कंप्यूटिंग मशीनें और दिमाग। // इन: हॉफस्टेडर डी., डेनेट डी. द माइंड्स आई। - समारा: बहराख-एम, 2003. - एस. 47-59।
• अंग्रेजी में पुस्तक: रोजर पेनरोज़ "द एम्परर्स न्यू माइंड"।
• एलन ट्यूरिंग द्वारा लेख:
  • एलन ट्यूरिंग, कंप्यूटिंग मशीनरी और इंटेलिजेंस, माइंड, वॉल्यूम। एलआईएक्स, नहीं. 236, अक्टूबर 1950, पृ. 433-460.
  • ऑनलाइन:
• स्टैनफोर्ड इनसाइक्लोपीडिया ऑफ फिलॉसफी से ट्यूरिंग टेस्ट पर जी. ओपी और डी. डोवे का लेख (अंग्रेजी में)
• "ट्यूरिंग टेस्ट: 50 इयर्स लेटर" 2000 के दृष्टिकोण से, ट्यूरिंग टेस्ट पर 50 वर्षों के काम की समीक्षा (अंग्रेजी में)।

हम फिर से ट्यूरिंग मशीन पर लौटते हैं। एलन ट्यूरिंग के बारे में एक लेख के एक अंश में, यह कहा गया है कि पहली बार ट्यूरिंग मशीन की अवधारणा को तथाकथित के हिस्से के रूप में प्रस्तावित किया गया था। चर्च-ट्यूरिंग थीसिस:

विकिपीडिया लेख "एलन ट्यूरिंग" से अंश

कोई भी सहज रूप से गणना योग्य फ़ंक्शन आंशिक रूप से गणना योग्य है, या, समकक्ष, कुछ ट्यूरिंग मशीन द्वारा गणना की जा सकती है।

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

"द चर्च-ट्यूरिंग थीसिस" नामक लेख में वे उसके बारे में इस प्रकार लिखते हैं:

चर्च-ट्यूरिंग थीसिस

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

अपने सबसे सामान्य रूप में, यह बताता है कि कोई भी सहज रूप से गणना योग्य फ़ंक्शन आंशिक रूप से गणना योग्य है, या, समकक्ष, कुछ ट्यूरिंग मशीन द्वारा गणना की जा सकती है।

चर्च-ट्यूरिंग थीसिस को सख्ती से साबित या अस्वीकृत नहीं किया जा सकता है, क्योंकि यह आंशिक रूप से गणना योग्य फ़ंक्शन की सख्ती से औपचारिक धारणा और "सहज रूप से गणना योग्य फ़ंक्शन" की अनौपचारिक धारणा के बीच "समानता" स्थापित करता है।

चर्च-ट्यूरिंग भौतिक थीसिसपढ़ता है: कोई भी फ़ंक्शन जिसकी गणना किसी भौतिक उपकरण द्वारा की जा सकती है, उसकी गणना ट्यूरिंग मशीन द्वारा की जा सकती है.

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

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

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

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

किसी भी नियतात्मक ट्यूरिंग मशीन का प्रोग्राम कुछ सीमित वर्णमाला का उपयोग करके लिखा जा सकता है जिसमें राज्य प्रतीक, कोष्ठक, तीर इत्यादि शामिल हैं; आइए इस मशीन वर्णमाला को इस प्रकार निरूपित करें Σ 1 (\displaystyle \सिग्मा _(1)). फिर यूनिवर्सल ट्यूरिंग मशीन यूवर्णमाला वाली मशीनों के एक वर्ग के लिए Σ 2 (\displaystyle \सिग्मा _(2))और कइनपुट टेप को ट्यूरिंग मशीन कहा जाता है क+1प्रवेश टेप और वर्णमाला Σ 1 ∪ Σ 2 (\displaystyle \सिग्मा _(1)\कप \सिग्मा _(2))जैसे कि यदि आप पहले आवेदन करते हैं कटेप इनपुट मान, और पर क+1तो, कुछ ट्यूरिंग मशीन का सही ढंग से लिखा गया कोड है यूवही उत्तर देगा जो वह इन इनपुट्स पर देगा एम 1 (\डिस्प्लेस्टाइल एम_(1)), या अनिश्चित काल तक चलेगा यदि एम 1 (\डिस्प्लेस्टाइल एम_(1))इस डेटा पर मत रुकें.

यूनिवर्सल ट्यूरिंग मशीन प्रमेय में कहा गया है कि ऐसी मशीन मौजूद है और अन्य मशीनों को अधिकतम द्विघात मंदी के साथ मॉडल करती है (अर्थात, यदि मूल मशीन का उत्पादन होता है टीचरण, तब सार्वभौमिक अधिकतम उत्पादन करेगा ct2). इस प्रमेय का प्रमाण रचनात्मक है (ऐसी मशीन बनाना आसान है, आपको बस इसका सावधानीपूर्वक वर्णन करने की आवश्यकता है)। यह प्रमेय 1936-37 में ट्यूरिंग द्वारा प्रस्तावित और सिद्ध किया गया था।

डेल्फ़ी प्रोग्रामिंग भाषा में सॉफ़्टवेयर कार्यान्वयन काफी सरल है। इनमें से एक कार्यान्वयन http://kleron.ucoz.ru/load/24-1-0-52 पर पाया जा सकता है। एक्सेल फ़ाइल को लोड करना और सहेजना संभव है।

गैर-नियतात्मक ट्यूरिंग मशीन

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

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

एक संभाव्य ट्यूरिंग मशीन एक गैर-नियतात्मक ट्यूरिंग मशीन के समान है, केवल एक गैर-नियतात्मक संक्रमण के बजाय, मशीन कुछ संभावनाओं के साथ विकल्पों में से एक को चुनती है।

एक वैकल्पिक परिभाषा भी है:

एक संभाव्य ट्यूरिंग मशीन एक नियतात्मक ट्यूरिंग मशीन है जिसमें यादृच्छिक बिट्स का एक अतिरिक्त हार्डवेयर स्रोत होता है, उदाहरण के लिए, किसी भी संख्या में, यह एक अलग टेप पर "ऑर्डर" और "लोड" कर सकता है और फिर सामान्य तरीके से गणना में उपयोग कर सकता है। माउंट

एल्गोरिदम का वह वर्ग जो एक संभाव्य ट्यूरिंग मशीन पर बहुपद समय में समाप्त होता है और 1/3 से कम त्रुटि के साथ प्रतिक्रिया देता है, बीपीपी वर्ग कहलाता है।

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

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

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

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

ट्यूरिंग मशीनें: परिभाषा

ट्यूरिंग मशीनदोनों दिशाओं में अनंत है फीता, वर्गों में विभाजित ( कोशिकाओं). प्रत्येक कोशिका में एक निश्चित (किसी दी गई मशीन के लिए) परिमित सेट से कुछ वर्ण शामिल हो सकते हैं वर्णक्रमयह यंत्र। वर्णमाला के प्रतीकों में से एक को हाइलाइट किया गया है और इसे "स्पेस" कहा जाता है, यह माना जाता है कि शुरू में पूरा टेप खाली है, यानी रिक्त स्थान से भरा हुआ है।

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

इस प्रकार, ट्यूरिंग मशीन को परिभाषित करने के लिए, निम्नलिखित वस्तुओं को निर्दिष्ट किया जाना चाहिए:

जंप टेबल को निम्नानुसार व्यवस्थित किया गया है: प्रत्येक जोड़ी के लिए, एक ट्रिपल दर्शाया गया है। यहां बदलाव संख्याओं -1 (बाएं), 0 (स्थान पर) और 1 (दाएं) में से एक है। इस प्रकार, संक्रमण तालिका उन जोड़ियों पर परिभाषित S x A -> S x A x (-1,0,1) प्रकार का एक फ़ंक्शन है जिसमें स्थिति अंतिम नहीं है।

यह ट्यूरिंग मशीन के व्यवहार का वर्णन करना बाकी है। हर पल कुछ न कुछ है विन्यास, जिसमें टेप की सामग्री शामिल है (औपचारिक रूप से कहें तो, टेप की सामग्री एक मनमाना मैपिंग Z -> A है), सिर की वर्तमान स्थिति (कुछ पूर्णांक) और मशीन की वर्तमान स्थिति (तत्व S)। कॉन्फ़िगरेशन का अगले में परिवर्तन प्राकृतिक नियमों के अनुसार होता है: हम तालिका में देखते हैं कि किसी दिए गए राज्य और दिए गए प्रतीक के लिए क्या करने की आवश्यकता है, यानी, हम मशीन की नई स्थिति का पता लगाते हैं, बदलते हैं निर्दिष्ट एक पर प्रतीक लगाएं, और फिर सिर को बाएँ, दाएँ घुमाएँ, या उसे उसी स्थान पर छोड़ दें। इस मामले में, यदि नया राज्य अंतिम में से एक है, तो मशीन का संचालन समाप्त हो जाता है। यह इस बात पर सहमत होना बाकी है कि हम मशीन के इनपुट पर जानकारी कैसे जमा करते हैं और उसके काम का परिणाम क्या माना जाता है। हम मान लेंगे कि मशीन की वर्णमाला में, स्थान के अलावा, अक्षर 0 और 1 (और, संभवतः, कुछ अन्य अक्षर भी) शामिल हैं। मशीन का इनपुट और आउटपुट शून्य और एक (बाइनरी शब्द) का सीमित क्रम होगा। इनपुट शब्द को एक खाली टेप पर लिखा जाता है, मशीन हेड को उसके पहले सेल में रखा जाता है, मशीन को इनिशियलाइज़ किया जाता है और चालू किया जाता है। यदि मशीन रुक जाती है, तो परिणाम एक बाइनरी शब्द होता है जिसे सिर की स्थिति से शुरू करके दाईं ओर ले जाकर पढ़ा जा सकता है (जब तक कि 0 और 1 के अलावा कोई अन्य वर्ण प्रकट न हो जाए)।

इस प्रकार, कोई भी ट्यूरिंग मशीन बाइनरी शब्दों पर कुछ आंशिक फ़ंक्शन को परिभाषित करती है। ऐसे सभी कार्यों को कॉल करना स्वाभाविक है ट्यूरिंग मशीनों पर गणना योग्य.

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

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

कैसे समझें कि कौन से परिवर्तन हानिरहित हैं और कौन से नहीं? जाहिरा तौर पर, यहां ट्यूरिंग मशीनों पर व्यावहारिक प्रोग्रामिंग के कुछ अनुभव की आवश्यकता है, कम से कम एक छोटा सा अनुभव। उसके बाद, कार्यक्रमों को पूर्ण रूप से लिखे बिना मशीन की क्षमताओं की कल्पना करना पहले से ही संभव है, लेकिन केवल अनुमानित विवरण द्वारा निर्देशित किया जा रहा है। उदाहरण के तौर पर, आइए एक ऐसी मशीन का वर्णन करें जो इनपुट शब्द को दोगुना कर देती है (यदि इनपुट शब्द X था तो XX शब्द उत्पन्न करता है)।

यदि मशीन को कोई स्थान दिखाई देता है (इनपुट शब्द खाली है), तो वह बंद हो जाती है। यदि नहीं, तो यह वर्तमान वर्ण को याद रखता है और एक चिह्न लगाता है (वर्णमाला में, वर्ण 0 और 1 के अलावा, उनके "चिह्नित संस्करण" और भी होंगे)। फिर वह दाईं ओर एक खाली सेल की ओर जाती है, जिसके बाद वह वहां याद किए गए चरित्र की एक प्रति लिखती है। फिर वह निशान तक बायीं ओर चलती है; खुद को उस निशान में दबाते हुए, पीछे हटता है और अगले पात्र को याद करता है, और इसी तरह, जब तक कि वह पूरे शब्द की नकल नहीं कर लेता।

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

थोड़े और अनुभव के साथ, आप समझ सकते हैं कि इस विवरण में पूरे शब्द की प्रतिलिपि बनाते समय स्टॉप मैकेनिज्म प्रदान न करने में त्रुटि है, क्योंकि वर्णों की प्रतियां मूल शब्द के वर्णों से भिन्न नहीं हैं। यह भी स्पष्ट है कि त्रुटि को ठीक करने के लिए विशेष वर्ण और प्रतियों के रूप में लिखना आवश्यक है, और अंतिम चरण में सभी चिह्न हटा दें।

77 . दिखाएँ कि रिवर्स फ़ंक्शन, जो किसी शब्द को पीछे की ओर फ़्लिप करता है, ट्यूरिंग मशीन पर गणना योग्य है।

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

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

ट्यूरिंग मशीन (एमटी)- अमूर्त निष्पादक (अमूर्त कंप्यूटर)। प्रस्तावित किया गया था एलन ट्यूरिंगवी 1936अवधारणा को औपचारिक बनाने के लिए कलन विधि.

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

ट्यूरिंग मशीन डिवाइस

ट्यूरिंग मशीन की संरचना में दोनों दिशाओं में अनंत शामिल हैं फीता(संभव ट्यूरिंग मशीनें जिनमें कई अनंत टेप हैं) कोशिकाओं में विभाजित हैं, और नियंत्रण उपकरणमें से एक में होने में सक्षम राज्यों का सेट. नियंत्रण उपकरण की संभावित अवस्थाओं की संख्या सीमित और सटीक दी गई है।

नियंत्रण उपकरण टेप के साथ बाएँ और दाएँ घूम सकता है, टेप कोशिकाओं में कुछ परिमित वर्णमाला के प्रतीकों को पढ़ और लिख सकता है। एक विशेष खालीएक प्रतीक जो टेप की सभी कोशिकाओं को भरता है, उनमें से (एक सीमित संख्या) को छोड़कर, जिस पर इनपुट डेटा रिकॉर्ड किया जाता है।

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

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

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

एक विशिष्ट ट्यूरिंग मशीन को वर्णमाला ए के अक्षरों के सेट, राज्यों क्यू के सेट और नियमों के सेट के तत्वों की गणना करके निर्दिष्ट किया जाता है जिसके द्वारा मशीन संचालित होती है। वे इस तरह दिखते हैं: q i a j →q i1 a j1 d k तीन विकल्प: बाईं ओर एक सेल (L), दाईं ओर एक सेल (R), जगह पर बने रहें (N))। हर संभव कॉन्फ़िगरेशन के लिए बिल्कुल एक नियम है. केवल अंतिम स्थिति के लिए कोई नियम नहीं हैं, जिसमें मशीन बंद हो जाती है। इसके अलावा, आपको अंत और प्रारंभ स्थिति, टेप पर प्रारंभिक कॉन्फ़िगरेशन और मशीन हेड का स्थान निर्दिष्ट करना होगा।

ट्यूरिंग मशीन उदाहरण

आइए संख्याओं को गुणा करने के लिए MT का एक उदाहरण दें एकात्मक संख्या प्रणाली. मशीन निम्नलिखित नियमों के अनुसार संचालित होती है:

इकाई प्रणाली में MT 3 को 2 से गुणा करें:

प्रोटोकॉल एमटी की प्रारंभिक और अंतिम स्थिति, टेप पर प्रारंभिक कॉन्फ़िगरेशन और मशीन हेड के स्थान (रेखांकित प्रतीक) को इंगित करता है।

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

मुख्य लेख: ट्यूरिंग पूर्णता

हम कह सकते हैं कि ट्यूरिंग मशीन सबसे सरल रैखिक मेमोरी कंप्यूटर है, जो औपचारिक नियमों के अनुसार, अनुक्रम का उपयोग करके इनपुट डेटा को परिवर्तित करता है प्रारंभिक क्रियाएं.

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

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

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

जैसा कि कहा गया था, ट्यूरिंग मशीन पर अन्य सभी निष्पादकों की नकल करना (संक्रमण नियम निर्धारित करके) संभव है जो किसी तरह चरण-दर-चरण गणना की प्रक्रिया को लागू करते हैं, जिसमें गणना का प्रत्येक चरण काफी प्राथमिक होता है।

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

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

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

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

अर्ध-अनंत टेप पर चलने वाली ट्यूरिंग मशीन

ऐसी कमी के उदाहरण के रूप में, निम्नलिखित प्रमेय पर विचार करें: किसी भी ट्यूरिंग मशीन के लिए, अर्ध-अनंत टेप पर चलने वाली एक समकक्ष ट्यूरिंग मशीन होती है।

यू. जी. कार्पोव द्वारा थ्योरी ऑफ ऑटोमेटा पुस्तक में दिए गए प्रमाण पर विचार करें। इस प्रमेय का प्रमाण रचनात्मक है, अर्थात, हम एक एल्गोरिथ्म देंगे जिसके द्वारा, किसी भी ट्यूरिंग मशीन के लिए, घोषित संपत्ति के साथ एक समकक्ष ट्यूरिंग मशीन का निर्माण किया जा सकता है। सबसे पहले, हम एमटी वर्किंग टेप की कोशिकाओं को मनमाने ढंग से क्रमांकित करते हैं, अर्थात, हम टेप पर जानकारी का नया स्थान निर्धारित करते हैं:

फिर हम कोशिकाओं को पुनः क्रमांकित करते हैं, और हम मान लेंगे कि प्रतीक "*" एमटी शब्दकोश में शामिल नहीं है:

अंत में, हम ट्यूरिंग मशीन को उसके राज्यों की संख्या को दोगुना करके बदलते हैं और रीड-राइट हेड की शिफ्ट को बदलते हैं ताकि राज्यों के एक समूह में मशीन का संचालन छायांकित क्षेत्र में इसके संचालन के बराबर हो, और राज्यों के दूसरे समूह में मशीन वैसे ही काम करती है जैसे मूल मशीन करती है। छाया रहित क्षेत्र में। यदि एमटी ऑपरेशन के दौरान प्रतीक '*' का सामना करना पड़ता है, तो रीड-राइट हेड ज़ोन सीमा तक पहुंच गया है:

एक नई ट्यूरिंग मशीन की प्रारंभिक स्थिति एक ज़ोन या दूसरे में सेट की जाती है, यह इस बात पर निर्भर करता है कि मूल कॉन्फ़िगरेशन में रीड-राइट हेड मूल टेप में कहाँ स्थित था। जाहिर है, सीमा मार्कर "*" के बाईं ओर टेप का उपयोग समकक्ष ट्यूरिंग मशीन में नहीं किया जाता है।

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

सरल शब्दों में सार

एक महत्वपूर्ण बिंदु की तुरंत पहचान की जानी चाहिए: ट्यूरिंग मशीन एक विशेष रूप से सट्टा उपकरण है। प्रकृति में ऐसा कुछ भी मौजूद नहीं है। कंप्यूटर मॉडल मौजूद हैं. यहां तक ​​कि सक्रिय भी. लेकिन वे मॉडल से ज्यादा कुछ नहीं हैं.

ऐसा क्यों? क्योंकि चर्चा का विषय एक अंतहीन टेप है, जिसका पूर्ण भौतिक अस्तित्व विज्ञान और प्रौद्योगिकी के विकास के इस चरण में केवल सैद्धांतिक रूप से ही संभव है।

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

यह काम किस प्रकार करता है

गतिशील भाग पाठक और लेखक है। कोई चीज़ जो कोशिकाओं की सामग्री को पढ़ सकती है, उनमें अपना कुछ लिख सकती है, और, सबसे महत्वपूर्ण बात, परिणामी परिणामों के अनुसार कार्य कर सकती है।

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

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

विभिन्न प्रकार

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

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

हम इस अराजकता में कम से कम कुछ स्पष्टता लाने का प्रयास करेंगे और चर्चा के तहत डिवाइस के वास्तविक विकल्पों पर विचार करेंगे।

1. गैर नियतात्मक- यह एक ट्यूरिंग मशीन है जो गणना के एक विशेष चरण में उत्पन्न होने वाली स्थिति के अनुसार ऊपर वर्णित कोशिकाओं के साथ टेप पर कार्य करती है। वह जहां चाहेगी, दूसरे शब्दों में कहें तो वहां चली जायेगी.
2. नियतिवादीविशिष्ट निर्देशों वाला एक. उदाहरण के लिए, यदि जिस सेल में निष्पादन ऑटोमेटन स्थित है, उसमें अक्षर A है, तो आपको अक्षर B के साथ अगले वाले पर जाना होगा, चाहे आप इसे चाहें या नहीं।
3. पूरा- सामान्य रूप से हर उस चीज़ की गणना करने में सक्षम जिसकी गणना चरण-दर-चरण संचालन द्वारा की जा सकती है। यह एक मशीन में एक मशीन का अनुकरण भी कर सकता है, एक एमुलेटर जो एल्गोरिदम के साथ किसी अन्य समान डिवाइस के संचालन का वर्णन करता है।
4. सार्वभौमिक- वह सब कुछ करने में सक्षम जो कोई भी ट्यूरिंग मशीन कर सकती है। सामान्य तौर पर, कोई भी, अभी तक आविष्कार भी नहीं हुआ है। निःसंदेह यह पूर्ण है।

व्यावहारिक लाभ

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

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

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

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

पिछले प्रकाशन:

अंतिम संपादन: 2013-04-01 10:58:05

सामग्री टैग: ,

एक सार्वभौमिक कलाकार का अध्ययन करने के लिए सिम्युलेटर

यह क्या है?

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

ट्यूरिंग मशीन में एक कैरिज (पढ़ने और लिखने वाले हेड) और कोशिकाओं में विभाजित एक अंतहीन टेप होता है। टेप के प्रत्येक सेल में किसी वर्णमाला का एक अक्षर A=(a 0 ,a 1 ,…,a N ) हो सकता है। किसी भी वर्णमाला में एक स्पेस चिन्ह होता है, जिसे 0 या Λ के रूप में दर्शाया जाता है। कमांड दर्ज करते समय, स्थान को अंडरस्कोर "_" से बदल दिया जाता है।

ट्यूरिंग मशीन एक ऑटोमेटन है जिसे एक टेबल द्वारा नियंत्रित किया जाता है। तालिका में पंक्तियाँ चयनित वर्णमाला A के प्रतीकों के अनुरूप हैं, और कॉलम ऑटोमेटन Q=(q 0 ,q 1 ,…,q M ) की स्थितियों के अनुरूप हैं। ऑपरेशन की शुरुआत में, ट्यूरिंग मशीन राज्य q 1 में है। अवस्था q 0 अंतिम अवस्था है: इसमें प्रवेश करने के बाद, ऑटोमेटन अपना काम समाप्त कर देता है।

तालिका के प्रत्येक कक्ष में कुछ प्रतीक a i और कुछ अवस्था q j के अनुरूप एक कमांड होता है जिसमें तीन भाग होते हैं:

1. वर्णमाला ए से एक अक्षर;
2. चाल की दिशा: > (दाएं),
3. नई मशीन स्थिति

समाचार

1. फालिना आई.एन.कंप्यूटर विज्ञान के स्कूल पाठ्यक्रम में विषय "ट्यूरिंग मशीन" (inf.1september.ru)।
2. मेयर आर.वी.पोस्ट और ट्यूरिंग मशीनें (komp-model.naroad.ru)।
3. पिल्शिकोव वी.एन., अब्रामोव वी.जी., विलिटोक ए.ए., हॉट आई.वी.ट्यूरिंग मशीन और मार्कोव एल्गोरिदम। समस्या समाधान, मॉस्को: मॉस्को स्टेट यूनिवर्सिटी, 2006।
4. बेकमैन आई.एन.कंप्यूटर विज्ञान। व्याख्यान 7. एल्गोरिदम (profbeckman.naroad.ru)
5. सोलोविएव ए.सूत्रों के बिना पृथक गणित (lib.rus.ec)
6. एर्शोव एस.एस.एल्गोरिदम के सिद्धांत के तत्व, चेल्याबिंस्क, एसयूएसयू का प्रकाशन केंद्र, 2009।
7. वरपाखोव्स्की एफ.एल.एल्गोरिदम के सिद्धांत के तत्व, एम: ज्ञानोदय, 1970।
8. वीरेशचागिन एन.के., शेन ए.कम्प्यूटेबल फ़ंक्शंस, एम: एमटीएसएनएमओ, 1999।

उसके साथ क्या करें?

प्रोग्राम के शीर्ष पर एक संपादक फ़ील्ड है जिसमें आप समस्या की स्थिति को निःशुल्क रूप में दर्ज कर सकते हैं।

रिबन को उसके बाएँ और दाएँ स्थित बटनों का उपयोग करके बाएँ और दाएँ घुमाया जाता है। रिबन सेल पर डबल-क्लिक करके (या उस पर राइट-क्लिक करके), आप इसकी सामग्री को बदल सकते हैं।

मेनू का उपयोग करना फीताआप टेप की स्थिति को आंतरिक बफ़र में संग्रहीत कर सकते हैं और बफ़र से टेप को पुनर्स्थापित कर सकते हैं।

खेत मेँ वर्णमालाचयनित वर्णमाला के अक्षर निर्धारित हैं। दर्ज किए गए वर्णों में स्वचालित रूप से एक स्थान जुड़ जाता है।

प्रोग्राम विंडो के नीचे तालिका में टाइप किया गया है। पहले कॉलम में वर्णमाला वर्ण होते हैं और यह स्वचालित रूप से भर जाता है। पहली पंक्ति सभी संभावित स्थितियों को सूचीबद्ध करती है। आप तालिका के ऊपर स्थित बटनों का उपयोग करके तालिका (स्थिति) कॉलम जोड़ और हटा सकते हैं।

तालिका सेल में एक कमांड दर्ज करते समय, आपको पहले एक नया वर्ण दर्ज करना होगा, फिर संक्रमण की दिशा और राज्य संख्या दर्ज करनी होगी। यदि कोई वर्ण छोड़ दिया जाता है, तो वह डिफ़ॉल्ट रूप से नहीं बदलता है। यदि राज्य संख्या छोड़ दी जाती है, तो ऑटोमेटन की स्थिति डिफ़ॉल्ट रूप से नहीं बदलती है।

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

प्रोग्राम को लगातार (F9) या चरणों में (F8) निष्पादित किया जा सकता है। अब जिस कमांड को निष्पादित किया जाएगा उसे हरे रंग की पृष्ठभूमि के साथ हाइलाइट किया गया है। निष्पादन गति मेनू के माध्यम से समायोज्य रफ़्तार.

ट्यूरिंग मशीन के कार्यों को फाइलों में संग्रहीत किया जा सकता है। कार्य की स्थिति, वर्णमाला, कार्यक्रम, टिप्पणियाँ और टेप की प्रारंभिक स्थिति सहेजी जाती है। किसी फ़ाइल से किसी कार्य को लोड करते समय और उसे फ़ाइल में सहेजते समय, टेप की स्थिति स्वचालित रूप से बफ़र पर लिखी जाती है।

यदि आपको कोई त्रुटि नज़र आती है या आपके पास सुझाव, टिप्पणियाँ, शिकायतें, अनुरोध और कथन हैं, तो लिखें।

तकनीकी आवश्यकताएं

प्रोग्राम लाइन के ऑपरेटिंग सिस्टम के अंतर्गत चलता है खिड़कियाँकिसी भी आधुनिक कंप्यूटर पर.

लाइसेंस

कार्यक्रम गैर-व्यावसायिक उपयोग के लिए निःशुल्क है। प्रोग्राम का स्रोत कोड वितरित नहीं है.

कार्यक्रम के साथ आता है जैसा है”, अर्थात्, लेखक इसके उपयोग के सभी संभावित परिणामों के लिए कोई ज़िम्मेदारी नहीं लेता है, जिसमें नैतिक और भौतिक हानि, उपकरण विफलता, शारीरिक और मानसिक चोटें शामिल हैं।

प्रोग्राम को अन्य वेबसाइटों पर रखते समय, स्रोत के लिंक की आवश्यकता होती है।

1. 1) किसी भी रूप में सामग्री प्रकाशित करना, जिसमें अन्य वेब साइटों पर सामग्री पोस्ट करना भी शामिल है;
2. 2) अपूर्ण या परिवर्तित सामग्री का वितरण;
3. 3) किसी भी मीडिया पर संग्रह में सामग्री को शामिल करना;
4. 4) सामग्री की बिक्री या अन्य उपयोग से व्यावसायिक लाभ प्राप्त करना।

सामग्री डाउनलोड करने का मतलब है कि आपने इस लाइसेंस समझौते की शर्तों को स्वीकार कर लिया है।

डाउनलोड करना

संग्रह को अनपैक करने के बाद, प्रोग्राम काम करने की स्थिति में है और उसे किसी अतिरिक्त इंस्टॉलेशन की आवश्यकता नहीं है।