सेलुलर ऑटोमेटा के बारे में थोड़ा सा

पहले से ही एक कई पर - कई - कई बार खेल "जीवन" के बारे में लिखा। अभी हाल ही में, लोबाचेव्स्की विमान पर एक अद्भुत लेख Life था । लेकिन खेल "जीवन" तथाकथित का एक विशेष मामला है। सेलुलर ऑटोमेटा । कई अन्य सेलुलर ऑटोमेटा हैं जो लाइफ गेम से पूरी तरह से अलग हैं, लेकिन फिर भी बहुत दिलचस्प हैं। मैं उनमें से कुछ के बारे में यहां बात करना चाहता हूं।

शुरू करने के लिए, हम कोशिकाओं की एक श्रृंखला पर विचार करते हैं, जिसमें एक के अलावा, शून्य होते हैं:

  ... 0 1 0 0 0 0 0 0 ... 

निम्नलिखित नियम पर विचार करें, इस संख्या के योग के साथ सेल में नंबर को बदलें और बाईं ओर पड़ोसी। हम राज्यों की निम्नलिखित श्रृंखला प्राप्त करते हैं:

 ... 0 1 0 0 0 0 0 0 ...
 ... 0 1 1 0 0 0 0 0 ...
 ... 0 1 2 1 0 0 0 0 ...
 ... 0 1 3 3 1 0 0 0 ...
 ... 0 1 4 6 4 1 0 0 ...
 ... 0 1 5 10 10 5 1 0 ...
 ... 0 1 6 15 20 15 6 1 ...

यह देखना मुश्किल नहीं है कि यह पास्कल का त्रिकोण है। और अब, सामान्य जोड़ के बजाय, हम जोड़ मोडुलो दो का उपयोग करेंगे। यह ज्ञात है (और यहां तक ​​कि हाल ही में वर्णित है स्रास्टिंस्की ट्राइंगल और पास्कल ट्रायंगल ) जिसमें हमें सीरपिन्स्की त्रिकोण का असतत एनालॉग मिलता है:

 ... 0 1 0 0 0 0 0 0 ...
 ... 0 1 1 0 0 0 0 0 ...
 ... 0 1 0 1 0 0 0 0 ...
 ... 0 1 1 1 1 0 0 0 ...
 ... 0 1 0 0 0 1 1 0 0 ...
 ... 0 1 1 0 0 1 1 0 ...
 ... 0 1 0 1 0 0 1 0 1 ...

रुचि रखते हैं? पर पढ़ें!


सेलुलर ऑटोमेटन की सटीक परिभाषा देने का कोई मतलब नहीं है, लेकिन सेलुलर ऑटोमेटा के निम्नलिखित गुणों पर ध्यान देना उपयोगी है: समानता , स्थानीयता और समरूपता । समानांतरवाद का अर्थ है कि सभी कोशिकाओं के अपडेट एक-दूसरे से स्वतंत्र रूप से होते हैं। स्थानीयता से अभिप्राय यह है कि कोशिका की नई अवस्था केवल कोशिका की पुरानी स्थिति और उसके परिवेश पर निर्भर करती है। और अंत में, एकरूपता का मतलब है कि सभी कोशिकाओं को समान नियमों के अनुसार अपडेट किया गया है।

अनंत ग्रिड के साथ गड़बड़ न करने के लिए, हम सेलुलर ऑटोमेटा को एक परिमित चतुष्कोणीय ग्रिड पर विचार करेंगे, और ताकि सीमाओं के साथ कोई समस्या न हो, हम ग्रिड को एक टोरस में लपेटते हैं। सेल के दो पड़ोसों के व्यक्तिगत नाम हैं: यह मूर का पड़ोस है - आसपास के सभी आठ सेल पड़ोसी हैं, और वॉन न्यूमैन के पड़ोस - केवल बाईं ओर, दाईं ओर, ऊपर और नीचे के निकटतम सेल पड़ोसी हैं। अस्पष्टता से बचने के लिए, सेल के राज्य को बदलने के लिए नियम के मौखिक विवरण के अलावा, फ़ंक्शन का कार्यान्वयन भी दिया जाएगा।

int transformCell( int northWestCell, int northCell, int northEastCell, int westCell, int centerCell, int eastCell, int southWestCell, int southCell, int southEastCell); 

सीमित और असीमित वृद्धि

तो, कोशिकाओं को दो राज्यों में हो सकता है: 0 - मृत, और 1 - जीवित।
निम्नलिखित नियम पर विचार करें: यदि कोई सेल अपने पड़ोसियों में से कम से कम एक जीवित है, तो वह जीवित हो जाता है; एक बार एक कोशिका जीवित हो गई है, यह हमेशा जीवित रहती है। मूर के पड़ोस के मामले में, transformCell() की बॉडी होगी:

 int sum = northWestCell + northCell + northEastCell + westCell + eastCell + southWestCell + southCell + southEastCell; if (sum > 0) { return 1; } else { return centerCell; } 

यदि फ़ील्ड को शुरू में शून्य से भर दिया जाता है, तो जीवित कोशिकाएं दिखाई नहीं देंगी, लेकिन यदि कोशिकाओं में से एक को जीवित किया जाता है, तो जीवित कोशिकाओं का एक बढ़ता वर्ग इस "भ्रूण" से उत्पन्न होगा, जो अंततः क्षेत्र को भर देगा। इस मामले में, जीवित कोशिकाओं का क्षेत्र उच्चतम संभव गति से बढ़ता है - प्रकाश की गति।


हम ऊपर दिए गए नियम को थोड़ा बदल देते हैं: इस शर्त के बजाय "पड़ोसियों में से कम से कम एक जीवित है", हम इस शर्त पर विचार करते हैं कि "पड़ोसी में से कोई एक जीवित है"।

 int sum = northWestCell + northCell + northEastCell + westCell + eastCell + southWestCell + southCell + southEastCell; if (sum == 1) { return 1; } else { return centerCell; } 

एक सेल से प्राप्त संरचना, सबसे पहले, बहुत दुर्लभ, और, दूसरी बात, एक स्पष्ट भग्न चरित्र होगी।


मूर पड़ोस के बजाय, हम वॉन न्यूमैन पड़ोस पर विचार कर सकते हैं:

 int sum = northCell + westCell + eastCell + southCell; if (sum == 1) { return 1; } else { return centerCell; } 

चक्रीय सेलुलर ऑटोमेटा

डेविड ग्रिफिथ द्वारा चक्रीय सेलुलर ऑटोमेटा का आविष्कार किया गया था। एक सेल n अवस्थाओं में हो सकती है, जिसे हम संख्याओं 0, 1, ..., n - 1. द्वारा कहेंगे। हम कहते हैं कि राज्य m राज्य k के बगल में है यदि m + 1 = k (mod n )। राज्य एम से एक सेल अगले राज्य के पास जाता है केवल तभी पड़ोसी कोशिकाओं में से एक राज्य के । उदाहरण के लिए, एक वॉन न्यूमैन पड़ोस के मामले में, परिवर्तन इस प्रकार लिखा गया है:

 int nextState = (centerCell + 1) % statesNumber; if (northCell == nextState || westCell == nextState || eastCell == nextState || southCell == nextState) { return nextState; } else { return centerCell; } 

इसके अलावा, यदि आप एक बेतरतीब ढंग से भरे क्षेत्र से शुरू करते हैं, तो तीन अलग-अलग चरणों का अवलोकन किया जा सकता है। पहला चरण एक यादृच्छिक क्षेत्र है। फिर रंगीन क्षेत्र दिखाई देने लगते हैं जो अनियमित रूप से भरे क्षेत्रों को अवशोषित करेंगे। ये ब्लॉक अपना रंग बदलने के लिए "लहर" करेंगे। फिर सर्पिल होते हैं, जिन्हें दानव भी कहा जाता है । और अंत में, तीसरे चरण में, मैदान राक्षसों द्वारा भस्म हो जाएगा।





आप एक आयामी चक्रीय सेलुलर ऑटोमोबोन पर भी विचार कर सकते हैं:

 int transformCell(int leftCell, int centerCell, int rightCell) { int nextState = (centerCell + 1) % statesNumber; if (nextState == leftCell || nextState == rightCell) { return nextState; } else { return centerCell; } } 

यदि आप अधिक विवरण सीखने में रुचि रखते हैं, तो मैं विकिपीडिया चक्रीय सेलुलर ऑटोमेटन के साथ शुरुआत करने की सलाह देता हूं।

हैश

सेल को फिर से 0, 1, ..., n - 1 राज्यों में होने दें।
तीन-भाग नियम पर विचार करें।

स्वास्थ्य। यदि कोई कोशिका 0 (यानी, स्वस्थ) अवस्था में है, तो यह बीमार हो जाता है अगर उसके कई पड़ोसी बीमार हैं (यानी, एक शून्य-शून्य स्थिति में हैं)।

वसूली । यदि सेल राज्य n - 1 में है, तो यह स्व-उपचार करता है और राज्य 0 में जाता है।

रोग । अन्यथा, कोशिका की स्थिति की गणना पड़ोसी कोशिकाओं के राज्यों के औसत और कुछ स्थिर के रूप में की जाती है। (यदि परिणामी संख्या n - 1 से अधिक है, तो नया राज्य n - 1. होगा)

 int sum = northWestCell + northCell + northEastCell + westCell + eastCell + southWestCell + southCell + southEastCell; if (centerCell == 0) { if (sum < 5) { return 0; } else if (sum < 100) { return 2; } else { return 3; } } else if (centerCell == statesNumber - 1) { return 0; } else { return Math.min(sum / 8 + 5, statesNumber - 1); } 

यह ध्यान दिया जाता है कि इस तरह से प्राप्त तरंग जैसी प्रक्रियाएं बेलौसोव-ज़बोटिन्स्की की प्रतिक्रिया से मिलती जुलती हैं।

शिराओं की सतह

यह नियम (और साथ ही पिछले एक) मुझे सेलब मैनुअल में मिला। प्रत्येक कोशिका राज्य में 0, 1, 2 या 4 है। नियम का रूप है:

 if (centerCell == 0) { return 2 * ((northWestCell % 2) ^ (northEastCell % 2)) + northCell % 2; } else if (centerCell == 1) { return 2 * ((northWestCell % 2) ^ (southWestCell % 2)) + westCell % 2; } else if (centerCell == 2) { return 2 * ((southWestCell % 2) ^ (southEastCell % 2)) + southCell % 2; } else { return 2 * ((southEastCell % 2) ^ (northEastCell % 2)) + eastCell % 2; } 

यदि आप एक बेतरतीब ढंग से भरे क्षेत्र से शुरू करते हैं, तो दो "प्रवाह" एक दूसरे में दुर्घटनाग्रस्त हो जाते हैं: ऊर्ध्वाधर और क्षैतिज। कुछ समय बाद, "प्रवाह" में से एक प्रबल होना शुरू हो जाता है। और अंत में, केवल एक ही रहता है।





यह सेलुलर ऑटोमेटा का एक छोटा सा हिस्सा है जिसके बारे में मैं बात करना चाहता था, लेकिन मुझे रोकना होगा ताकि लेख बहुत बड़ा न हो जाए। उन लोगों के लिए जो कुछ लिंक देंगे:

(1) टी। टोफोली, एन। मार्गोलस, सेल्युलर ऑटोमेटा की मशीनें , एम।, मीर, 1991।

(२) एम। श्रोएडर, फ्रैक्टल्स, अराजकता, बिजली कानून। एंडलेस पैराडाइज , इज़ेव्स्क, आरएचडी, 2001, पीपी 469--490 से लघुचित्र।

(३) आर। रूकर, जे। वाकर सेलब मैनुअल ।