Блоктық ұялы автоматтар: физикалық ережелерді сақтау және кері қайтымдылық
Block cellular automaton
Блоктық ұялы автоматтар – физикалық үлгілеуге арналған, блоктар бойынша ереже қолданылатын ерекше автоматтар. Маргалус аймағы негізгі схема болып табылады.
Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Ұялы автоматтың түрі
Kind of cellular automaton
Блоктық ұялы автомат немесе бөлгіштік ұялы автомат – ұялы торлардың бір-біріне қабаттаспайтын блоктарға бөлінетін (әр түрлі уақыт қадамдарында әртүрлі бөлістермен) және ауысу ережесінің жеке клеткаға емес, бүкіл блокқа бірден қолданылатын ерекше түрі. Блоктық ұялы автоматтар физикалық шамаларды модельдеу үшін пайдалы, себебі кері қайтымдылық және сақталу заңдары сияқты физикалық шектеулерді сақтайтын ауысу ережелерін таңдау оңай.
A block cellular automaton or partitioning cellular automaton is a special kind of cellular automaton in which the lattice of cells is divided into non overlapping blocks (with different partitions at different time steps) and the transition rule is applied to a whole block at a time rather than a single cell. Block cellular automata are useful for simulations of physical quantities, because it is straightforward to choose transition rules that obey physical constraints such as reversibility and conservation laws.
Көршіліктер
Ең қарапайым бөлу схемасы, әлдебір Марголус аймағы болуы мүмкін, бұл атау Норман Марголусқа байланысты, ол осы аймақ құрылымын қолдана отырып, блоктық жасуша автоматтарының алғашқы зерттеушісі болды. Марголус аймағында тор 2 жасушалық блокқа (немесе екі өлшемде 2 × 2 квадраттарға, немесе үш өлшемде 2 × 2 × 2 кубтарға және т.б.) бөлінеді. Бұл блоктар бір жасушаға (әр өлшем бойынша) кезекті уақыт қадамдарында жылдырылады. К. Морита мен М. Хараоға тиесілі ұқсас техника, әр жасушаны шектеулі бөліктерге бөлуден тұрады, мұнда әр бөлік белгілі бір көршіге арналған. Эволюция көршілес бөліктерді алмастыру арқылы және содан кейін әр жасушаға жасушаның күйіне ғана байланысты (көрші жасушалардың күйіне емес) таза жергілікті түрлендіруді қолдану арқылы жүзеге асырылады. Мұндай құрылымдық схемамен, егер жергілікті түрлендіру өзі биекция болса, жасушалық автоматтың қайтымдылығы кепілдендіріледі. Бұл техниканы әрбір үлкен жасушаның бөліктерінен құралған ұсақ жасушалардың торындағы блоктық жасушалық автомат ретінде қарастыруға болады; осы ұсақ тордың блоктары бір үлкен жасушадағы бөліктер жиынтығы мен бір-бірімен бөліктерді бөлісетін көрші жасушалардағы бөліктер жиынтығы арасында ауысып отырады.
The simplest partitioning scheme is probably the Margolus neighborhood, named after Norman Margolus, who first studied block cellular automata using this neighborhood structure. In the Margolus neighborhood, the lattice is divided into 2 cell blocks (or 2 × 2 squares in two dimensions, or 2 × 2 × 2 cubes in three dimensions, etc.) which are shifted by one cell (along each dimension) on alternate timesteps. A closely related technique due to K. Morita and M. Harao consists in partitioning each cell into a finite number of parts, each part being devoted to some neighbor. The evolution proceeds by exchanging the corresponding parts between neighbors and then applying on each cell a purely local transformation depending only on the state of the cell (and not on the states of its neighbors). With such a construction scheme, the cellular automaton is guaranteed to be reversible if the local transformation is itself a bijection. This technique may be viewed as a block cellular automaton on a finer lattice of cells, formed by the parts of each larger cell; the blocks of this finer lattice alternate between the sets of parts within a single large cell and the sets of parts in neighboring cells that share parts with each other.
Қайта қалпына келтіру және сақтау
Әрбір блоктың даму ережесі қайтымды болғанша, бүкіл автоматтың дамуы да қайтымды болады. Одан да күштірек айтқанда, бұл жағдайда автоматтың уақыт бойынша кері жүрген мінез-құлқы да блоктық жасушалық автомат ретінде сипатталуы мүмкін, бұл ретте ол бірдей блок құрылымымен және әрбір блок ішінде бастапқы автоматтың ережесін керітетін ауысу ережесімен анықталады. Керісі де дұрыс: егер блоктар жеке-жеке қайтымды болмаса, жаһандық даму қайтымды бола алмайды: егер бір блоктан екі түрлі бастапқы жағдай – x және y – бірдей нәтижелі жағдайға z-ға әкелсе, онда бір блокта x орналасқан жаһандық жағдай, бір қадамнан кейін x-ті y-мен алмастырған жағдайдан ажыратылмайды. Яғни, жасушалық автомат жаһандық деңгейде қайтымды болу үшін, міндетті түрде блок деңгейінде де қайтымды болуы керек. Кез келген қайтымды жасушалық автоматты көптеген күйлермен қайтымды блоктық жасушалық автомат арқылы модельдеуге болады; алайда, блоксыз жасушалық автоматтар үшін қайтымдылықтың шешілмейтін мәселесіне байланысты, модельдеудегі блоктарға сәйкес келетін блоксыз автоматтағы аймақтардың радиусы үшін есептеліп шығарылатын шек жоқ, сондай-ақ блоксыз ережені блок ережесіне аудару да есептеліп шығарылмайды. Блоктық жасушалық автоматтар – қайталанатындықтан басқа, бөлшектер санын сақтау, импульсті сақтау сияқты заңдарды іске асыратын ережелерді жобалау үшін де ыңғайлы құрал болып табылады. Мысалы, егер әрбір блок ішіндегі ереже сол блоктан тірі жасушалардың санын сақтаса, онда автоматтың жаһандық дамуы да сол санды сақтайды. Бұл қасиет жасушалық автоматтарды физикалық модельдеуде қолдану үшін өте пайдалы.
As long as the rule for evolving each block is reversible, the entire automaton will also be. More strongly, in this case, the time reversed behavior of the automaton can also be described as a block cellular automaton, with the same block structure and with a transition rule that inverts the original automaton's rule within each block. The converse is also true: if the blocks are not individually reversible, the global evolution cannot be reversible: if two different configurations x and y of a block lead to the same result state z, then a global configuration with x in one block would be indistinguishable after one step from the configuration in which the x is replaced by y. That is, a cellular automaton is reversible globally if and only if it is reversible at the block level. Any reversible cellular automaton may be simulated by a reversible block cellular automaton with a larger number of states; however, because of the undecidability of reversibility for non block cellular automata, there is no computable bound on the radius of the regions in the non block automaton that correspond to blocks in the simulation, and the translation from a non block rule to a block rule is also not computable. Block cellular automata are also a convenient formalism in which to design rules that, in addition to reversibility, implement conservation laws such as the conservation of particle number, conservation of momentum, etc For instance, if the rule within each block preserves the number of live cells in the block, then the global evolution of the automaton will also preserve the same number. This property is useful in the applications of cellular automata to physical simulation.
Трон
"Трон" ережесінде ауысу функциясы әрбір блокты өзгеріссіз қалдырады, тек оның барлық төрт ұяшығы бірдей күйде болған жағдайда ғана, олардың күйлері кері өзгереді. Бұл ережені тірі жасушалардың тіктөртбұрышты пішіндегі бастапқы шарттарынан немесе ұқсас қарапайым тік сызықты пішіндерден іске қосу күрделі тікбұрышты үлгілерге алып келеді. Тоффоли мен Марголус бұл ережені кез келген Марголус маңайындағы блоктық жасушалық автоматты асинхронды жасушалық автоматты пайдалану арқылы модельдеуге мүмкіндік беретін жергілікті синхрондау ережесін жүзеге асыру үшін де қолдануға болатынын айтады. Бұл модельдеуде асинхронды автоматтың әрбір ұяшығы модельделетін автоматтың күйін және сол ұяшықтың уақыт белгісінің жұптығын көрсететін екінші битті сақтайды; демек, нәтижедегі асинхронды автоматтың күйлері модельделетін автоматтан екі есе көп. Уақыт белгілерінің арасындағы айырмашылық ең көп дегенде бірге тең болуы керек, ал төрт ұяшықтың кез келген блогы, егер олардың уақыт белгілерінің бәрі дұрыс жұптыққа ие болса, модельделетін блок ережесіне сәйкес жаңартылуы мүмкін. Мұндай жаңартулар орындалғанда, уақыт белгілерінің жұптығы да "Трон" ережесіне сәйкес жаңартылуы керек, бұл көршілес уақыт белгілеріне қатысты шектеуді міндетті түрде сақтайды. Осылайша жергілікті жаңартуларды орындау арқылы асинхронды автоматтағы әрбір жасушаның эволюциясы модельделетін синхронды блоктық автоматтағы эволюциясына сәйкес келеді.
In the "Tron" rule, the transition function leaves each block unchanged except when all four of its cells have the same state, in which case their states are all reversed. Running this rule from initial conditions in the form of a rectangle of live cells, or from similar simple straight edged shapes, leads to complex rectilinear patterns. Toffoli and Margolus also suggest that this rule can be used to implement a local synchronization rule that allows any Margolus neighborhood block cellular automaton to be simulated using an asynchronous cellular automaton. In this simulation, each cell of an asynchronous automaton stores both a state for the simulated automaton and a second bit representing the parity of a timestamp for that cell; therefore, the resulting asynchronous automaton has twice as many states as the automaton it simulates. The timestamps are constrained to differ by at most one between adjacent cells, and any block of four cells whose timestamps all have the correct parity may be updated according to the block rule being simulated. When an update of this type is performed, the timestamp parities should also be updated according to the Tron rule, which necessarily preserves the constraint on adjacent timestamps. By performing local updates in this way, the evolution of each cell in the asynchronous automaton is identical to its evolution in the synchronous block automaton being simulated.