ट्यूरिंग मशीन, ऑटोमेटन कार्यक्रमों के एक मॉडल के रूप में

ट्यूरिंग मशीन, ऑटोमेटन कार्यक्रमों के एक मॉडल के रूप में

1. परिचय

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

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

स्वचालित प्रोग्रामिंग की समस्याओं की चर्चा के लिए एक आधार के रूप में, हम ए। शाल्टो द्वारा हालिया व्याख्यान लेते हैं [१] और इसके "प्रोग्रामेटिक" लेख स्वचालित प्रोग्रामिंग के प्रतिमान की परिभाषा पर [२, ३]।

1. स्वचालित वस्तुएं, कार्यक्रम योजनाएं

व्याख्यान में, स्वचालित प्रोग्रामिंग की उपलब्धि स्वचालित नियंत्रण वस्तुओं की अवधारणा का परिचय है, स्वचालित नियंत्रण (TAU) के सिद्धांत से उधार लिया गया है। लेकिन, याद रखें कि ताऊ में वे इतनी वस्तुओं पर नहीं, बल्कि प्रणालियों पर विचार करते हैं, जिनके बीच निम्नलिखित प्रतिष्ठित हैं [4]:



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


चित्र 1। स्व-चालित बंदूकों के कार्यात्मक आरेख

लेकिन टीएयू की ओर क्यों मुड़ें, अगर कंप्यूटर सिस्टम डिजाइन की प्रोग्रामिंग के करीब एक अभ्यास है, जिसमें ऑपरेटिंग डिवाइस (ओएस), जो, निश्चित रूप से, एमटी शामिल हैं, को ऑपरेटिंग (ओए) और कंट्रोलिंग (यूए) मशीनों के संयोजन के रूप में माना जाता है। और यह उस चीज के करीब है जो हम अंततः के लिए प्रयास करते हैं - स्वचालित प्रोग्रामिंग की शक्ति को उचित। अंजीर में। 2 मेयरोव एस.ए., नोविकोव जी.आई द्वारा एक मोनोग्राफ से पाठ की एक स्क्रीन दिखाता है। इलेक्ट्रॉनिक कंप्यूटरों की संरचना [5], जिसमें op-amps के डिजाइन मुद्दों को काफी विस्तार से माना जाता है।


अंजीर। २। प्रबंधक और ऑपरेटिंग मशीनों की अवधारणा

लेकिन, अगर हम कंप्यूटर डिजाइन के सिद्धांत और कार्यक्रमों के सिद्धांत की तुलना करते हैं, तो उनके बीच एक स्पष्ट संरचनात्मक सादृश्य का पता लगाया जा सकता है। प्रोग्रामिंग सिद्धांत में, संरचनात्मक स्तर पर किसी भी कार्यक्रम के मॉडल को एक कार्यक्रम योजना एस = (एम, ए, सी) के रूप में दर्शाया जा सकता है, जहां एम मेमोरी तत्वों का सेट है, ए ऑपरेटरों का सेट है, सी नियंत्रण है [10]। इस दृष्टिकोण के बाद, किसी भी ट्यूरिंग मशीन कार्यक्रम को एक कार्यक्रम योजना के रूप में भी परिभाषित किया जा सकता है जिसमें सेट एम को टेप कोशिकाओं द्वारा दर्शाया जाता है, 1 के सेल से जुड़े एमटी कार्यों द्वारा ऑपरेटरों का सेट) सेल विश्लेषण, 2) टेप कोशिकाओं में बदलते वर्ण और 3) सिर को घुमाते हैं।

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

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

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

आपको यह भी याद होगा कि ट्यूरिंग मशीन को ऑटोमैटिक मैट [6] या चरम मामलों में इसका सरल विस्तार [7] माना जाता है। लेकिन आपको यह समझने की आवश्यकता है कि यह किस प्रकार का ऑटोमेटन है, यह किस प्रकार का विस्तार है, और क्या वे शास्त्रीय सूक्ष्म राज्य मशीनों के मॉडल के बराबर हैं। आइए इसे स्पष्ट करने का प्रयास करें।

2. एक स्वचालित प्रोग्रामिंग वातावरण में प्रोग्रामिंग ट्यूरिंग

अंजीर में। चित्र 3 मोनोग्राफ [8] से एमटी वेतन वृद्धि समारोह के लिए ऑटोमेटन को दर्शाता है। रूप में, यह स्पष्ट रूप से एक एमटी कार्यक्रम नहीं है, लेकिन पहले से ही एक क्लासिक परिमित राज्य मशीन नहीं है। अंजीर में। चित्र 4 में शास्त्रीय संरचनात्मक परिमित राज्य मशीन (SKA) का ग्राफ और VKPa पर्यावरण में इसका कार्यान्वयन (Qt पुस्तकालय और Qt निर्माता पर्यावरण के ढांचे में C ++ में दृश्य घटक स्वचालित प्रोग्रामिंग का वातावरण) दिखाया गया है, जो एक ही MT नियंत्रण इकाई एल्गोरिथ्म को लागू करता है।


चित्र 3। ट्यूरिंग मशीन का उपयोग करके प्रति यूनिट संख्या बढ़ाएं


चित्र 4 SKA के रूप में MT के लिए वेतन वृद्धि कार्यक्रम का मॉडल

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

यह SKA अंजीर में ऑटोमेटन के रूप में राज्यों का एक ही सेट है। 3। इसके अलावा, ऑटोमेटन मैपिंग के अलावा, एसकेए द्वारा प्रस्तुत, यह दो और मैपिंग को लागू करता है: एक ही मशीन के इनपुट चैनलों के सेट के लिए प्रेडिसेट्स (X1, ..., xM) के सेट को मैप करना, और मशीन के आउटपुट चैनलों का सेट एक ही क्रियाओं के सेट के लिए - y1, ..., yN। उदाहरण के लिए, विधेय x3 सही लौटेगा (उसी नाम के इनपुट संकेत के लिए मान 1), यदि वर्तमान सेल में 1 है, और क्रिया y4, जो ट्रिगर हो जाएगी जब मशीन का समान आउटपुट संकेत मान लेता है 1, सिर को बाईं ओर ले जाने के लिए अनुरूप होगा (L) और आदि आदि

ध्यान दें कि एसकेए सीधे टेप को नियंत्रित नहीं करता है, लेकिन ऑटोमेशन के संकेतों को जोड़ने वाले कार्यों के साथ [अतिरिक्त] मैपिंग को लागू करता है, जो ट्यूरिंग मशीन के कई कार्यों को निर्धारित करता है। यह एक बार फिर हमें आश्वस्त करता है कि "पुराने जमाने" की स्थिति में एक स्वचालित नियंत्रण वस्तु की अवधारणा को पेश करने की आवश्यकता नहीं है, लेकिन गणितीय रूप से मानचित्रण की कठोर अवधारणा पर्याप्त है।

अंजीर में ऑटोमेटा की तुलना करना। 3 और अंजीर। 4, यह देखा जा सकता है कि SKA "*" कमांड का उपयोग नहीं करता है (चित्र 1 देखें)। ऐसी स्थिति में, यह उसके लिए पर्याप्त है कि वह इस कमांड से जुड़े सिग्नल को न दे। इसके अलावा, एक ही संक्रमण में दो या अधिक सिग्नल (इनपुट और आउटपुट दोनों) समानांतर हैं। इसलिए, जब साझा वस्तुओं तक पहुंच का संघर्ष होता है (उदाहरण के लिए, आपको सेल को बदलने और सिर को स्थानांतरित करने की आवश्यकता है), एक समझौते का उपयोग किया जाता है: एक संक्रमण पर कार्रवाई क्रमिक रूप से उनकी संख्याओं के क्रम में की जाती है, अर्थात्। उच्च संख्या वाली क्रिया कम संख्या वाली क्रिया के बाद की जाती है। यह अनुबंध, विधेय पर लागू नहीं होता है, जैसा कि वे टेप नहीं बदलते हैं। इसलिए हम मशीन को अधिक कॉम्पैक्ट और सहज बनाते हैं (मध्यवर्ती राज्यों को पेश करने की कोई आवश्यकता नहीं है)।

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

2.1। C ++ में MT का ऑब्जेक्ट कार्यान्वयन

VKPa वातावरण में C ++ में एक ट्यूरिंग मशीन के ऑब्जेक्ट सॉफ्टवेयर कार्यान्वयन पर विचार करें, जो वेतन वृद्धि कार्यक्रम सहित MT के लिए किसी भी कार्यक्रम को लागू करता है।

इस उद्देश्य के लिए, एक बेस क्लास बनाया गया है जो किसी भी ट्यूरिंग मशीन का प्रतिनिधित्व करता है, जो एक या दूसरे एमटी प्रोग्राम को लागू करने वाले सॉफ़्टवेयर ऑब्जेक्ट्स द्वारा विरासत में मिला है। यह मूल एक सूची 1 में दिखाया गया है, और कार्यक्रम जो वेतन वृद्धि कार्य को लागू करता है, सूची 2 में दिखाया गया है।

लिस्टिंग 1. एमटी बेस क्लास का सॉफ्टवेयर कार्यान्वयन

#include "lfsaappl.h" class FTuringMashine : public LFsaAppl { public: FTuringMashine(string strNam, CVarFsaLibrary *pCVFL, LArc* pTBL); protected: int x15(); int x16(); void y14(); void y15(); void y16(); void y17(); QString strSrc; //    QString strTape; //  QString strHead; //  int nIndexHead{0}; //   bool bRestart{false}; //   int nHeadPosition{0}; //    }; #include "stdafx.h" #include "FTuringMashine.h" FTuringMashine::FTuringMashine(string strNam, CVarFsaLibrary *pCVFL, LArc* pTBL): LFsaAppl(pTBL, strNam, nullptr, pCVFL) { nHeadPosition = 0; strHead = "________________________________________"; nIndexHead = nHeadPosition; } //============================================================== //  //  ? int FTuringMashine::x15() { return strTape[nIndexHead] == '#'; } // ? int FTuringMashine::x16() { return bRestart; } //============================================================== //  //      void FTuringMashine::y14() { strTape[nIndexHead] = '#'; } //    ( ) void FTuringMashine::y15() { nIndexHead++; } //    ( ) void FTuringMashine::y16() { nIndexHead--; } //     void FTuringMashine::y17() { strTape = strSrc; nIndexHead = 0; bRestart = false; nIndexHead = nHeadPosition; } 

लिस्टिंग 2. ट्यूरिंग मशीन के लिए वृद्धि कार्यक्रम

 #include "FTuringMashine.h" class FTIncrement : public FTuringMashine { public: LFsaAppl* Create(CVarFSA *pCVF) { Q_UNUSED(pCVF)return new FTIncrement(nameFsa, pCVarFsaLibrary); } FTIncrement(string strNam, CVarFsaLibrary *pCVFL); protected: int x1(); int x2(); int x3(); void y1(); void y2(); }; #include "FTIncrement.h" static LArc TBL_TIncrement[] = { // . . , .   , 2- , 2011 ., // .17-18 //=====    (. ..   , - .: , 2003. - 208 .) ============== // f(,^` `) = (,`*`,R) // f(,` `) = (,` `,L) // f(,`1`) = (,`0`,L) // f(,` `) = (,`1`,R) // f(,`0`) = (,`1`,R) //========================================= LArc(" ", " ", "^x1", "y15"), LArc(" ", " ", "x1", "y16"), LArc(" ", " ", "x2", "y2y16"), LArc(" ", "", "x1", "y1"), LArc(" ", "", "x3", "y1"), LArc("", " ", "x16", "y17"), LArc() }; FTIncrement::FTIncrement(string strNam, CVarFsaLibrary *pCVFL): FTuringMashine(strNam, pCVFL, TBL_TIncrement) { strSrc = "11011110011111 "; strTape = strSrc; } //  int FTIncrement::x1() { return strTape[nIndexHead] == ' '; } int FTIncrement::x2() { return strTape[nIndexHead] == '1'; } int FTIncrement::x3() { return strTape[nIndexHead] == '0'; } //  void FTIncrement::y1() { strTape[nIndexHead] = '1'; } void FTIncrement::y2() { strTape[nIndexHead] = '0'; } 

2.2। C ++ में कार्यान्वयन के साथ MT के लिए कार्यक्रमों के उदाहरण

एमटी के लिए एक कार्यक्रम के उदाहरण पर विचार करें जो "भाषा के स्वीकर्ता के रूप में कार्य करता है, अर्थात। यह भाषा को "9] से पहचान सकता है। इसका संक्रमण कार्य अंजीर में दिखाया गया है। 5, और अंजीर में SKA के रूप में समकक्ष ऑटोमेटन। 6।

 δ(1, a) = (2, x, R) δ(1, y) = (4, y, R) δ(2, a) = (2, a, R) δ(2, y) = (2, y, R) δ(2, b) = (3, y, L) δ(3, y) = (3, y, L) δ(3, a) = (3, a, R) δ(3, x) = (1, x, R) δ(4, y) = (4, a, R) δ(4, #) = (F, #, L) 

अंजीर। 5. ट्यूरिंग मशीन का संक्रमण कार्य, भाषा को पहचानना {abn: n }1}


अंजीर। 6. ट्यूरिंग मशीन का SKA ग्राफ जो भाषा को पहचानता है {abn: n }1}

SKA के रूप में MT नियंत्रण इकाई में 6 इनपुट और 7 आउटपुट चैनल हैं। स्वीकर्ता कार्यक्रम में संबंधित संख्या और क्रियाएं भी शामिल हैं, जो ऑटोमेटन ग्राफ के दाईं ओर चित्र में प्रस्तुत किए गए हैं। VKPA वातावरण में C ++ प्रोग्राम का कार्यान्वयन सूची 3 में दिखाया गया है।

लिस्टिंग 3. ट्यूरिंग मशीन के लिए प्रोग्राम जो भाषा को पहचानता है {abn: n }1}

 #include "FTuringMashine.h" extern LArc TBL_TAcceptor[]; class FTAcceptor : public FTuringMashine { public: LFsaAppl* Create(CVarFSA *pCVF) { Q_UNUSED(pCVF)return new FTAcceptor(nameFsa, pCVarFsaLibrary); } FTAcceptor(string strNam, CVarFsaLibrary *pCVFL, LArc* pTB = TBL_TAcceptor); protected: int x1(); int x2(); int x3(); int x4(); void y1(); void y2(); void y3(); void y18(); int nState{1}; friend class CDlgTAcceptor; }; #include "stdafx.h" #include "FTAcceptor.h" LArc TBL_TAcceptor[] = { // . .Ma  .   . 2013 ., //     , .304 //=====    ============== // f(1,a) = (2,x,R) f(1,y) = (4,y,R) // f(2,a) = (2,x,R) f(2,y) = (2,y,R) // f(2,b) = (2,x,R) f(3,y) = (3,y,L) // f(3,a) = (3,a,R) f(3,x) = (1,x,R) // f(4,y) = (4,a,R) f(4,#) = (F,#,L) //========================================= LArc("1", "2","x1", "y1y15"), // 1,a,2,x,R LArc("1", "4","x3", "y15"), // 1,y,4,R LArc("2", "2","x1", "y15"), // 2,a,2,R LArc("2", "3","x2", "y2y16"), // 2,b,3,y,L LArc("2", "2","x3", "y15"), // 2,y,2,R LArc("3", "3","x1", "y16"), // 3,a,3,L LArc("3", "3","x3", "y16"), // 3,y,3,L LArc("3", "1","x4", "y15"), // 3,x,1,R LArc("4", "4","x3", "y2y15"), // 4,y,4,a,R LArc("4", "F","x15", "-"), // 4,#,F,-,- LArc("F", "1","x16", "y17"), // LArc("1", "1","x16", "y17"), // LArc("2", "1","x16", "y17"), // LArc("3", "1","x16", "y17"), // LArc("4", "1","x16", "y17"), // // LArc("1", "1","--", "y18"), // LArc() }; FTAcceptor::FTAcceptor(string strNam, CVarFsaLibrary *pCVFL, LArc* pTB): FTuringMashine(strNam, pCVFL, pTB) { strSrc = "aaaaaaaaaabbbbbbbbbb#"; strTape = strSrc; } int FTAcceptor::x1() { return strTape[nIndexHead] == 'a'; } int FTAcceptor::x2() { return strTape[nIndexHead] == 'b'; } int FTAcceptor::x3() { return strTape[nIndexHead] == 'y'; } int FTAcceptor::x4() { return strTape[nIndexHead] == 'x'; } void FTAcceptor::y1() { strTape[nIndexHead] = 'x'; } void FTAcceptor::y2() { strTape[nIndexHead] = 'y'; } void FTAcceptor::y3() { strTape[nIndexHead] = 'a'; } void FTAcceptor::y18() { switch(nState) { case 1: if (x1()) { nState = 2; y1(); y5(); break; } if (x3()) { nState = 4; y5(); break; } break; case 2: if (x1()) { nState = 2; y5(); break; } if (x2()) { nState = 3; y2();y6(); break; } if (x3()) { nState = 2; y5(); break; } break; case 3: if (x1()) { nState = 3; y6(); break; } if (x3()) { nState = 3; y6(); break; } if (x4()) { nState = 1; y5(); break; } break; case 4: if (x3()) { nState = 4; y2(); y5(); break; } if (x5()) { nState = 5; break; } break; case 5: if (x6()) { y7(); nState = 1; break; } break; } } 

लिस्टिंग 3 में, एक्शन y18 SWITCH प्रौद्योगिकी दृष्टिकोण के अनुसार एमटी कार्यक्रम के एक संस्करण का प्रतिनिधित्व करता है। वीकेपीए पर्यावरण के स्वचालित प्रोग्रामिंग के कार्यान्वयन के हिस्से के रूप में, इस मामले में, अंजीर में ऑटोमेटन के बजाय। 6, एक राज्य के साथ एक ऑटोमेटन को लागू करना आवश्यक होगा, जो चक्र में एक संकेत y18 जारी करता है। यह लिस्टिंग 3 में रूपांतरण तालिका की टिप्पणी की गई आउट लाइन से मेल खाती है। स्वाइप के रूप में काम करने के लिए स्वचालित मशीन के लिए, आपको इस लाइन से टिप्पणी को हटाने और शेष लाइनों पर टिप्पणी करने की आवश्यकता है।

[7] से ट्यूरिंग मशीन के लिए एक कार्यक्रम के एक और उदाहरण पर विचार करें, जहां एमटी को "एक परिमित राज्य मशीन मॉडल का एक बहुत ही सरल विस्तार" के रूप में परिभाषित किया गया है। इस मामले में, ट्यूरिंग मशीन के लिए कार्यक्रम संक्रमण और आउटपुट के आंशिक रूप से परिभाषित फ़ंक्शन के पत्नियों की एक सीमित सूची है: S × XS × X × G।

एमटी कार्यक्रम, जो दो नंबरों का सबसे बड़ा सामान्य विभाजक (जीसीडी) पाता है, को अंजीर में दिखाया गया है। 7. इसके बराबर SKA ग्राफ अंजीर में प्रस्तुत किया गया है। 8. ध्यान दें कि पुनर्लेखन आदेश का उपयोग यहां नहीं किया गया है। C ++ कार्यान्वयन को सूची 4 में दिखाया गया है।


अंजीर। 7. ट्यूरिंग मशीन का ट्रांस्फ़ॉर्म ग्राफ, जो दो नंबरों की एक जोड़ी को संसाधित करते समय दो संख्याओं के GCD और इसके कई विन्यासों की गणना करता है।


अंजीर। 8. एसकेए ग्राफ, अंजीर में ग्राफ के बराबर। 7

लिस्टिंग 4. दो नंबरों की जीसीडी खोजने के लिए ट्यूरिंग मशीन के लिए कार्यक्रम

 #include "FTuringMashine.h" class FTGrCmDiv: public FTuringMashine { public: LFsaAppl* Create(CVarFSA *pCVF) { Q_UNUSED(pCVF)return new FTGrCmDiv(nameFsa, pCVarFsaLibrary); } FTGrCmDiv(string strNam, CVarFsaLibrary *pCVFL); protected: int x1(); int x2(); int x3(); int x4(); void y1(); void y2(); void y3(); void y17(); }; #include "FTGrCmDiv.h" static LArc TBL_TGrCmDiv[] = { //=====     (Greatest Common Divider) ============== // . ..   , - .: , 2003. - 208 . // .194 // .  ..    . .:  , 1974, - 200. // .76, 84-87 LArc("s","s","x1", "y16"), // LArc("s","s","x2", "y16"), // LArc("s","p","x3", "y1"), // LArc("s","r","x15", "y15"), // LArc("p","p","x1", "y15"), // LArc("p","p","x2", "y15"), // LArc("p","s","x3", "y2"), // LArc("p","q","x15", "y16"), // LArc("q","q","x1", "y3y16"), // LArc("q","q","x2", "y14y16"), // LArc("q","s","x3", "y15"), // LArc("q","s","x15", "y15"), // LArc("r","r","x1", "y14y15"), // LArc("r","r","x2", "y3y15"), // LArc("r","s","x3", "y16"), // LArc("r","!","x15", "--"), // LArc("!","s","x16", "y17"), // LArc() }; FTGrCmDiv::FTGrCmDiv(string strNam, CVarFsaLibrary *pCVFL): FTuringMashine(strNam, pCVFL, TBL_TGrCmDiv) { nHeadPosition = 4; strSrc = "#1111111111## "; strTape = strSrc; nIndexHead = nHeadPosition; } int FTGrCmDiv::x1() { return strTape[nIndexHead] == 'a'; } int FTGrCmDiv::x2() { return strTape[nIndexHead] == 'b'; } int FTGrCmDiv::x3() { return strTape[nIndexHead] == '1'; } int FTGrCmDiv::x4() { return strTape[nIndexHead] == '#'; } void FTGrCmDiv::y1() { strTape[nIndexHead] = 'a'; } void FTGrCmDiv::y2() { strTape[nIndexHead] = 'b'; } void FTGrCmDiv::y3() { strTape[nIndexHead] = '1'; } void FTGrCmDiv::y17() { strTape = strSrc; nIndexHead = 4; bRestart = false; nIndexHead = nHeadPosition; } 

निष्कर्ष में, SWITH- प्रौद्योगिकी के डेवलपर्स से एक और एमटी कार्यक्रम, जिसे लेख [11] में माना जाता है, जो दो संस्करणों में कोष्ठक को पहचानने का कार्य प्रस्तुत करता है। एक माइली मशीन के रूप में है, दूसरी एक मिश्रित मशीन है (क्रमशः चित्र 9 और अंजीर में 11)। उनके अनुरूप संरचनात्मक ऑटोमेटा को अंजीर में दिखाया गया है। 10 और अंजीर। 12. C ++ प्रोग्राम कार्यान्वयन को लिस्टिंग 5 में दिखाया गया है।


अंजीर। 9. मनमानी गहराई के कोष्ठक की मान्यता। माइल रूपांतरण ग्राफ़


अंजीर। 10. मनमानी गहराई के कोष्ठक की मान्यता। अर्ल एसकेए माइल्स


अंजीर। 11. मनमानी गहराई के कोष्ठक की मान्यता। एक मिश्रित ऑटोमेटन का संक्रमण ग्राफ


अंजीर। 12. मनमानी गहराई के कोष्ठक की मान्यता। मिश्रित ऑटोमेटन के संक्रमण का एससीए ग्राफ

लिस्टिंग 5. कोष्ठक को पहचानने के लिए एक ट्यूरिंग मशीन के लिए कार्यक्रम

 #include "../FTuringMashine.h" class FTListing2 : public FTuringMashine { public: void MooreAction(); LFsaAppl* Create(CVarFSA *pCVF) { Q_UNUSED(pCVF)return new FTListing2(nameFsa, pCVarFsaLibrary); } FTListing2(string strNam, CVarFsaLibrary *pCVFL); protected: int x1(); int x2(); int x3(); int x4(); void y1(); void y2(); void y3(); void y4(); void y5(); int i{0}; }; #include "FTListing2.h" static LArc TBL_TListing2[] = { // .  ..,  ..     , , №2, .144-149 //=====    (. ..   , - .: , 2003. - 208 .) ============== // f(,^` `) = (,`*`,R) // f(,` `) = (,` `,L) // f(,`1`) = (,`0`,L) // f(,` `) = (,`1`,R) // f(,`0`) = (,`1`,R) //========================================= /* //  LArc("0", "1", "x2", "y2"), // '(';  LArc("0", "3", "x3", "--"), // '('; LArc("1", "1", "x2", "y2"), // '(';  LArc("1", "1", "x3", "y3"), // ')';  LArc("1", "3", "^x1x4", "--"), // i!=0;' ';  LArc("1", "3", "x1x3", "--"), // i==0;')';  LArc("1", "2", "x1x4", "--"), // i==0;' ';  LArc("2", "0", "x16", "y17"), // bRestart;  LArc("3", "0", "x16", "y17"), // bRestart;  */ //* //   - LArc("0", "1", "x2", "y2"), // '(' LArc("0", "3", "x3", "--"), // ')' LArc("1", "1", "x2", "y2"), //'(';  LArc("1", "1", "x3", "y3"), // ')';  LArc("1", "2", "x1x4", "--"), // i==0;' '; LArc("1", "3", "^x1x4", "--"), // i!=0;' '; LArc("1", "3", "x1x3", "--"), // i==0;')'; LArc("2", "0", "x16", "y17"), // bRestart;  LArc("3", "0", "x16", "y17"), // bRestart;  //*/ LArc() }; FTListing2::FTListing2(string strNam, CVarFsaLibrary *pCVFL): FTuringMashine(strNam, pCVFL, TBL_TListing2) { strSrc = "(()()) "; strTape = strSrc; } //  int FTListing2::x1() { return i == 0; } int FTListing2::x2() { return strTape[nIndexHead] == '('; } // int FTListing2::x3() { return strTape[nIndexHead] == ')'; } // int FTListing2::x4() { return strTape[nIndexHead] == ' '; } // //  void FTListing2::y1() { i = 0; } // z1_0 void FTListing2::y2() { i++; } // z1_1 void FTListing2::y3() { i--; } // z1_2 void FTListing2::y4() { strTape = ""; } // z2_0 void FTListing2::y5() { strTape = ""; } // z2_1 void FTListing2::MooreAction() { string strState = FGetState(); if (strState=="0") { y1(); } //   else if (strState=="1") { y15(); } //    else if (strState=="2") { y4(); } //  else if (strState=="3") { y5(); } //  } 

अंजीर में automaton के बाद से। 12 ने काम करने से इनकार कर दिया, यह मशीन में अंजीर में जाने का फैसला किया गया था। 9. एसकेए के रूप में इसके बराबर एक स्वचालित मशीन को अंजीर में दिखाया गया है। 10. सच है, औपचारिक रूप से यह एक मिश्रित ऑटोमेटोन भी है, जिसमें से राज्य में संकेत "0" और राज्य में संकेत y15 "1" को पहले कार्यान्वयन (छवि 12) से छोड़ दिया गया था। प्रारंभिक स्थापना के दौरान पहला आवश्यक है, और y15 सिग्नल अगले टेप चरित्र को पढ़ने के लिए एक सिर को दाईं ओर लागू करता है। बाकि के SKA अंजीर में माइल्स मशीन से मेल खाती है। 9।

अंजीर में ऑटोमेटन के बाद। 10 का सफलतापूर्वक परीक्षण किया गया, मशीन में अंजीर में वापस आ गया। 11. और यह स्पष्ट हो गया है कि राज्य "1" के साथ संकेत z1_1 इसके लिए बहुत अधिक है (चित्र 12 में ऑटोमेटन के लिए यह संकेत y2 है)। समस्या यह है कि जब वह "बाएं ब्रैकेट" पाता है, तो वह काउंटर को दो इकाइयों द्वारा बढ़ाता है, और जब वह "बाएं ब्रैकेट" पाता है, तो वह इसे बिल्कुल नहीं बदलता है। इसलिए, जब "बाएं कोष्ठक" का पता लगाया जाता है, तो इसे दो बार कहा जाता है - एक बार लूप पर चिह्नित x2 / y2, और दूसरी बार राज्य में प्रवेश करने पर। और जब एक "सही ब्रैकेट" का पता लगाया जाता है, तो काउंटर पहले लूप पर घटता है, और फिर राज्य में प्रवेश करने पर बढ़ता है।

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

3. निष्कर्ष

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

इसलिए, एक ऑटोमेटन प्रोग्राम और ऑटोमैटॉन प्रोग्रामिंग की अवधारणाओं की परिभाषा देते हुए, हमें "स्वचालित नियंत्रण ऑब्जेक्ट्स" के बारे में बात करने की ज़रूरत नहीं है, लेकिन केवल उन कार्यक्रमों और केवल कार्यक्रमों के बारे में है जिनका नियंत्रण शास्त्रीय परिमित राज्य मशीन के रूप में है।
और एक और दिलचस्प तथ्य जो मैं ध्यान आकर्षित करना चाहूंगा। 2000 के दशक की शुरुआत में, लेखकों ने व्यापक दर्शकों के लिए स्वचालित प्रोग्रामिंग की अपनी समझ को आवाज़ दी। अमूर्त मशीनों पर उनके लेख 2002 [11, 12, 13] के पीसी वर्ल्ड पत्रिका नंबर 2 में प्रकाशित हुए थे। यह तर्क दिया जा सकता है कि इन वर्षों में, पार्टियों के अपराधी प्रभावित नहीं हुए थे। हालांकि, शायद यह केवल चुने हुए निर्णयों में उनके आत्मविश्वास की डिग्री को दर्शाता है।

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

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

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

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