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

वांग टाइल (डोमिनोइज) का आविष्कार हाओ वांग ने 1961 में गणितीय समस्याओं के लिए किया था, लेकिन टाइल ग्राफिक्स बनाने के लिए व्यापक रूप से गेम में उपयोग किया गया था। उनके लिए धन्यवाद, परिणाम दोहराव नहीं दिखता है, दोनों 2D बनावट और टाइलिंग के साथ 3 डी मॉडल में।

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

यह एक अद्भुत और समझ से बाहर का बयान है, इसलिए इस पोस्ट में मैं इस मुद्दे को थोड़ा सा पता लगाऊंगा।

वैन टाइल्स के बारे में संक्षेप में

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

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

ग्राफिक उदाहरण, अधिक विस्तृत जानकारी, और Shadertoy के लिंक यहां मिल सकते हैं: वांग टाइलिंग ।

यहाँ एक उदाहरण मैंने बनाया है। मेरे ग्राफिक्स "आर्ट प्रोग्रामर" हैं, लेकिन मुझे उम्मीद है कि यह विचार स्पष्ट है। ड्राइंग 16 टाइलों से बना है, और प्रत्येक चेहरे के लिए दो अलग-अलग प्रकार के चेहरे हैं।

ट्यूरिंग मशीनों के बारे में संक्षेप में

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

ट्यूरिंग मशीन कई मुख्य घटकों से बनी होती है: मेमोरी टेप, रीड / राइट हेड और स्टेट मशीन।

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

रीड / राइट हेड टेप की एक निश्चित स्थिति से शुरू होता है और मूल्यों को पढ़ / लिख सकता है, और टेप के साथ बाएँ और दाएँ भी घूम सकता है।

राज्य मशीन रीड / राइट हेड को नियंत्रित करती है।

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

उदाहरण के लिए, राज्य ए में, यदि टेप से 0 पढ़ा जाता है, तो नियम टेप की वर्तमान स्थिति में 1 लिखने के लिए हो सकता है, पढ़ने / लिखने के सिर को दाईं ओर ले जा सकता है, या राज्य में जा सकता है। राज्य बी में एक पूरी तरह से अलग तर्क हो सकता है और या तो संक्रमण कर सकता है। राज्य A पर वापस जाएं, या राज्य B में रहें या पूरी तरह से अलग अवस्था में चले जाएं।

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

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

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

वांग टाइल गणना

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

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

आइए एक सरल उदाहरण देखें जिसमें निम्नलिखित राज्य मशीन तर्क नियम हैं:

1. जब मशीन राज्य ए में होती है, तो 0 पढ़ने के मामले में, हम 1 लिखते हैं, रीड / राइट हेड को नीचे ले जाते हैं और स्टेट बी पर जाते हैं।
2. जब मशीन राज्य ए में होती है, तो 1 पढ़ने के मामले में, कार्यक्रम बंद हो जाता है (अंतिम स्थिति में स्विच)।
3. जब मशीन स्टेट B में होती है, तो 0 पढ़ने के मामले में, हम 1 लिखते हैं, रीड-राइट हेड को ऊपर ले जाते हैं और स्टेट A पर जाते हैं।
4. जब मशीन राज्य बी में होती है, तो 1 पढ़ने के मामले में, कार्यक्रम बंद हो जाता है (अंतिम स्थिति में चला जाता है)

टेप ड्राइव

सबसे पहले, हमें टेप के लिए एक स्थायी भंडारण की आवश्यकता है। ऐसा करने के लिए, हमें निम्नलिखित दो टाइलों की आवश्यकता है:


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

नीचे दिए गए आरेख में, हम बाईं ओर के कॉलम (समय 0) में 0101 मान के साथ टेप को इनिशियलाइज़ करते हैं। संगत चेहरों के साथ केवल टाइलें होने से, हम देखते हैं कि स्मृति में मूल्य हमेशा के लिए संग्रहीत होते हैं। हमने एक मेमोरी ड्राइव लागू किया है!


हम 0 से आरंभ की गई मेमोरी के साथ अपने उदाहरण को प्रदर्शित करना शुरू करेंगे, और ऊपर की आकृति केवल स्मृति की दृढ़ता को दर्शाती है।

हेड स्टेट मशीन पढ़ें-लिखें

ट्यूरिंग मशीन का रीड / राइट हेड चेहरे की जानकारी के हिस्से के रूप में प्रस्तुत किया जाता है। इस प्रकार, चेहरे के भंडारण के अलावा 0 या 1, यदि पढ़ने / लिखने वाला सिर इसमें है, तो यह राज्य मशीन की स्थिति को भी संग्रहीत करता है।

हमारे उदाहरण में, दो राज्यों का उपयोग किया जाता है (अंतिम राज्य शामिल नहीं): ए और बी। यदि 1 पढ़ा जाता है, तो किसी भी राज्य (ए या बी) में कार्यक्रम समाप्त होता है।

इसे संभालने के लिए, हमें निम्नलिखित टाइलों की आवश्यकता है:



अब जब हमारे पास अंतिम स्थिति (नियम 2 और 4) में संक्रमण के लिए नियम हैं, तो हमें यह समझने की आवश्यकता है कि एक राज्य से दूसरे राज्य में स्विच करने वाले नियमों को कैसे लागू किया जाए (नियम 1 और 3)।

रीड / राइट हेड को आगे बढ़ाना

नियम 1 में कहा गया है कि अगर हम राज्य A में हैं और 0 पढ़ते हैं, तो हमें 1 लिखना होगा, रीड / राइट हेड को नीचे ले जाएँ और राज्य B पर जाएँ।

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


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


नियम 3 में कहा गया है कि यदि हम राज्य B में हैं और 0 पढ़ते हैं, तो हमें 1 लिखना होगा, रीड / राइट हेड को ऊपर ले जाना चाहिए और स्टेट A पर जाना होगा।

ऐसा करने के लिए, हमें नियम 1 के निर्माण के समान एक निर्माण की आवश्यकता है, लेकिन हम नीचे नहीं जाते हैं, लेकिन ऊपर। निम्नलिखित तीन टाइलें वांछित परिणाम देंगी:

प्रारंभिक स्तंभ टाइलें

हम सिमुलेशन क्षेत्र की सीमाओं का अनुभव करेंगे जैसे कि उनके पास "एक्स" चेहरा है।

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

ये दो टाइलें हैं:

टाइल्स का तैयार सेट

यहां 12 टाइलों का पूरा सेट है, जिनका हम उपयोग करेंगे:

पूर्ण अनुकरण

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


यहां से, दूसरा कॉलम बनाने के लिए, हम ऊपर से शुरू करते हैं और नीचे जाते हैं, एक टाइल का चयन करते हैं जो चेहरे के प्रतिबंधों से मेल खाती है जो इसे छूती है। इस पहले चरण में, सिर 0 पढ़ता है, 1 लिखता है, नीचे जाता है और राज्य बी में जाता है।


यहां दूसरा चरण है, जहां सिर 0 पढ़ता है, 1 लिखता है, ऊपर जाता है और राज्य ए में जाता है।


यहां अंतिम चरण है जिसमें सिर 1 पढ़ता है और अंतिम स्थिति में प्रवेश करता है, यह दर्शाता है कि कार्यक्रम पूरा हो गया है।


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

महत्वपूर्ण विवरण

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

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



फिर हम सही को कैसे चुनते हैं?

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

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

निष्कर्ष और लिंक

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

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

यहाँ WebGL पिक्सेल शेडर में Shadertoy में वांग टाइलों का उपयोग करके अपराधों की गणना का कार्यान्वयन है:

शैडरटॉय: वांगटाइल्स: प्राइमनेरेटर

यहाँ ट्यूरिंग कारों और रुकने की समस्या के बारे में कुछ और बेहतरीन वीडियो हैं:

ट्यूरिंग मशीन समझाया - कंप्यूटरफाइल

ट्यूरिंग एंड द हॉल्टिंग समस्या - कंप्यूटरफाइल

और यहाँ कुछ और लिंक दिए गए हैं:

टाइल्स के साथ कम्प्यूटिंग

वान टाइलें

वांग टाइलें और ट्यूरिंग मशीनें

वांग टाइलें - 1

यहाँ कुछ वैज्ञानिक लेख दिए गए हैं:

टाइल्स के साथ कम्प्यूटिंग

झुकाव की संगणना