दूसरे क्रम का सेलुलर ऑटोमेटन
दूसरे क्रम का सेल्युलर ऑटोमेटन एक प्रकार का प्रतिवर्ती सेल्युलर ऑटोमेटन (सीए) है जिसका आविष्कार एडवर्ड फ्रेडकिन ने किया था।[1][2] जहां समय t पर एक सेल की स्थिति न केवल समय t − 1 पर उसके निकटता पर निर्भर करती है किंतु उसके समय t − 2 पर बताया गया है।[3]
सामान्य तकनीक
सामान्य रूप से दूसरे क्रम के ऑटोमेटन के विकास नियम को एक फ़ंक्शन f के रूप में वर्णित किया जा सकता है जो सेल के निकट को ऑटोमेटन की स्थिति पर क्रमपरिवर्तन के लिए मैप करता है। प्रत्येक समय चरण 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] चूँकि परिणामी दूसरे क्रम का ऑटोमेटन समान्यत: उस साधारण सीए से बहुत कम समानता रखता है जिससे इसका निर्माण किया गया था। इस तरह से बनाए गए दूसरे क्रम के नियमों को आधार नियम की संख्या या वोल्फ्राम कोड में "R" जोड़कर स्टीफन वोल्फ्राम द्वारा नाम दिया गया है।[3]
अनुप्रयोग
दूसरे क्रम के ऑटोमेटा का उपयोग बिलियर्ड-बॉल कंप्यूटरों[1] और सांख्यिकीय यांत्रिकी में लौहचुंबकत्व के आइसिंग मॉडल का अनुकरण करने के लिए किया जा सकता है[2][4] इनका उपयोग क्रिप्टोग्राफी के लिए भी किया जा सकता है।[5]
संदर्भ
- ↑ Jump up to: 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.
- ↑ Jump up to: 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.
- ↑ Jump up to: 3.0 3.1 Wolfram, Stephen (2002), A New Kind of Science, Wolfram Media, pp. 437–440, 452, ISBN 1-57955-008-8.
- ↑ Jump up to: 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.
