टरमिट
कंप्यूटर विज्ञान में, टरमिट एक ट्यूरिंग मशीन है जिसमें वर्तमान स्थिति के अलावा एक ओरिएंटेशन होता है और एक टेप होता है जिसमें कोशिकाओं के अनंत दो-आयामी ग्रिड होते हैं। आंट और वांट शब्दों का भी प्रयोग किया जाता है। लैंग्टन की आंट एक वर्गाकार ग्रिड की कोशिकाओं पर परिभाषित एक प्रसिद्ध प्रकार की टर्माइट है। पैटर्सन के कीड़े एक प्रकार के टरमिट हैं जो त्रिकोणीय टाइलिंग के किनारों पर परिभाषित होते हैं।
यह दिखाया गया है कि सामान्य रूप पर दीरमाइट्स एक अनंत टेप के साथ एक-आयामी ट्यूरिंग मशीनों की शक्ति के सामान होते हैं, क्योंकि इनमें से कोई भी दूसरे का अनुकरण कर सकता है।
इतिहास
लैंग्टन की चींटियों का आविष्कार 1986 में किया गया था और इन्हें ट्यूरिंग मशीनों के समकक्ष घोषित किया गया था।[1] स्वतंत्र रूप से, 1988 में, एलन एच. ब्रैडी ने एक अभिविन्यास के साथ द्वि-आयामी ट्यूरिंग मशीनों के विचार पर विचार किया और उन्हें टर्निंग मशीनें कहा जाता है।[2][3]
वास्तविक रूप से इन दोनों से मुक्त रूप से,[4] ग्रेग तुर्क ने इसी तरह की सिस्टम की जांच की और उनके बारे में ए.के. ड्यूडनी को लिखा है। ए.के. ड्यूडनी ने 1989 में अमेरिकी वैज्ञानिक में अपने कंप्यूटर रिक्रिएशन्स कॉलम में उन्हें टर-माइट्स नाम दिया है।[5] रूडी रूकर कहानी को इस प्रकार बताते हैं:
ड्यूडनी की रिपोर्ट है कि, तुर्क के प्राणियों के लिए एक नाम की खोज में, उन्होंने सोचा, "ठीक है, वे तुर्क द्वारा अध्ययन की गई ट्यूरिंग मशीनें हैं, इसलिए उन्हें ट्यूर-कुछ होना चाहिए। और वे छोटे कीड़े, या घुन की तरह हैं, इसलिए मैं' मैं उन्हें टर-माइट्स कहूंगा! और यह दीमकों जैसा लगता है!" तुर्क और ड्यूडनी की अनुमति से, मैं हाइफ़न को छोड़ रहा हूँ, और उन्हें दीमक कहूँगा।
— रूडी रूकर, कृत्रिम जीवन प्रयोगशाला[4]
सापेक्ष बनाम एब्सोल्यूट टरमिट
टरमिट को सापेक्ष या निरपेक्ष के रूप में वर्गीकृत किया जा सकता है। सापेक्ष टरमिट, जिसे वैकल्पिक रूप से टर्निंग मशीन के रूप में जाना जाता है, में एक आंतरिक अभिविन्यास होता है। लैंग्टन की आंट ऐसा ही एक उदाहरण है। सापेक्ष टरमिट, परिभाषा के अनुसार, समदैशिक हैं; टरमिट को घुमाने से इसके परिणाम पर कोई प्रभाव नहीं पड़ता है। रिलेटिव टर्माईट्स का नाम इसलिए रखा गया है क्योंकि दिशाओं को वर्तमान अभिविन्यास के सापेक्ष एन्कोड किया गया है, जो बाएँ या पीछे शब्दों के उपयोग के सामान है। तुलनात्मक रूप से, निरपेक्ष टरमिट अपनी दिशाओं को निरपेक्ष रूप से कूटबद्ध करते हैं: एक विशेष निर्देश टरमिट को उत्तर की ओर बढ़ने का निर्देश दे सकता है। एब्सोल्यूट टर्माइट पारंपरिक ट्यूरिंग मशीनों के द्वि-आयामी एनालॉग हैं, इसलिए कभी-कभी इन्हें केवल द्वि-आयामी ट्यूरिंग मशीनों के रूप में जाना जाता है। इस लेख का शेष भाग संबंधित स्थिति से संबंधित है।
विशिष्टता
निम्नलिखित विशिष्टता द्वि-आयामी वर्ग ग्रिड पर टरमिट के लिए विशिष्ट है, जो टरमिट का सबसे अधिक अध्ययन किया जाने वाला प्रकार है। अन्य ग्रिडों पर टरमिट को इसी तरह से निर्दिष्ट किया जा सकता है।
लैंग्टन की आंट की तरह, टरमिट प्रत्येक टाइमस्टेप पर निम्नलिखित कार्य करते हैं:
- मौके पर मुड़ें (90° के कुछ गुणक द्वारा)
- वर्ग का रंग बदलें
- एक वर्ग आगे बढ़ें.
ट्यूरिंग मशीनों की तरह, क्रियाओं को एक स्थान संक्रमण तालिका द्वारा निर्दिष्ट किया जाता है जिसमें टरमाइट की वर्तमान आंतरिक स्थिति और उस सेल का रंग सूचीबद्ध होता है जिस पर वह वर्तमान में खड़ा है। उदाहरण के लिए, इस पृष्ठ के शीर्ष पर छवि में दिखाया गया टर्माइट निम्नलिखित तालिका द्वारा निर्दिष्ट है:
| वर्तमान कलर | |||||||
|---|---|---|---|---|---|---|---|
| 0 | 1 | ||||||
| कलर लिखें | मोड़ | अगली अवस्था | कलर लिखें | मोड़ | अगली अवस्था | ||
| वर्तमान अवस्था | 0 | 1 | R | 0 | 1 | R | 1 |
| 1 | 0 | N | 0 | 0 | N | 1 | |
मुड़ने की दिशा L (90° बाएँ), R (90° दाएँ), N (कोई मोड़ नहीं) और U (180° यू टर्न) में से एक है।
उदाहरण
<गैलरी कैप्शन= वर्गाकार टाइलिंग पर दो-अवस्था वाले दो-रंग वाले टरमिट के उदाहरण, सभी एक रिक्त कॉन्फ़िगरेशन से प्रारंभ होते हैं: > File:Turmite-111180121010-12536.svg|सर्पिल वृद्धि. File:Turmite-121021110111-27731.svg|अराजक विकास की अवधि के पश्चात् एक राजमार्ग का उत्पादन। File:Turmite-121181121020-65932.svg|एक विशिष्ट बनावट के साथ अराजक विकास। File:Turmite-180121020081-223577.svg|एक विस्तारित फ्रेम के अंदर एक विशिष्ट बनावट के साथ विकास। File:Turmite-181181121010-10211.svg|फाइबोनैचि सर्पिल का निर्माण। File:Turmite creating a growing diamond.png|बढ़ते हीरे का निर्माण </गैलरी> <गैलरी कैप्शन= अधिक राज्यों और रंगों के साथ और गैर-वर्ग ग्रिड पर टरमिट के उदाहरण: > File:Turmite_Snowflake.jpg|तीन-अवस्था वाला दो-रंग का टरमीट बर्फ के टुकड़े जैसा भग्न पैटर्न पैदा करता है। File:Hexagonal turmite.svg| षटकोणीय टाइलिंग पर तीन-रंग की तीन-अवस्था वाली टर्माइट, लगभग 194150 कदमों के पश्चात् एक आवधिक लूप में फंसने से पहले एक विशिष्ट बनावट के साथ अव्यवस्थित रूप से बढ़ रही है। </गैलरी>
रिक्त ग्रिड या अन्य कॉन्फ़िगरेशन से प्रारंभ करके, सबसे समान्य रूप पर देखे जाने वाले व्यवहार अराजक विकास, सर्पिल विकास और 'राजमार्ग' निर्माण हैं। कुछ निश्चित चरणों के पश्चात् दुर्लभ उदाहरण आवधिक हो जाते हैं।
बिजी बीवर गेम
एलन एच. ब्रैडी ने टर्मिनेटिंग टर्माइट (बिजी बीवर के समतुल्य) की खोज की और एक 2-स्टेट 2-रंग मशीन पाई जो रुकने से पहले 37 1 प्रिंट करती थी, और दूसरी मशीन जो रुकने से पहले 121 कदम चलती थी।[3] उन्होंने उन दीमकों पर भी विचार किया जो त्रिकोणीय टाइलिंग पर चलते हैं, और यहां भी अनेक बिजी बीवर खोजते हैं।
एड पेग, जूनियर ने बिजी बीवर गेम के लिए एक और दृष्टिकोण पर विचार किया गया था। उन्होंने ऐसे दीमकों का सुझाव दिया जो उदाहरण के लिए बाएँ और दाएँ दोनों ओर मुड़ सकते हैं, जो दो भागों में विभाजित हो सकते हैं। इसक पश्चात् में मिलने वाली टरमिट एक दूसरे को नष्ट कर देती हैं। इस सिस्टम में, एक बिजी बीवर वह है जो एक ही टरमिट के प्रारंभिक पैटर्न से सबसे लंबे समय तक चलता है, इससे पहले कि सभी टरमिट एक-दूसरे को नष्ट कर देता है।[6]
अन्य ग्रिड
एलन एच. ब्रैडी के त्रिकोणीय ग्रिड पर टरमिट के प्रारंभिक कार्य के पश्चात्, हेक्सागोनल टाइलिंग का भी पता लगाया गया है। इस कार्य का अधिकांश भाग टिम हटन के कारण है, और उनके परिणाम रूल टेबल रिपोजिटरी पर हैं। उन्होंने टर्माइट्स पर तीन आयामों में भी विचार किया है, और कुछ प्रारंभिक परिणाम एकत्र किए हैं। एलन एच. ब्रैडी और टिम हटन ने पूर्णांक जाली पर एक आयामी सापेक्ष टरमिट की भी जांच की है, जिसे ब्रैडी ने फ़्लिपर्स कहा है। (एक-आयामी निरपेक्ष टर्माइट को निश्चित रूप से ट्यूरिंग मशीन के रूप में जाना जाता है।)
यह भी देखें
- सेलुलर ऑटोमेटन
- लैंग्टन की आंट
- पैटर्सन के कीड़े
संदर्भ
- ↑ Langton, Chris G. (1986). "सेलुलर ऑटोमेटा के साथ कृत्रिम जीवन का अध्ययन" (PDF). Physica D: Nonlinear Phenomena. 22 (1–3): 120–149. Bibcode:1986PhyD...22..120L. doi:10.1016/0167-2789(86)90237-X. hdl:2027.42/26022.
- ↑ Brady, Allen H. (1988). "The Busy Beaver Game and the Meaning of Life". In Rolf Herken (ed.). The Universal Turing Machine: A Half-Century Survey. Springer-Verlag. ISBN 0-19-853741-7.
- ↑ 3.0 3.1 Brady, Allen H. (1995). "The Busy Beaver Game and the Meaning of Life". In Rolf Herken (ed.). The Universal Turing Machine: A Half-Century Survey (2nd ed.). Springer-Verlag. pp. 237–254. ISBN 3-211-82637-8.
- ↑ 4.0 4.1 Rucker, Rudy. "कृत्रिम जीवन प्रयोगशाला". Retrieved October 16, 2009.
- ↑ Dewdney, A. K. (September 1989). "Computer Recreations: Two-dimensional Turing machines and Turmites make tracks on a plane". Scientific American. 261: 180–183. doi:10.1038/scientificamerican0989-180.
- ↑ Pegg, Jr., Ed. "गणित पहेली". Retrieved 15 October 2009.
बाहरी संबंध
- "Webpage demonstrating several turmites". Archived from the original on 2013-12-21.
- Pegg Jr., Ed (June 7, 2004). "Math Games: 2D Turing Machines". MAA Online. Archived from the original on 2013-05-16.
- Pegg Jr., Ed (October 27, 2003). "Math Games: Paterson's Worms Revisited". MAA Online. Archived from the original on 2004-03-23.
- Turmite, at MathWorld.
- Golly script for generating arbitrary turmites
- Absolute- and relative-movement Turmites and Busy Beavers on square, cubic, triangular and hexagonal grids
