टरमिट: Difference between revisions

From Vigyanwiki
(Created page with "{{Short description|Turing machine on a two-dimensional grid}} {{Distinguish|Termite}} File:Turmite-120121010011-8342.svg|frame|right|एक वर्गाकार ग्...")
 
No edit summary
 
(7 intermediate revisions by 4 users not shown)
Line 1: Line 1:
{{Short description|Turing machine on a two-dimensional grid}}
{{Short description|Turing machine on a two-dimensional grid}}
{{Distinguish|Termite}}
{{Distinguish|दीमक}}
[[File:Turmite-120121010011-8342.svg|frame|right|एक वर्गाकार ग्रिड पर 2-अवस्था 2-रंग की दीरमाइट। एक खाली ग्रिड से शुरू करके, 8342 चरणों के बाद टर्माइट (एक लाल पिक्सेल) ने अराजक और नियमित गति दोनों चरणों का प्रदर्शन किया है।]][[कंप्यूटर विज्ञान]] में, टरमिट एक [[ट्यूरिंग मशीन]] है जिसमें वर्तमान स्थिति के अलावा एक ओरिएंटेशन होता है और एक टेप होता है जिसमें कोशिकाओं के अनंत दो-आयामी ग्रिड होते हैं। चींटी और वांट शब्दों का भी प्रयोग किया जाता है। लैंग्टन की चींटी एक वर्गाकार ग्रिड की कोशिकाओं पर परिभाषित एक प्रसिद्ध प्रकार की टर्माइट है। पैटर्सन के कीड़े एक प्रकार के टरमिट हैं जो [[त्रिकोणीय टाइलिंग]] के किनारों पर परिभाषित होते हैं।
[[File:Turmite-120121010011-8342.svg|frame|right|एक वर्गाकार ग्रिड पर 2-अवस्था 2-रंग की दीरमाइट। एक रिक्त ग्रिड से शुरू करके, 8342 चरणों के पश्चात् टर्माइट (एक लाल पिक्सेल) ने अराजक और नियमित गति दोनों चरणों का प्रदर्शन किया है।]][[कंप्यूटर विज्ञान]] में, टरमिट एक [[ट्यूरिंग मशीन]] है जिसमें वर्तमान स्थिति के अलावा एक ओरिएंटेशन होता है और एक टेप होता है जिसमें कोशिकाओं के अनंत दो-आयामी ग्रिड होते हैं। आंट और वांट शब्दों का भी प्रयोग किया जाता है। लैंग्टन की आंट एक वर्गाकार ग्रिड की कोशिकाओं पर परिभाषित एक प्रसिद्ध प्रकार की टर्माइट है। पैटर्सन के कीड़े एक प्रकार के टरमिट हैं जो [[त्रिकोणीय टाइलिंग]] के किनारों पर परिभाषित होते हैं।


यह दिखाया गया है कि सामान्य तौर पर दीरमाइट्स एक अनंत टेप के साथ एक-आयामी ट्यूरिंग मशीनों की शक्ति के बराबर होते हैं, क्योंकि इनमें से कोई भी दूसरे का अनुकरण कर सकता है।
यह दिखाया गया है कि सामान्य रूप पर दीरमाइट्स एक अनंत टेप के साथ एक-आयामी ट्यूरिंग मशीनों की शक्ति के सामान होते हैं, क्योंकि इनमें से कोई भी दूसरे का अनुकरण कर सकता है।


== इतिहास ==
== इतिहास ==


लैंग्टन की चींटियों का आविष्कार 1986 में किया गया था और इन्हें ट्यूरिंग मशीनों के समकक्ष घोषित किया गया था।<ref>{{cite journal | doi = 10.1016/0167-2789(86)90237-X | last = Langton | first = Chris G. | title = सेलुलर ऑटोमेटा के साथ कृत्रिम जीवन का अध्ययन| year = 1986 | journal = Physica D: Nonlinear Phenomena | volume = 22 | issue = 1–3 | pages = 120–149 | hdl = 2027.42/26022| url = https://deepblue.lib.umich.edu/bitstream/2027.42/26022/1/0000093.pdf | bibcode = 1986PhyD...22..120L | hdl-access = free }}</ref> स्वतंत्र रूप से, 1988 में, एलन एच. ब्रैडी ने एक अभिविन्यास के साथ द्वि-आयामी ट्यूरिंग मशीनों के विचार पर विचार किया और उन्हें टर्निंग मशीनें कहा।<ref>{{cite book | title=The Universal Turing Machine: A Half-Century Survey | last=Brady | first=Allen H. | chapter=The Busy Beaver Game and the Meaning of Life | editor=Rolf Herken | year=1988 | publisher=Springer-Verlag | isbn=0-19-853741-7 | url-access=registration | url=https://archive.org/details/universalturingm0000unse }}</ref><ref name="Brady95">{{cite book | title=The Universal Turing Machine: A Half-Century Survey | edition=2nd | last=Brady | first=Allen H. | chapter=The Busy Beaver Game and the Meaning of Life | editor=Rolf Herken|chapter-url=https://books.google.com/books?id=YafIDVd1Z68C&q=universal%20turing%20machine%20herken&pg=PA237 | year=1995 | pages=237–254 | publisher=Springer-Verlag | isbn=3-211-82637-8}}</ref>
लैंग्टन की चींटियों का आविष्कार 1986 में किया गया था और इन्हें ट्यूरिंग मशीनों के समकक्ष घोषित किया गया था।<ref>{{cite journal | doi = 10.1016/0167-2789(86)90237-X | last = Langton | first = Chris G. | title = सेलुलर ऑटोमेटा के साथ कृत्रिम जीवन का अध्ययन| year = 1986 | journal = Physica D: Nonlinear Phenomena | volume = 22 | issue = 1–3 | pages = 120–149 | hdl = 2027.42/26022| url = https://deepblue.lib.umich.edu/bitstream/2027.42/26022/1/0000093.pdf | bibcode = 1986PhyD...22..120L | hdl-access = free }}</ref> स्वतंत्र रूप से, 1988 में, एलन एच. ब्रैडी ने एक अभिविन्यास के साथ द्वि-आयामी ट्यूरिंग मशीनों के विचार पर विचार किया और उन्हें टर्निंग मशीनें कहा जाता है।<ref>{{cite book | title=The Universal Turing Machine: A Half-Century Survey | last=Brady | first=Allen H. | chapter=The Busy Beaver Game and the Meaning of Life | editor=Rolf Herken | year=1988 | publisher=Springer-Verlag | isbn=0-19-853741-7 | url-access=registration | url=https://archive.org/details/universalturingm0000unse }}</ref><ref name="Brady95">{{cite book | title=The Universal Turing Machine: A Half-Century Survey | edition=2nd | last=Brady | first=Allen H. | chapter=The Busy Beaver Game and the Meaning of Life | editor=Rolf Herken|chapter-url=https://books.google.com/books?id=YafIDVd1Z68C&q=universal%20turing%20machine%20herken&pg=PA237 | year=1995 | pages=237–254 | publisher=Springer-Verlag | isbn=3-211-82637-8}}</ref>
जाहिर तौर पर इन दोनों से स्वतंत्र रूप से,<ref name="rucker">{{cite web|last=Rucker|first=Rudy|title=कृत्रिम जीवन प्रयोगशाला|url=http://www.cs.sjsu.edu/~rucker/bopbook.htm|access-date=October 16, 2009}}</ref> [[ग्रेग तुर्क]] ने इसी तरह की प्रणाली की जांच की और उनके बारे में ए.के. ड्यूडनी को लिखा। ए.के. ड्यूडनी ने 1989 में [[ अमेरिकी वैज्ञानिक ]] में अपने कंप्यूटर रिक्रिएशन्स कॉलम में उन्हें टर-माइट्स नाम दिया।<ref>{{cite journal|last=Dewdney|first=A. K. | title=Computer Recreations: Two-dimensional Turing machines and Turmites make tracks on a plane | journal = Scientific American |date=September 1989 | pages=180–183 |volume=261 |doi=10.1038/scientificamerican0989-180}} {{closed access}}</ref> [[रूडी रूकर]] कहानी को इस प्रकार बताते हैं:


{{quote|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<ref name="rucker" />}}
वास्तविक रूप से इन दोनों से मुक्त रूप से,<ref name="rucker">{{cite web|last=Rucker|first=Rudy|title=कृत्रिम जीवन प्रयोगशाला|url=http://www.cs.sjsu.edu/~rucker/bopbook.htm|access-date=October 16, 2009}}</ref> [[ग्रेग तुर्क]] ने इसी तरह की सिस्टम की जांच की और उनके बारे में ए.के. ड्यूडनी को लिखा है। ए.के. ड्यूडनी ने 1989 में [[ अमेरिकी वैज्ञानिक |अमेरिकी वैज्ञानिक]] में अपने कंप्यूटर रिक्रिएशन्स कॉलम में उन्हें टर-माइट्स नाम दिया है।<ref>{{cite journal|last=Dewdney|first=A. K. | title=Computer Recreations: Two-dimensional Turing machines and Turmites make tracks on a plane | journal = Scientific American |date=September 1989 | pages=180–183 |volume=261 |doi=10.1038/scientificamerican0989-180}} {{closed access}}</ref> [[रूडी रूकर]] कहानी को इस प्रकार बताते हैं:


== सापेक्ष बनाम पूर्ण दीमक ==
{{quote|ड्यूडनी की रिपोर्ट है कि, तुर्क के प्राणियों के लिए एक नाम की खोज  में, उन्होंने सोचा, "ठीक है, वे तुर्क द्वारा अध्ययन की गई ट्यूरिंग मशीनें हैं, इसलिए उन्हें ट्यूर-कुछ होना चाहिए। और वे छोटे कीड़े, या घुन की तरह हैं, इसलिए मैं' मैं उन्हें टर-माइट्स कहूंगा! और यह दीमकों जैसा लगता है!" तुर्क और ड्यूडनी की अनुमति से, मैं हाइफ़न को छोड़ रहा हूँ, और उन्हें दीमक कहूँगा।|रूडी रूकर|कृत्रिम जीवन प्रयोगशाला<ref name="rucker" />}}


हल्दी को सापेक्ष या निरपेक्ष के रूप में वर्गीकृत किया जा सकता है। सापेक्ष दीमक, जिसे वैकल्पिक रूप से टर्निंग मशीन के रूप में जाना जाता है, में एक आंतरिक अभिविन्यास होता है। लैंग्टन की चींटी ऐसा ही एक उदाहरण है। सापेक्ष दीमक, परिभाषा के अनुसार, [[ समदैशिक ]] हैं; दीमक को घुमाने से इसके परिणाम पर कोई प्रभाव नहीं पड़ता है। रिलेटिव टर्माईट्स का नाम इसलिए रखा गया है क्योंकि दिशाओं को वर्तमान अभिविन्यास के सापेक्ष एन्कोड किया गया है, जो बाएँ या पीछे शब्दों के उपयोग के बराबर है। तुलनात्मक रूप से, निरपेक्ष दीमक अपनी दिशाओं को निरपेक्ष रूप से कूटबद्ध करते हैं: एक विशेष निर्देश दीमक को उत्तर की ओर बढ़ने का निर्देश दे सकता है। एब्सोल्यूट टर्माइट पारंपरिक ट्यूरिंग मशीनों के द्वि-आयामी एनालॉग हैं, इसलिए कभी-कभी इन्हें केवल द्वि-आयामी ट्यूरिंग मशीनों के रूप में जाना जाता है। इस लेख का शेष भाग संबंधित मामले से संबंधित है।
== सापेक्ष बनाम एब्सोल्यूट टरमिट ==
 
टरमिट को सापेक्ष या निरपेक्ष के रूप में वर्गीकृत किया जा सकता है। सापेक्ष टरमिट, जिसे वैकल्पिक रूप से टर्निंग मशीन के रूप में जाना जाता है, में एक आंतरिक अभिविन्यास होता है। लैंग्टन की आंट ऐसा ही एक उदाहरण है। सापेक्ष टरमिट, परिभाषा के अनुसार, [[ समदैशिक |समदैशिक]] हैं; टरमिट को घुमाने से इसके परिणाम पर कोई प्रभाव नहीं पड़ता है। रिलेटिव टर्माईट्स का नाम इसलिए रखा गया है क्योंकि दिशाओं को वर्तमान अभिविन्यास के सापेक्ष एन्कोड किया गया है, जो बाएँ या पीछे शब्दों के उपयोग के सामान है। तुलनात्मक रूप से, निरपेक्ष टरमिट अपनी दिशाओं को निरपेक्ष रूप से कूटबद्ध करते हैं: एक विशेष निर्देश टरमिट को उत्तर की ओर बढ़ने का निर्देश दे सकता है। एब्सोल्यूट टर्माइट पारंपरिक ट्यूरिंग मशीनों के द्वि-आयामी एनालॉग हैं, इसलिए कभी-कभी इन्हें केवल द्वि-आयामी ट्यूरिंग मशीनों के रूप में जाना जाता है। इस लेख का शेष भाग संबंधित स्थिति से संबंधित है।


== विशिष्टता ==
== विशिष्टता ==
निम्नलिखित विशिष्टता द्वि-आयामी वर्ग ग्रिड पर दीमक के लिए विशिष्ट है, जो दीमक का सबसे अधिक अध्ययन किया जाने वाला प्रकार है। अन्य ग्रिडों पर हल्दी को इसी तरह से निर्दिष्ट किया जा सकता है।
निम्नलिखित विशिष्टता द्वि-आयामी वर्ग ग्रिड पर टरमिट के लिए विशिष्ट है, जो टरमिट का सबसे अधिक अध्ययन किया जाने वाला प्रकार है। अन्य ग्रिडों पर टरमिट को इसी तरह से निर्दिष्ट किया जा सकता है।


लैंग्टन की चींटी की तरह, दीमक प्रत्येक टाइमस्टेप पर निम्नलिखित कार्य करते हैं:
लैंग्टन की आंट की तरह, टरमिट प्रत्येक टाइमस्टेप पर निम्नलिखित कार्य करते हैं:


# मौके पर मुड़ें (90° के कुछ गुणक द्वारा)
# मौके पर मुड़ें (90° के कुछ गुणक द्वारा)
Line 25: Line 26:
# एक वर्ग आगे बढ़ें.
# एक वर्ग आगे बढ़ें.


ट्यूरिंग मशीनों की तरह, क्रियाओं को एक [[राज्य संक्रमण तालिका]] द्वारा निर्दिष्ट किया जाता है जिसमें टरमाइट की वर्तमान आंतरिक स्थिति और उस सेल का रंग सूचीबद्ध होता है जिस पर वह वर्तमान में खड़ा है। उदाहरण के लिए, इस पृष्ठ के शीर्ष पर छवि में दिखाया गया टर्माइट निम्नलिखित तालिका द्वारा निर्दिष्ट है:
ट्यूरिंग मशीनों की तरह, क्रियाओं को एक [[राज्य संक्रमण तालिका|स्थान संक्रमण तालिका]] द्वारा निर्दिष्ट किया जाता है जिसमें टरमाइट की वर्तमान आंतरिक स्थिति और उस सेल का रंग सूचीबद्ध होता है जिस पर वह वर्तमान में खड़ा है। उदाहरण के लिए, इस पृष्ठ के शीर्ष पर छवि में दिखाया गया टर्माइट निम्नलिखित तालिका द्वारा निर्दिष्ट है:


{| class="wikitable" style="text-align:center"
{| class="wikitable" style="text-align:center"
! rowspan="3" colspan="2" |
! rowspan="3" colspan="2" |
! colspan="6" | Current color
! colspan="6" |वर्तमान कलर
|-
|-
! colspan="3" | 0
! colspan="3" | 0
! colspan="3" | 1
! colspan="3" | 1
|- style="font-size:9pt"
|- style="font-size:9pt"
! Write color
!कलर लिखें
! Turn
!मोड़
! Next state
!अगली अवस्था
! Write color
!कलर लिखें
! Turn
!मोड़
! Next state
!अगली अवस्था
|-
|-
! rowspan="2" | Current state
! rowspan="2" | वर्तमान अवस्था
! 0
! 0
| 1
| 1
Line 62: Line 63:
== उदाहरण ==
== उदाहरण ==


<गैलरी कैप्शन= वर्गाकार टाइलिंग पर दो-अवस्था वाले दो-रंग वाले दीमक के उदाहरण, सभी एक खाली कॉन्फ़िगरेशन से शुरू होते हैं: >
'''<गैलरी कैप्शन= वर्गाकार टाइलिंग पर दो-अवस्था वाले दो-रंग वाले टरमिट के उदाहरण, सभी एक रिक्त कॉन्फ़िगरेशन से प्रारंभ होते हैं: >'''
File:Turmite-111180121010-12536.svg|सर्पिल वृद्धि.
File:Turmite-111180121010-12536.svg|सर्पिल वृद्धि.
File:Turmite-121021110111-27731.svg|अराजक विकास की अवधि के बाद एक राजमार्ग का उत्पादन।
File:Turmite-121021110111-27731.svg|अराजक विकास की अवधि के पश्चात् एक राजमार्ग का उत्पादन।
File:Turmite-121181121020-65932.svg|एक विशिष्ट बनावट के साथ अराजक विकास।
File:Turmite-121181121020-65932.svg|एक विशिष्ट बनावट के साथ अराजक विकास।
File:Turmite-180121020081-223577.svg|एक विस्तारित फ्रेम के अंदर एक विशिष्ट बनावट के साथ विकास।
File:Turmite-180121020081-223577.svg|एक विस्तारित फ्रेम के अंदर एक विशिष्ट बनावट के साथ विकास।
Line 70: Line 71:
File:Turmite creating a growing diamond.png|बढ़ते हीरे का निर्माण
File:Turmite creating a growing diamond.png|बढ़ते हीरे का निर्माण
</गैलरी>
</गैलरी>
<गैलरी कैप्शन= अधिक राज्यों और रंगों के साथ और गैर-वर्ग ग्रिड पर दीमक के उदाहरण: >
<गैलरी कैप्शन= अधिक राज्यों और रंगों के साथ और गैर-वर्ग ग्रिड पर टरमिट के उदाहरण: >
File:Turmite_Snowflake.jpg|तीन-अवस्था वाला दो-रंग का टरमीट बर्फ के टुकड़े जैसा [[ भग्न ]] पैटर्न पैदा करता है।
File:Turmite_Snowflake.jpg|तीन-अवस्था वाला दो-रंग का टरमीट बर्फ के टुकड़े जैसा [[ भग्न |भग्न]] पैटर्न पैदा करता है।
File:Hexagonal turmite.svg|[[ षटकोणीय टाइलिंग ]] पर तीन-रंग की तीन-अवस्था वाली टर्माइट, लगभग 194150 कदमों के बाद एक आवधिक लूप में फंसने से पहले एक विशिष्ट बनावट के साथ अव्यवस्थित रूप से बढ़ रही है।
File:Hexagonal turmite.svg|[[ षटकोणीय टाइलिंग | षटकोणीय टाइलिंग]] पर तीन-रंग की तीन-अवस्था वाली टर्माइट, लगभग 194150 कदमों के पश्चात् एक आवधिक लूप में फंसने से पहले एक विशिष्ट बनावट के साथ अव्यवस्थित रूप से बढ़ रही है।
</गैलरी>
</गैलरी>


खाली ग्रिड या अन्य कॉन्फ़िगरेशन से शुरू करके, सबसे आम तौर पर देखे जाने वाले व्यवहार अराजक विकास, सर्पिल विकास और 'राजमार्ग' निर्माण हैं। कुछ निश्चित चरणों के बाद दुर्लभ उदाहरण आवधिक हो जाते हैं।
रिक्त ग्रिड या अन्य कॉन्फ़िगरेशन से प्रारंभ करके, सबसे समान्य रूप पर देखे जाने वाले व्यवहार अराजक विकास, सर्पिल विकास और 'राजमार्ग' निर्माण हैं। कुछ निश्चित चरणों के पश्चात् दुर्लभ उदाहरण आवधिक हो जाते हैं।


== [[व्यस्त बीवर]] गेम ==
== [[व्यस्त बीवर|बिजी बीवर]] गेम ==


एलन एच. ब्रैडी ने टर्मिनेटिंग टर्माइट (बिजी बीवर के समतुल्य) की खोज की और एक 2-स्टेट 2-रंग मशीन पाई जो रुकने से पहले 37 1 प्रिंट करती थी, और दूसरी मशीन जो रुकने से पहले 121 कदम चलती थी।<ref name="Brady95" />उन्होंने उन दीमकों पर भी विचार किया जो त्रिकोणीय टाइलिंग पर चलते हैं, यहां भी कई व्यस्त ऊदबिलाव पाए गए।
एलन एच. ब्रैडी ने टर्मिनेटिंग टर्माइट (बिजी बीवर के समतुल्य) की खोज की और एक 2-स्टेट 2-रंग मशीन पाई जो रुकने से पहले 37 1 प्रिंट करती थी, और दूसरी मशीन जो रुकने से पहले 121 कदम चलती थी।<ref name="Brady95" /> उन्होंने उन दीमकों पर भी विचार किया जो त्रिकोणीय टाइलिंग पर चलते हैं, और यहां भी अनेक बिजी बीवर खोजते हैं।


एड पेग, जूनियर ने व्यस्त बीवर गेम के लिए एक और दृष्टिकोण पर विचार किया। उन्होंने ऐसे दीमकों का सुझाव दिया जो उदाहरण के लिए बाएँ और दाएँ दोनों ओर मुड़ सकते हैं, दो भागों में विभाजित हो सकते हैं। बाद में मिलने वाली हल्दी एक दूसरे को नष्ट कर देती हैं। इस प्रणाली में, एक व्यस्त बीवर वह है जो एक ही दीमक के शुरुआती पैटर्न से सबसे लंबे समय तक चलता है, इससे पहले कि सभी दीमक एक-दूसरे को नष्ट कर दें।<ref>{{cite web | last = Pegg, Jr. | first = Ed | title = गणित पहेली| url=http://www.mathpuzzle.com/26Mar03.html | access-date = 15 October 2009}}</ref>
एड पेग, जूनियर ने बिजी बीवर गेम के लिए एक और दृष्टिकोण पर विचार किया गया था। उन्होंने ऐसे दीमकों का सुझाव दिया जो उदाहरण के लिए बाएँ और दाएँ दोनों ओर मुड़ सकते हैं, जो दो भागों में विभाजित हो सकते हैं। इसक पश्चात् में मिलने वाली टरमिट एक दूसरे को नष्ट कर देती हैं। इस सिस्टम में, एक बिजी बीवर वह है जो एक ही टरमिट के प्रारंभिक पैटर्न से सबसे लंबे समय तक चलता है, इससे पहले कि सभी टरमिट एक-दूसरे को नष्ट कर देता है।<ref>{{cite web | last = Pegg, Jr. | first = Ed | title = गणित पहेली| url=http://www.mathpuzzle.com/26Mar03.html | access-date = 15 October 2009}}</ref>




== अन्य ग्रिड ==
== अन्य ग्रिड                                             ==


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


==यह भी देखें==
==यह भी देखें==
*{{annotated link|Cellular automaton}}
*सेलुलर ऑटोमेटन
*{{annotated link|Langton's ant}}
*लैंग्टन की आंट
*{{annotated link|Paterson's worms}}
*पैटर्सन के कीड़े 


== संदर्भ ==
== संदर्भ                                                                                                                                               ==
<references />
<references />


Line 105: Line 106:
* [https://gollygang.github.io/ruletablerepository/downloads/Turmites.zip Golly script for generating arbitrary turmites]
* [https://gollygang.github.io/ruletablerepository/downloads/Turmites.zip Golly script for generating arbitrary turmites]
* [https://github.com/GollyGang/ruletablerepository/wiki/TwoDimensionalTuringMachines Absolute- and relative-movement Turmites and Busy Beavers on square, cubic, triangular and hexagonal grids]
* [https://github.com/GollyGang/ruletablerepository/wiki/TwoDimensionalTuringMachines Absolute- and relative-movement Turmites and Busy Beavers on square, cubic, triangular and hexagonal grids]
[[Category: कृत्रिम जीवन]] [[Category: गणना के मॉडल]] [[Category: सेलुलर ऑटोमेटन नियम]] [[Category: ट्यूरिंग मशीन]]


[[Category: Machine Translated Page]]
[[Category:Articles with hatnote templates targeting a nonexistent page]]
[[Category:Commons category link is locally defined]]
[[Category:Created On 25/07/2023]]
[[Category:Created On 25/07/2023]]
[[Category:Lua-based templates]]
[[Category:Machine Translated Page]]
[[Category:Pages with script errors]]
[[Category:Short description with empty Wikidata description]]
[[Category:Templates Vigyan Ready]]
[[Category:Templates that add a tracking category]]
[[Category:Templates that generate short descriptions]]
[[Category:Templates using TemplateData]]
[[Category:कृत्रिम जीवन]]
[[Category:गणना के मॉडल]]
[[Category:ट्यूरिंग मशीन]]
[[Category:सेलुलर ऑटोमेटन नियम]]

Latest revision as of 14:42, 11 August 2023

Not to be confused with दीमक.
एक वर्गाकार ग्रिड पर 2-अवस्था 2-रंग की दीरमाइट। एक रिक्त ग्रिड से शुरू करके, 8342 चरणों के पश्चात् टर्माइट (एक लाल पिक्सेल) ने अराजक और नियमित गति दोनों चरणों का प्रदर्शन किया है।

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

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

इतिहास

लैंग्टन की चींटियों का आविष्कार 1986 में किया गया था और इन्हें ट्यूरिंग मशीनों के समकक्ष घोषित किया गया था।[1] स्वतंत्र रूप से, 1988 में, एलन एच. ब्रैडी ने एक अभिविन्यास के साथ द्वि-आयामी ट्यूरिंग मशीनों के विचार पर विचार किया और उन्हें टर्निंग मशीनें कहा जाता है।[2][3]

वास्तविक रूप से इन दोनों से मुक्त रूप से,[4] ग्रेग तुर्क ने इसी तरह की सिस्टम की जांच की और उनके बारे में ए.के. ड्यूडनी को लिखा है। ए.के. ड्यूडनी ने 1989 में अमेरिकी वैज्ञानिक में अपने कंप्यूटर रिक्रिएशन्स कॉलम में उन्हें टर-माइट्स नाम दिया है।[5] रूडी रूकर कहानी को इस प्रकार बताते हैं:

ड्यूडनी की रिपोर्ट है कि, तुर्क के प्राणियों के लिए एक नाम की खोज में, उन्होंने सोचा, "ठीक है, वे तुर्क द्वारा अध्ययन की गई ट्यूरिंग मशीनें हैं, इसलिए उन्हें ट्यूर-कुछ होना चाहिए। और वे छोटे कीड़े, या घुन की तरह हैं, इसलिए मैं' मैं उन्हें टर-माइट्स कहूंगा! और यह दीमकों जैसा लगता है!" तुर्क और ड्यूडनी की अनुमति से, मैं हाइफ़न को छोड़ रहा हूँ, और उन्हें दीमक कहूँगा।

— रूडी रूकर, कृत्रिम जीवन प्रयोगशाला[4]

सापेक्ष बनाम एब्सोल्यूट टरमिट

टरमिट को सापेक्ष या निरपेक्ष के रूप में वर्गीकृत किया जा सकता है। सापेक्ष टरमिट, जिसे वैकल्पिक रूप से टर्निंग मशीन के रूप में जाना जाता है, में एक आंतरिक अभिविन्यास होता है। लैंग्टन की आंट ऐसा ही एक उदाहरण है। सापेक्ष टरमिट, परिभाषा के अनुसार, समदैशिक हैं; टरमिट को घुमाने से इसके परिणाम पर कोई प्रभाव नहीं पड़ता है। रिलेटिव टर्माईट्स का नाम इसलिए रखा गया है क्योंकि दिशाओं को वर्तमान अभिविन्यास के सापेक्ष एन्कोड किया गया है, जो बाएँ या पीछे शब्दों के उपयोग के सामान है। तुलनात्मक रूप से, निरपेक्ष टरमिट अपनी दिशाओं को निरपेक्ष रूप से कूटबद्ध करते हैं: एक विशेष निर्देश टरमिट को उत्तर की ओर बढ़ने का निर्देश दे सकता है। एब्सोल्यूट टर्माइट पारंपरिक ट्यूरिंग मशीनों के द्वि-आयामी एनालॉग हैं, इसलिए कभी-कभी इन्हें केवल द्वि-आयामी ट्यूरिंग मशीनों के रूप में जाना जाता है। इस लेख का शेष भाग संबंधित स्थिति से संबंधित है।

विशिष्टता

निम्नलिखित विशिष्टता द्वि-आयामी वर्ग ग्रिड पर टरमिट के लिए विशिष्ट है, जो टरमिट का सबसे अधिक अध्ययन किया जाने वाला प्रकार है। अन्य ग्रिडों पर टरमिट को इसी तरह से निर्दिष्ट किया जा सकता है।

लैंग्टन की आंट की तरह, टरमिट प्रत्येक टाइमस्टेप पर निम्नलिखित कार्य करते हैं:

  1. मौके पर मुड़ें (90° के कुछ गुणक द्वारा)
  2. वर्ग का रंग बदलें
  3. एक वर्ग आगे बढ़ें.

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

वर्तमान कलर
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]


अन्य ग्रिड

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

यह भी देखें

  • सेलुलर ऑटोमेटन
  • लैंग्टन की आंट
  • पैटर्सन के कीड़े

संदर्भ

  1. ↑ 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.
  2. ↑ 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. ↑ 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. ↑ 4.0 4.1 Rucker, Rudy. "कृत्रिम जीवन प्रयोगशाला". Retrieved October 16, 2009.
  5. ↑ 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. closed access
  6. ↑ Pegg, Jr., Ed. "गणित पहेली". Retrieved 15 October 2009.


बाहरी संबंध

Wikimedia Commons has media related to Turmite.
Retrieved from ‘https://www.vigyanwiki.in/index.php?title=टरमिट&oldid=244997’