😭 🔒 🚥 एक्सेल ट्यूरिंग मशीन 🧕🏼 🚉 ㊗️

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

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

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

एक सरल उदाहरण: एक बाइनरी नंबर में एक जोड़ना

ऐसी मशीन के लिए, तीन वर्णों की वर्णमाला आवश्यक होती है (0,1, x) - जहाँ 0 और 1 एक संख्या के लिए होगा, और x एक खाली सेल के लिए। यही है, खाली टेप सभी वर्ण "x" से भरा है।
सिर में 4 राज्य होंगे: q1, q2, q3 और q4 - मशीन को रोकें।
हम मैट्रिक्स के रूप में मशीन के लिए नियम लिखते हैं:

यह सत्यापित करना आसान है कि ऐसी मशीन, जब प्रारंभिक राज्य q1 के साथ बाइनरी नंबर के उच्चतम अंक पर सिर रखते हैं, तो यह संख्या 1 से बढ़ जाएगी।

एक्सेल कार्यान्वयन

एक नियम तालिका बनाएं, जैसा कि ऊपर दिए गए उदाहरण में है। इस पूरी तालिका का चयन करें और इसे "नियम" कहें। मारो मारो।

मामूली बदलाव के साथ तालिका की संरचना ऊपर के उदाहरण के समान है:
• मशीन की स्थितियों को केवल संख्या कहा जाता है (बिना q)
• एक खाली सेल का अर्थ है प्रतीक "2"
• हेड मूवमेंट 1 - दायीं ओर, -1 - बाईं ओर, 0 - सेट है

टेप की प्रारंभिक स्थिति सेट करें:

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

ट्यूरिंग मशीन के लिए एक्सेल फॉर्मूला का विवरण

टेप सेल के लिए सूत्र:
= IF (K14 <> 0; INDEX (नियम; K14 + 1; 2 + K13 * 3); K13;
यह सूत्र अगले चरण (K17) में टेप सेल मान के लिए है। इसका मतलब है कि यदि सिर (K14) सेल के तहत है (यानी, K14 में सेल शून्य नहीं है), तो नियमों के अनुसार मूल्य इस सेल में लिखा जाना चाहिए (नियम सरणी से)। यदि टेप के सेल के तहत सेल शून्य है (जिसका अर्थ है कि इसके नीचे कोई सिर नहीं है), तो मान नहीं बदलता है।

सिर की स्थिति के लिए सूत्र (पठनीयता के लिए लाइन ब्रेक बनाये जाते हैं):
= IF (K14 <> 0; IF (INDEX (नियम; K14 + 1; 4 + K13 * 3) = 0; INDEX (नियम; K14 + 1; 3 + K13 * 3); 0);
IF (J14 <> 0; IF (INDEX (नियम; J14 + 1; 4 + J13 * 3) = 1; INDEX (नियम; J14 + 1; 3 + J13 * 3); 0);
IF (L14 <> 0; IF (INDEX (नियम; L14 + 1; 4 + L13 * 3) = - 1; INDEX (नियम; L14 + 1; 3 + L13 * 3); 0); 0)))

यह सूत्र
1) पहले यह जांचता है कि क्या सिर इस सेल में है (K14) - तो अगर नियम जगह पर बने रहने के लिए कहते हैं, तो मशीन की स्थिति नियमों के अनुसार इस सेल में लिखी जाती है
2) यदि सिर बाईं ओर (J14) एक कोशिका है और नियम दाईं ओर चलते हैं - तो मशीन की स्थिति को इस सेल में नियमों के अनुसार लिखा जाता है
3) यदि सिर दाईं ओर (L14) के लिए एक सेल है और नियम कहते हैं कि बाईं ओर चलते हैं - तो मशीन की स्थिति नियमों के अनुसार इस सेल में लिखी जाती है
4) अन्य सभी मामलों में, शून्य लिखा है
यह सूत्र सिर की गति को अनुकरण करता है।
सूत्र अनुक्रमणिका फ़ंक्शन ( सरणी, पंक्ति, स्तंभ ) का उपयोग करते हैं। हम INDEX मान (नियम; K14 + 1; 4 + K13 * 3) की गणना करते हैं - सिर राज्य सूत्र का एक टुकड़ा।
जैसा कि आकृति से देखा जा सकता है, K14 = 1, K13 = 1। इसलिए आपको INDEX (नियम; 1 + 1; 4 + 1 * 3) यानी INDEX (नियम; 2; 7) - 2 पंक्ति के चौराहे पर "नियम" सरणी में मूल्य और 7 वें कॉलम (पंक्तियों और स्तंभों) को 1 से शुरू करने की आवश्यकता है। नहीं ०)। हमारी नेमप्लेट में यह मान "1" है।

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

यहां एक्सेल फाइल का लिंक दिया गया है

निष्कर्ष

यदि Excel ने मनमाने ढंग से बड़ी संख्या में पंक्तियों और स्तंभों का समर्थन किया है, तो इसका स्वचालित रूप से मतलब होगा कि Excel सूत्रों का उपयोग करके आप किसी भी कम्प्यूटेशनल फ़ंक्शन को लागू कर सकते हैं, क्योंकि Excel Turing-complete होगा

पीएस ट्रिकी कार्य: लेख में वर्णित ट्यूरिंग मशीन के नियमों को बदल दें ताकि यह बाइनरी संख्या 1 से कम कर दे।

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

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

एक सरल उदाहरण: एक बाइनरी नंबर में एक जोड़ना

एक्सेल कार्यान्वयन

निष्कर्ष

More articles: