टरमिट
कंप्यूटर विज्ञान में, टरमिट एक ट्यूरिंग मशीन है जिसमें वर्तमान स्थिति के अलावा एक ओरिएंटेशन होता है और एक टेप होता है जिसमें कोशिकाओं के अनंत दो-आयामी ग्रिड होते हैं। चींटी और वांट शब्दों का भी प्रयोग किया जाता है। लैंग्टन की चींटी एक वर्गाकार ग्रिड की कोशिकाओं पर परिभाषित एक प्रसिद्ध प्रकार की टर्माइट है। पैटर्सन के कीड़े एक प्रकार के टरमिट हैं जो त्रिकोणीय टाइलिंग के किनारों पर परिभाषित होते हैं।
यह दिखाया गया है कि सामान्य तौर पर दीरमाइट्स एक अनंत टेप के साथ एक-आयामी ट्यूरिंग मशीनों की शक्ति के बराबर होते हैं, क्योंकि इनमें से कोई भी दूसरे का अनुकरण कर सकता है।
इतिहास
लैंग्टन की चींटियों का आविष्कार 1986 में किया गया था और इन्हें ट्यूरिंग मशीनों के समकक्ष घोषित किया गया था।[1] स्वतंत्र रूप से, 1988 में, एलन एच. ब्रैडी ने एक अभिविन्यास के साथ द्वि-आयामी ट्यूरिंग मशीनों के विचार पर विचार किया और उन्हें टर्निंग मशीनें कहा।[2][3] जाहिर तौर पर इन दोनों से स्वतंत्र रूप से,[4] ग्रेग तुर्क ने इसी तरह की प्रणाली की जांच की और उनके बारे में ए.के. ड्यूडनी को लिखा। ए.के. ड्यूडनी ने 1989 में अमेरिकी वैज्ञानिक में अपने कंप्यूटर रिक्रिएशन्स कॉलम में उन्हें टर-माइट्स नाम दिया।[5] रूडी रूकर कहानी को इस प्रकार बताते हैं:
Dewdney reports that, casting about for a name for Turk's creatures, he thought, "Well, they're Turing machines studied by Turk, so they should be tur-something. And they're like little insects, or mites, so I'll call them tur-mites! And that sounds like termites!" With the kind permission of Turk and Dewdney, I'm going to leave out the hyphen, and call them turmites.
— Rudy Rucker, Artificial Life Lab[4]
सापेक्ष बनाम पूर्ण दीमक
हल्दी को सापेक्ष या निरपेक्ष के रूप में वर्गीकृत किया जा सकता है। सापेक्ष दीमक, जिसे वैकल्पिक रूप से टर्निंग मशीन के रूप में जाना जाता है, में एक आंतरिक अभिविन्यास होता है। लैंग्टन की चींटी ऐसा ही एक उदाहरण है। सापेक्ष दीमक, परिभाषा के अनुसार, समदैशिक हैं; दीमक को घुमाने से इसके परिणाम पर कोई प्रभाव नहीं पड़ता है। रिलेटिव टर्माईट्स का नाम इसलिए रखा गया है क्योंकि दिशाओं को वर्तमान अभिविन्यास के सापेक्ष एन्कोड किया गया है, जो बाएँ या पीछे शब्दों के उपयोग के बराबर है। तुलनात्मक रूप से, निरपेक्ष दीमक अपनी दिशाओं को निरपेक्ष रूप से कूटबद्ध करते हैं: एक विशेष निर्देश दीमक को उत्तर की ओर बढ़ने का निर्देश दे सकता है। एब्सोल्यूट टर्माइट पारंपरिक ट्यूरिंग मशीनों के द्वि-आयामी एनालॉग हैं, इसलिए कभी-कभी इन्हें केवल द्वि-आयामी ट्यूरिंग मशीनों के रूप में जाना जाता है। इस लेख का शेष भाग संबंधित मामले से संबंधित है।
विशिष्टता
निम्नलिखित विशिष्टता द्वि-आयामी वर्ग ग्रिड पर दीमक के लिए विशिष्ट है, जो दीमक का सबसे अधिक अध्ययन किया जाने वाला प्रकार है। अन्य ग्रिडों पर हल्दी को इसी तरह से निर्दिष्ट किया जा सकता है।
लैंग्टन की चींटी की तरह, दीमक प्रत्येक टाइमस्टेप पर निम्नलिखित कार्य करते हैं:
- मौके पर मुड़ें (90° के कुछ गुणक द्वारा)
- वर्ग का रंग बदलें
- एक वर्ग आगे बढ़ें.
ट्यूरिंग मशीनों की तरह, क्रियाओं को एक राज्य संक्रमण तालिका द्वारा निर्दिष्ट किया जाता है जिसमें टरमाइट की वर्तमान आंतरिक स्थिति और उस सेल का रंग सूचीबद्ध होता है जिस पर वह वर्तमान में खड़ा है। उदाहरण के लिए, इस पृष्ठ के शीर्ष पर छवि में दिखाया गया टर्माइट निम्नलिखित तालिका द्वारा निर्दिष्ट है:
| Current color | |||||||
|---|---|---|---|---|---|---|---|
| 0 | 1 | ||||||
| Write color | Turn | Next state | Write color | Turn | Next state | ||
| Current state | 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
