दूसरे क्रम का सेलुलर ऑटोमेटन: Difference between revisions
No edit summary |
No edit summary |
||
| Line 3: | Line 3: | ||
[[Image:CARuleComparison18-18R.png|thumb|200px|right|प्राथमिक सीए नियम 18 (बाएं) और इसका दूसरे क्रम का समकक्ष नियम 18आर (दाएं)। समय नीचे की ओर चलता है। अपरिवर्तनीय नियम में ऊपर/नीचे असममित त्रिभुजों पर ध्यान दें।]] | [[Image:CARuleComparison18-18R.png|thumb|200px|right|प्राथमिक सीए नियम 18 (बाएं) और इसका दूसरे क्रम का समकक्ष नियम 18आर (दाएं)। समय नीचे की ओर चलता है। अपरिवर्तनीय नियम में ऊपर/नीचे असममित त्रिभुजों पर ध्यान दें।]] | ||
दूसरे क्रम का सेल्युलर ऑटोमेटन एक प्रकार का प्रतिवर्ती सेल्युलर ऑटोमेटन (सीए) है जिसका आविष्कार एडवर्ड फ्रेडकिन ने किया था।<ref name="m84">{{citation|first=N.|last=Margolus|authorlink=Norman Margolus|title=Physics-like models of computation|journal=Physica D|volume=10|year=1984|pages=81–95|doi=10.1016/0167-2789(84)90252-5}}. Reprinted in {{citation|editor-first=Stephen|editor-last=Wolfram|editor-link=Stephen Wolfram|title=Theory and Applications of Cellular Automata|series=Advanced series on complex systems|volume=1|publisher=World Scientific|year=1986|pages=232–246}}.</ref><ref name="vichniac">{{citation|title=Simulating physics with cellular automata|journal=Physica D|first=G.|last=Vichniac|volume=10|year=1984|pages=96–115|doi=10.1016/0167-2789(84)90253-7}}.</ref> जहां समय {{math|''t''}} पर एक सेल की स्थिति न केवल समय {{math|''t'' − 1}} पर उसके निकट पर निर्भर करती है किंतु उसके समय {{math|''t'' − 2}} पर बताया गया है।<ref name="nkos">{{citation|last=Wolfram|first=Stephen|authorlink=Stephen Wolfram|year=2002|title=[[A New Kind of Science]]|pages=[https://archive.org/details/newkindofscience00wolf/page/437 437–440, 452]|publisher=Wolfram Media|isbn=1-57955-008-8}}.</ref> | |||
==सामान्य तकनीक== | |||
सामान्य रूप से दूसरे क्रम के ऑटोमेटन के विकास नियम को एक फ़ंक्शन एफ के रूप में वर्णित किया जा सकता है जो सेल के निकट को ऑटोमेटन की स्थिति पर क्रमपरिवर्तन के लिए मैप करता है। प्रत्येक समय चरण t में, ऑटोमेटन के प्रत्येक सेल c के लिए, क्रमपरिवर्तन σc देने के लिए इस फ़ंक्शन को c के निकट पर प्रयुक्त किया जाता है। फिर, यह क्रमपरिवर्तन σc समय t - 1 पर सेल c की स्थिति पर प्रयुक्त होता है, और परिणाम समय t + 1 पर सेल की स्थिति है। इस तरह, प्रत्येक समय चरण पर ऑटोमेटन के कॉन्फ़िगरेशन की गणना की जाती है पिछले दो समय चरण: ठीक पिछला चरण उन क्रमपरिवर्तनों को निर्धारित करता है जो कोशिकाओं पर प्रयुक्त होते हैं, और उससे पहले का समय चरण उन अवस्थाओं को बताता है जिन पर ये क्रमपरिवर्तन संचालित होते हैं।<ref name="tm90">{{citation|first1=Tommaso|last1=Toffoli|author1-link=Tommaso Toffoli|first2=Norman|last2=Margolus|author2-link=Norman Margolus|title=Invertible cellular automata|journal=Physica D|volume=45|year=1990|pages=229–253|doi=10.1016/0167-2789(90)90185-r}}. See especially section 5.4 "Second-order cellular automata", pp. 238–240. This issue of Physica D was reprinted as {{citation|title=Cellular Automata: Theory and Experiment|editor-first=Howard|editor-last=Gutowitz|publisher=MIT/North-Holland|year=1991}}. | |||
</ref> | |||
दूसरे क्रम के ऑटोमेटन के विपरीत समय की गतिशीलता को उसी निकट के साथ दूसरे दूसरे क्रम के ऑटोमेटन द्वारा वर्णित किया जा सकता है, जिसमें फ़ंक्शन g निकट को क्रमपरिवर्तन के लिए मैप करने से f को विपरीत क्रमपरिवर्तन देता है। अर्थात्, प्रत्येक संभावित निकट N, f(N) और g(N) पर व्युत्क्रम क्रमपरिवर्तन होना चाहिए। इस विपरीत नियम के साथ, फ़ंक्शन g द्वारा वर्णित ऑटोमेटन समय t और ''t'' + 1 पर कॉन्फ़िगरेशन से समय ''t'' − 1 पर कॉन्फ़िगरेशन की सही रूप से गणना करता है। क्योंकि प्रत्येक दूसरे क्रम के ऑटोमेटन को इस तरह से विपरीत किया जा सकता है, यह इस प्रकार है कि वे सभी हैं प्रतिवर्ती सेलुलर ऑटोमेटा, इस पर ध्यान दिए बिना कि ऑटोमेटन नियम निर्धारित करने के लिए कौन सा फ़ंक्शन f चुना गया है। | दूसरे क्रम के ऑटोमेटन के विपरीत समय की गतिशीलता को उसी निकट के साथ दूसरे दूसरे क्रम के ऑटोमेटन द्वारा वर्णित किया जा सकता है, जिसमें फ़ंक्शन g निकट को क्रमपरिवर्तन के लिए मैप करने से f को विपरीत क्रमपरिवर्तन देता है। अर्थात्, प्रत्येक संभावित निकट N, f(N) और g(N) पर व्युत्क्रम क्रमपरिवर्तन होना चाहिए। इस विपरीत नियम के साथ, फ़ंक्शन g द्वारा वर्णित ऑटोमेटन समय t और ''t'' + 1 पर कॉन्फ़िगरेशन से समय ''t'' − 1 पर कॉन्फ़िगरेशन की सही रूप से गणना करता है। क्योंकि प्रत्येक दूसरे क्रम के ऑटोमेटन को इस तरह से विपरीत किया जा सकता है, यह इस प्रकार है कि वे सभी हैं प्रतिवर्ती सेलुलर ऑटोमेटा, इस पर ध्यान दिए बिना कि ऑटोमेटन नियम निर्धारित करने के लिए कौन सा फ़ंक्शन f चुना गया है। | ||
==दो-अवस्था ऑटोमेटा के लिए == | ==दो-अवस्था ऑटोमेटा के लिए == | ||
यदि एक सेलुलर ऑटोमेटन में केवल दो | यदि एक सेलुलर ऑटोमेटन में केवल दो अवस्था हैं, तो राज्यों के केवल दो संभावित क्रमपरिवर्तन भी हैं: पहचान क्रमपरिवर्तन जो प्रत्येक अवस्था को स्वयं में मैप करता है, और क्रमपरिवर्तन जो प्रत्येक अवस्था को दूसरे अवस्था में मैप करता है। हम इन दो क्रमपरिवर्तनों को ऑटोमेटन की दो अवस्थाओं के साथ पहचान सकते हैं। इस तरह, प्रत्येक दूसरे क्रम का सेलुलर ऑटोमेटन (निकट से क्रमपरिवर्तन तक एक फ़ंक्शन द्वारा परिभाषित) विशिष्ट रूप से एक सामान्य (प्रथम-क्रम) सेलुलर ऑटोमेटन से मेल खाता है, जो सीधे निकट से राज्यों तक एक फ़ंक्शन द्वारा परिभाषित होता है।<ref name="tm90"/> दो-अवस्था द्वितीय-क्रम ऑटोमेटा समय विपरीत के अनुसार सममित हैं: ऑटोमेटन की समय-विपरीत गतिशीलता को मूल गतिशीलता के समान नियम के साथ अनुकरण किया जा सकता है। | ||
यदि हम दोनों अवस्थाओं को बूलियन मानों के रूप में देखते हैं, तो साधारण और दूसरे क्रम के ऑटोमेटन के बीच इस पत्राचार को सरलता से वर्णित किया जा सकता है: समय {{math|''t'' + 1}} पर दूसरे क्रम के ऑटोमेटन के एक सेल की स्थिति अनन्य है या समय {{math|''t'' − 1}} पर इसकी स्थिति है। इस नियम के साथ कि सामान्य सेलुलर ऑटोमेटन नियम इसकी गणना करेगा।<ref name="tm90" /> वास्तव में, सभी दो- | यदि हम दोनों अवस्थाओं को बूलियन मानों के रूप में देखते हैं, तो साधारण और दूसरे क्रम के ऑटोमेटन के बीच इस पत्राचार को सरलता से वर्णित किया जा सकता है: समय {{math|''t'' + 1}} पर दूसरे क्रम के ऑटोमेटन के एक सेल की स्थिति अनन्य है या समय {{math|''t'' − 1}} पर इसकी स्थिति है। इस नियम के साथ कि सामान्य सेलुलर ऑटोमेटन नियम इसकी गणना करेगा।<ref name="tm90" /> वास्तव में, सभी दो-अवस्था दूसरे क्रम के नियमों को इस तरह से तैयार किया जा सकता है।<ref name="m84"/> चूँकि परिणामी दूसरे क्रम का ऑटोमेटन समान्यत: उस साधारण सीए से बहुत कम समानता रखता है जिससे इसका निर्माण किया गया था। इस तरह से बनाए गए दूसरे क्रम के नियमों को आधार नियम की संख्या या वोल्फ्राम कोड में "आर" जोड़कर स्टीफन वोल्फ्राम द्वारा नाम दिया गया है।<ref name="nkos"/> | ||
==अनुप्रयोग | ==अनुप्रयोग == | ||
दूसरे क्रम के ऑटोमेटा का उपयोग बिलियर्ड-बॉल कंप्यूटरों<ref name="m84"/> और सांख्यिकीय यांत्रिकी में लौहचुंबकत्व के आइसिंग मॉडल का अनुकरण करने के लिए किया जा सकता है<ref name="vichniac" /><ref name="tm90"/> इनका उपयोग क्रिप्टोग्राफी के लिए भी किया जा सकता है।<ref>{{citation | दूसरे क्रम के ऑटोमेटा का उपयोग बिलियर्ड-बॉल कंप्यूटरों<ref name="m84"/> और सांख्यिकीय यांत्रिकी में लौहचुंबकत्व के आइसिंग मॉडल का अनुकरण करने के लिए किया जा सकता है<ref name="vichniac" /><ref name="tm90"/> इनका उपयोग क्रिप्टोग्राफी के लिए भी किया जा सकता है।<ref>{{citation | ||
Revision as of 09:28, 11 August 2023
दूसरे क्रम का सेल्युलर ऑटोमेटन एक प्रकार का प्रतिवर्ती सेल्युलर ऑटोमेटन (सीए) है जिसका आविष्कार एडवर्ड फ्रेडकिन ने किया था।[1][2] जहां समय t पर एक सेल की स्थिति न केवल समय t − 1 पर उसके निकट पर निर्भर करती है किंतु उसके समय t − 2 पर बताया गया है।[3]
सामान्य तकनीक
सामान्य रूप से दूसरे क्रम के ऑटोमेटन के विकास नियम को एक फ़ंक्शन एफ के रूप में वर्णित किया जा सकता है जो सेल के निकट को ऑटोमेटन की स्थिति पर क्रमपरिवर्तन के लिए मैप करता है। प्रत्येक समय चरण t में, ऑटोमेटन के प्रत्येक सेल c के लिए, क्रमपरिवर्तन σc देने के लिए इस फ़ंक्शन को c के निकट पर प्रयुक्त किया जाता है। फिर, यह क्रमपरिवर्तन σc समय t - 1 पर सेल c की स्थिति पर प्रयुक्त होता है, और परिणाम समय t + 1 पर सेल की स्थिति है। इस तरह, प्रत्येक समय चरण पर ऑटोमेटन के कॉन्फ़िगरेशन की गणना की जाती है पिछले दो समय चरण: ठीक पिछला चरण उन क्रमपरिवर्तनों को निर्धारित करता है जो कोशिकाओं पर प्रयुक्त होते हैं, और उससे पहले का समय चरण उन अवस्थाओं को बताता है जिन पर ये क्रमपरिवर्तन संचालित होते हैं।[4]
दूसरे क्रम के ऑटोमेटन के विपरीत समय की गतिशीलता को उसी निकट के साथ दूसरे दूसरे क्रम के ऑटोमेटन द्वारा वर्णित किया जा सकता है, जिसमें फ़ंक्शन g निकट को क्रमपरिवर्तन के लिए मैप करने से f को विपरीत क्रमपरिवर्तन देता है। अर्थात्, प्रत्येक संभावित निकट N, f(N) और g(N) पर व्युत्क्रम क्रमपरिवर्तन होना चाहिए। इस विपरीत नियम के साथ, फ़ंक्शन g द्वारा वर्णित ऑटोमेटन समय t और t + 1 पर कॉन्फ़िगरेशन से समय t − 1 पर कॉन्फ़िगरेशन की सही रूप से गणना करता है। क्योंकि प्रत्येक दूसरे क्रम के ऑटोमेटन को इस तरह से विपरीत किया जा सकता है, यह इस प्रकार है कि वे सभी हैं प्रतिवर्ती सेलुलर ऑटोमेटा, इस पर ध्यान दिए बिना कि ऑटोमेटन नियम निर्धारित करने के लिए कौन सा फ़ंक्शन f चुना गया है।
दो-अवस्था ऑटोमेटा के लिए
यदि एक सेलुलर ऑटोमेटन में केवल दो अवस्था हैं, तो राज्यों के केवल दो संभावित क्रमपरिवर्तन भी हैं: पहचान क्रमपरिवर्तन जो प्रत्येक अवस्था को स्वयं में मैप करता है, और क्रमपरिवर्तन जो प्रत्येक अवस्था को दूसरे अवस्था में मैप करता है। हम इन दो क्रमपरिवर्तनों को ऑटोमेटन की दो अवस्थाओं के साथ पहचान सकते हैं। इस तरह, प्रत्येक दूसरे क्रम का सेलुलर ऑटोमेटन (निकट से क्रमपरिवर्तन तक एक फ़ंक्शन द्वारा परिभाषित) विशिष्ट रूप से एक सामान्य (प्रथम-क्रम) सेलुलर ऑटोमेटन से मेल खाता है, जो सीधे निकट से राज्यों तक एक फ़ंक्शन द्वारा परिभाषित होता है।[4] दो-अवस्था द्वितीय-क्रम ऑटोमेटा समय विपरीत के अनुसार सममित हैं: ऑटोमेटन की समय-विपरीत गतिशीलता को मूल गतिशीलता के समान नियम के साथ अनुकरण किया जा सकता है।
यदि हम दोनों अवस्थाओं को बूलियन मानों के रूप में देखते हैं, तो साधारण और दूसरे क्रम के ऑटोमेटन के बीच इस पत्राचार को सरलता से वर्णित किया जा सकता है: समय t + 1 पर दूसरे क्रम के ऑटोमेटन के एक सेल की स्थिति अनन्य है या समय t − 1 पर इसकी स्थिति है। इस नियम के साथ कि सामान्य सेलुलर ऑटोमेटन नियम इसकी गणना करेगा।[4] वास्तव में, सभी दो-अवस्था दूसरे क्रम के नियमों को इस तरह से तैयार किया जा सकता है।[1] चूँकि परिणामी दूसरे क्रम का ऑटोमेटन समान्यत: उस साधारण सीए से बहुत कम समानता रखता है जिससे इसका निर्माण किया गया था। इस तरह से बनाए गए दूसरे क्रम के नियमों को आधार नियम की संख्या या वोल्फ्राम कोड में "आर" जोड़कर स्टीफन वोल्फ्राम द्वारा नाम दिया गया है।[3]
अनुप्रयोग
दूसरे क्रम के ऑटोमेटा का उपयोग बिलियर्ड-बॉल कंप्यूटरों[1] और सांख्यिकीय यांत्रिकी में लौहचुंबकत्व के आइसिंग मॉडल का अनुकरण करने के लिए किया जा सकता है[2][4] इनका उपयोग क्रिप्टोग्राफी के लिए भी किया जा सकता है।[5]
संदर्भ
- ↑ 1.0 1.1 1.2 Margolus, N. (1984), "Physics-like models of computation", Physica D, 10: 81–95, doi:10.1016/0167-2789(84)90252-5. Reprinted in Wolfram, Stephen, ed. (1986), Theory and Applications of Cellular Automata, Advanced series on complex systems, vol. 1, World Scientific, pp. 232–246.
- ↑ 2.0 2.1 Vichniac, G. (1984), "Simulating physics with cellular automata", Physica D, 10: 96–115, doi:10.1016/0167-2789(84)90253-7.
- ↑ 3.0 3.1 Wolfram, Stephen (2002), A New Kind of Science, Wolfram Media, pp. 437–440, 452, ISBN 1-57955-008-8.
- ↑ 4.0 4.1 4.2 4.3 Toffoli, Tommaso; Margolus, Norman (1990), "Invertible cellular automata", Physica D, 45: 229–253, doi:10.1016/0167-2789(90)90185-r. See especially section 5.4 "Second-order cellular automata", pp. 238–240. This issue of Physica D was reprinted as Gutowitz, Howard, ed. (1991), Cellular Automata: Theory and Experiment, MIT/North-Holland.
- ↑ Chai, Zhenchuan; Cao, Zhenfu; Zhou, Yuan (2005), "Encryption based on reversible second-order cellular automata", Parallel and Distributed Processing and Applications (ISPA 2005 Workshops), Lecture Notes in Computer Science, Springer, pp. 350–358, doi:10.1007/11576259_39.
