Жасушалық автоматтар: Дискретті есептеу моделі

Кіріспе

Компьютерлік ғылымда зерттелген дискретті модель. Ұялы автомат (көпше түрі: ұялы автоматтары, аббревиатурасы: CA) – автоматтар теориясында зерттелетін дискретті есептеу моделі. Ұялы автоматтар ұялы кеңістіктер, теселлациялық автоматтар, гомогенді құрылымдар, ұялы құрылымдар, теселлациялық құрылымдар және итерациялық тізімдер деп те аталады. Ұялы автоматтар физика, теориялық биология және микроқұрылымдарды модельдеу сияқты әртүрлі салаларда қолданыс тапқан. Ұялы автоматта жасушалардың реттелген торы болады, олардың әрқайсысы шекті сандағы күйлердің бірінде болады, мысалы, қосулы және өшірулі (қосастырылған карталар торынан өзгеше). Тор кез келген шекті өлшемде болуы мүмкін. Әр жасуша үшін, оның көршілесі деп аталатын жасушалар жиынтығы, берілген жасушаға қатысты анықталады. Бастапқы күй (t = 0 уақыты) әр жасушаға күй тағайындау арқылы таңдалады. Жаңа буын жасалады (t 1-ге артырылады), белгілі бір тұрақты ережеге (әдетте математикалық функция) сәйкес, әр жасушаның жаңа күйі оның ағымдағы күйі және оның көршілерінің күйлеріне қарай анықталады. Әдетте, жасуша күйін жаңарту ережесі әр жасуша үшін бірдей және уақыт өте келе өзгермейді, сондай-ақ бүкіл торға бір мезгілде қолданылады, бірақ ерекшеліктері бар, мысалы, стохастикалық ұялы автомат және асинхронды ұялы автомат. Бұл тұжырым 1940 жылдары Станислав Улам мен Джон фон Нейман Лос-Аламос Ұлттық зертханасында бірге жұмыс істеген кезде ашқан. 1950-1960 жылдары кейбір ғалымдар зерттегенімен, 1970 жылдары және Конвейдің «Өмір» ойыны, екі өлшемді ұялы автомат, тақырыпқа қызығушылық академиялық қауымдастықтың шегінен шықты. 1980 жылдары Стивен Вольфрам бір өлшемді ұялы автоматтарды, яки ол «элементарлық ұялы автоматтар» деп атағандарын, жүйелі түрде зерттеді; оның ғылыми көмекшісі Мэтью Кук осы ережелердің бірінің Тьюринг толық екенін көрсетті. Вольфрам ұсынған ұялы автоматтардың негізгі жіктелуі біріншіден төртіншіге дейін нөмірленеді. Олар, ретімен, үлгілердің әдетте біртектілікке қалыптасатын автоматтары, үлгілердің көбінесе тұрақты немесе тербелісті құрылымдарға айналатын автоматтары, үлгілердің көріне хаотикалық түрде дамитын автоматтары және үлгілердің өте күрделі болып, тұрақты жергілікті құрылымдармен ұзақ уақытқа созылатын автоматтары. Осы соңғы сынып есептеу жағынан әмбебап, яки Тьюринг машинасының симуляциясын жасауға қабілетті деп саналады. Ұялы автоматтардың ерекше түрлері кері айналатын (бір конфигурация тікелей келесі бір конфигурацияға әкелетін) және тоталистік (жеке жасушаның болашақ мәні тек көрші жасушалар тобының жалпы мәніне байланысты болатын) болып бөлінеді. Ұялы автоматтар нақты әлемдегі әртүрлі жүйелерді, соның ішінде биологиялық және химиялық жүйелерді модельдей алады.

Discrete model studied in computer science

A cellular automaton (pl. cellular automata, abbrev. CA) is a discrete model of computation studied in automata theory. Cellular automata are also called cellular spaces, tessellation automata, homogeneous structures, cellular structures, tessellation structures, and iterative arrays. Cellular automata have found application in various areas, including physics, theoretical biology and microstructure modeling. A cellular automaton consists of a regular grid of cells, each in one of a finite number of states, such as on and off (in contrast to a coupled map lattice). The grid can be in any finite number of dimensions. For each cell, a set of cells called its neighborhood is defined relative to the specified cell. An initial state (time t = 0) is selected by assigning a state for each cell. A new generation is created (advancing t by 1), according to some fixed rule (generally, a mathematical function) that determines the new state of each cell in terms of the current state of the cell and the states of the cells in its neighborhood. Typically, the rule for updating the state of cells is the same for each cell and does not change over time, and is applied to the whole grid simultaneously, though exceptions are known, such as the stochastic cellular automaton and asynchronous cellular automaton. The concept was originally discovered in the 1940s by Stanislaw Ulam and John von Neumann while they were contemporaries at Los Alamos National Laboratory. While studied by some throughout the 1950s and 1960s, it was not until the 1970s and Conway's Game of Life, a two dimensional cellular automaton, that interest in the subject expanded beyond academia. In the 1980s, Stephen Wolfram engaged in a systematic study of one dimensional cellular automata, or what he calls elementary cellular automata; his research assistant Matthew Cook showed that one of these rules is Turing complete. The primary classifications of cellular automata, as outlined by Wolfram, are numbered one to four. They are, in order, automata in which patterns generally stabilize into homogeneity, automata in which patterns evolve into mostly stable or oscillating structures, automata in which patterns evolve in a seemingly chaotic fashion, and automata in which patterns become extremely complex and may last for a long time, with stable local structures. This last class is thought to be computationally universal, or capable of simulating a Turing machine. Special types of cellular automata are reversible, where only a single configuration leads directly to a subsequent one, and totalistic, in which the future value of individual cells only depends on the total value of a group of neighboring cells. Cellular automata can simulate a variety of real world systems, including biological and chemical ones.

Шолу

Екі өлшемді жасушалық автоматты модельдеудің бір жолы – шексіз графикалық қағаз парағы мен жасушалардың іс-әрекеті үшін ережелер жиынтығын пайдалану. Әрбір шаршы “жасуша” деп аталады және әрбір жасушаның екі мүмкін күйі бар: қара және ақ. Жасушаның маңы – жақын орналасқан, әдетте, іргелес жасушалар. Маңның ең көп таралған екі түрі – фон Нейман және Мур маңдары. Алғашқысы, жасушалық автоматтар теориясын қалаған ғалымның атымен аталып, төрт ортогональды іргелес жасушадан тұрады. Осылайша, Мур маңы бар екі өлшемді жүйеде мүмкін автоматтардың жалпы саны 229, немесе 1.34 болады. Әдетте, ғаламдағы барлық жасушалар бірдей күйде басталады, тек шектеулі сандағы жасушалар басқа күйде болады; күйлерді тағайындау конфигурация деп аталады. Көбінесе, ғалам бастапқыда периодтық үлгімен жабылған деп есептеледі, ал тек шектеулі сандағы жасушалар осы үлгіні бұзады. Соңғы болжам бір өлшемді жасушалық автоматтарда жиі кездеседі. Жасушалық автоматтар көбінесе шексіз емес, шекті торда модельделеді. Екі өлшемде ғалам шексіз жазықтық емес, тіктөртбұрыш болып келеді. Шекті тордың негізгі мәселесі – шеттегі жасушаларды қалай өңдеу. Оларды өңдеу әдісі тордағы барлық жасушалардың мәніне әсер етеді. Мүмкін болатын әдістердің бірі – осы жасушалардағы мәндерді өзгеріссіз қалдыру. Тағы бір әдіс – осы жасушалар үшін маңды басқаша анықтау. Олардың азырақ көршілері бар деуге болады, бірақ сонда шеттегі жасушалар үшін жаңа ережелерді анықтау қажет. Мұндай жасушалар көбінесе периодтық шекаралық шарттармен өңделеді, нәтижесінде тороидтік құрылым пайда болады: жоғарыдан шыққанда төменгі жақтағы сәйкес позициядан кіреді, ал сол жақтан шыққанда оң жақтан кіреді. (Бұл, негізінен, шексіз периодтық мозаиканы модельдеу, ал жекеше дифференциалдық теңдеулер саласында бұл кейде периодтық шекаралық шарттар деп аталады.) Бұл тіктөртбұрыштың сол және оң жиектерін түтіктей біріктіру, содан кейін түтіктің жоғарғы және төменгі жиектерін торга (қолшатыр пішіні) біріктіру арқылы көруге болады. Басқа өлшемдердегі ғаламдар да осылай өңделеді. Бұл маңмен байланысты шекаралық мәселелерді шешеді, бірақ тағы бір артықшылығы – оны модулдік арифметикалық функцияларды пайдалану арқылы оңай бағдарламалауға болады. Мысалы, төмендегі мысалдардағыдай бір өлшемді жасушалық автоматта жасушаның маңы {xi−1t−1, xit−1, xi+1t−1} болады, мұнда t – уақыт қадамы (тік), ал i – бір буынның индексі (көлденең).

One way to simulate a two dimensional cellular automaton is with an infinite sheet of graph paper along with a set of rules for the cells to follow. Each square is called a "cell" and each cell has two possible states, black and white. The neighborhood of a cell is the nearby, usually adjacent, cells. The two most common types of neighborhoods are the von Neumann neighborhood and the Moore neighborhood. The former, named after the founding cellular automaton theorist, consists of the four orthogonally adjacent cells. Thus, in the two dimensional system with a Moore neighborhood, the total number of automata possible would be 229, or 1.34. It is usually assumed that every cell in the universe starts in the same state, except for a finite number of cells in other states; the assignment of state values is called a configuration. More generally, it is sometimes assumed that the universe starts out covered with a periodic pattern, and only a finite number of cells violate that pattern. The latter assumption is common in one dimensional cellular automata. Cellular automata are often simulated on a finite grid rather than an infinite one. In two dimensions, the universe would be a rectangle instead of an infinite plane. The obvious problem with finite grids is how to handle the cells on the edges. How they are handled will affect the values of all the cells in the grid. One possible method is to allow the values in those cells to remain constant. Another method is to define neighborhoods differently for these cells. One could say that they have fewer neighbors, but then one would also have to define new rules for the cells located on the edges. These cells are usually handled with periodic boundary conditions resulting in a toroidal arrangement: when one goes off the top, one comes in at the corresponding position on the bottom, and when one goes off the left, one comes in on the right. (This essentially simulates an infinite periodic tiling, and in the field of partial differential equations is sometimes referred to as periodic boundary conditions.) This can be visualized as taping the left and right edges of the rectangle to form a tube, then taping the top and bottom edges of the tube to form a torus (doughnut shape). Universes of other dimensions are handled similarly. This solves boundary problems with neighborhoods, but another advantage is that it is easily programmable using modular arithmetic functions. For example, in a 1 dimensional cellular automaton like the examples below, the neighborhood of a cell xit is {xi−1t−1, xit−1, xi+1t−1}, where t is the time step (vertical), and i is the index (horizontal) in one generation.

Тарих

1940 жылдары Лос-Аламос ұлттық зертханасында жұмыс істеген кезде Станислав Улам қарапайым тор желісін модель ретінде қолдана отырып, кристалдардың өсуін зерттеді. Сол уақытта Джон фон Нейман, Уламның Лос-Аламостағы әріптесі, өзін-өзі көбейтуге қабілетті жүйелер мәселесі бойынша жұмыс істеді. Фон Нейманның бастапқы дизайны бір роботтың екінші роботты құрастыру идеясына негізделген. Бұл дизайн кинематикалық модель деп аталады. Осы дизайнды дамытқанда фон Нейман өзін-өзі көбейтуге қабілетті роботты жасаудың қиындығын, сондай-ақ роботты құрастыру үшін қажетті "детальдар теңізін" қамтамасыз етудің жоғары құнын түсінді. Нейман 1948 жылы Хиксон симпозиумы үшін «Автоматтардың жалпы және логикалық теориясы» деген мақала жазды. Нильс Аалл Барричелли осы жасанды өмір модельдерін алғашқы зерттеулердің көптерін жүргізді. Улам мен фон Нейман 1950 жылдардың соңында сұйық қозғалысын есептеу әдісін жасады. Әдістің негізгі идеясы сұйықтықты дискретті бірліктер тобы ретінде қарастыру және әрбір бірліктің қозғалысын оның көршілерінің мінез-құлқына сүйене отырып есептеу болды. Осылайша жасушалық автоматтардың алғашқы жүйесі дүниеге келді. Уламның тор желісі сияқты, фон Нейманның жасушалық автоматтары да екі өлшемді, ал оның өзін-өзі көбейтуге қабілетті құрылғысы алгоритмдік түрде іске асырылған. Нәтижесінде кішкентай аумақтағы жасушалық автоматта жұмыс істейтін әмбебап көшіруші және құрастырушы пайда болды (тек жанасқан жасушалар ғана көршілер болып саналады; фон Нейманның жасушалық автоматтары үшін тек ортогоналды жасушалар), және әр жасушада 29 күй болды. Фон Нейман белгілі бір үлгінің берілген жасушалық әлемде өзін-өзі шексіз көшіре алатынын, 200 000 жасушадан тұратын конфигурацияны құру арқылы көрсетті. 1940 жылдары Норберт Винер мен Артуро Розенблуетт жасушалық автоматтың кейбір сипаттамаларына ие болған, қозғыш ортаның моделін жасады. Олардың нақты мақсаты жүрек жүйелеріндегі импульстің таралуының математикалық сипаттамасын беру болды. Алайда, олардың моделі жасушалық автомат емес, себебі сигналдар таралатын орта үздіксіз, ал толқын фронттары қисық сызықтар болып табылады. 1978 жылы J. M. Greenberg және S. P. Hastings қозғыш ортаның нағыз жасушалық автомат моделін жасап, зерттеді; Гринберг-Хастингс жасушалық автоматын қараңыз. Винер мен Розенблуеттің бастапқы еңбегінде көптеген маңызды ойлар бар және ол жүрек аритмиясы және қозғыш жүйелер туралы қазіргі заманғы ғылыми жарияланымдарда әлі де сілтеме жасалады. 1960 жылдары жасушалық автоматтар динамикалық жүйенің ерекше түрі ретінде зерттелді және алғаш рет символдық динамиканың математикалық саласымен байланыс орнатылды. 1969 жылы Густав А. Хедлунд осы көзқарас бойынша көптеген нәтижелерді жинақтады, ол әлі күнге дейін жасушалық автоматтарды математикалық зерттеу үшін маңызды еңбек ретінде саналады. Ең негізгі нәтиже – Curtis–Hedlund–Lyndon теоремасындағы жасушалық автоматтардың жаһандық ережелері жиынтығының ауысу кеңістіктерінің үздіксіз эндоморфизмдер жиынтығы ретінде сипатталуы. 1969 жылы неміс компьютерлік пионері Конрад Цузе өзінің «Есептеу кеңістігі» атты кітабын жариялады, онда ол ғаламның физикалық заңдары табиғатынан дискретті екендігін және бүкіл ғалам бір жасушалық автоматта детерминистік есептеудің нәтижесі екенін ұсынды; «Цузе теориясы» цифрлық физика деп аталатын зерттеу саласының негізіне айналды. Сондай-ақ 1969 жылы компьютерлік ғалым Алви Рей Смит «Жасушалық автоматтар теориясы» тақырыбында Стенфордтағы PhD диссертациясын аяқтады, бұл CA-ны компьютерлердің жалпы класы ретінде математикалық тұрғыдан қарастырудың алғашқы әрекеті болды. Осы диссертациядан көптеген мақалалар туды: Ол әртүрлі пішіндердегі көршіліктердің теңдігін, Мур көршілігін фон Нейман көршілігіне қалай азайтуды немесе кез келген көршілікті фон Нейман көршілігіне қалай азайтуды көрсетті. Ол екі өлшемді CA-ның есептеуде әмбебап екенін дәлелдеді, 1 өлшемді CA-ны енгізді және олардың да есептеуде әмбебап екенін, тіпті қарапайым көршіліктермен де көрсетті. Ол күрделі фон Нейманның құрылымдық әмбебаптылығын (осылайша өзін-өзі көбейтуге қабілетті машиналарды) есептеу әмбебаптығының салдары ретінде 1 өлшемді CA-да қалай қосу керектігін көрсетті. Ол фон Нейманның АЖ туралы кітабының неміс тіліндегі басылымына кіріспе ретінде жазды, онда он жылға жуық уақыт бойы көптеген елдердегі көптеген авторлардың жұмыстарына ондаған сілтемелер келтірілді, бірақ қазіргі АЖ зерттеушілері көбінесе назардан тыс қалдырады. 1970 жылдары «Өмір ойыны» деп аталатын екі өлшемді, екі күйлі жасушалық автомат кеңінен танымал болды, әсіресе алғашқы есептеу қауымдастығында. Джон Конвей ойлап тапқан және Мартин Гарднер «Scientific American» журналында танымал еткен, оның ережелері былай:
Кез келген тірі жасушаның екінен аз тірі көршісі болса, ол өледі, себебі халық азаюынан. Кез келген тірі жасушаның екі немесе үш тірі көршісі болса, ол келесі буынға көшеді. Кез келген тірі жасушаның үштен көп тірі көршісі болса, ол өледі, себебі халық тым көп болғандықтан. Кез келген өлі жасушаның дәл үш тірі көршісі болса, ол тірі жасушаға айналады, себебі көбеюден. Өте қарапайым болғанына қарамастан, жүйе күрделі мінез-құлқына ие, көрінетін кездейсоқтық пен тәртіп арасында ауытқиды. «Өмір ойынының» ең айқын ерекшеліктерінің бірі – глайдерлердің жиі кездесуі, жасушалардың тізімі, олар өзінің торы бойынша қозғалады. Автоматты глайдерлердің өзара әрекеттесуіне есептеулер орындау үшін орналастыруға болады, және көптеген күш-жігерден кейін «Өмір ойыны» әмбебап Тьюринг машинасының үлгісін жасай алатыны көрсетілді. Бұл көбінесе ойын-сауық тақырыбы ретінде қарастырылды және 1970 жылдардың басында «Өмір ойынының» және оған ұқсас бірнеше ережелердің ерекшеліктерін зерттеуден басқа көптеген қосымша жұмыстар жасалмады. Стивен Вольфрам 1981 жылдың ортасында жасушалық автоматтарды тәуелсіз түрде зерттеуге кірісті, себебі табиғаттағы күрделі үлгілердің қалыптасуын қарастырғанда, олар термодинамиканың екінші заңына қайшы келеді. Бұл қарапайым ережелердің күтпеген күрделілігі Вольфрамды табиғаттағы күрделілік ұқсас механизмдерге байланысты болуы мүмкін деген күмәнді ойға жетеледі және 110-шы ереженің әмбебап болуы мүмкін екенін ұсынды – бұл фактіні кейін Вольфрамның ассистенті Мэттью Кук 1990 жылдары дәлелдеді.

Stanislaw Ulam, while working at the Los Alamos National Laboratory in the 1940s, studied the growth of crystals, using a simple lattice network as his model. At the same time, John von Neumann, Ulam's colleague at Los Alamos, was working on the problem of self replicating systems. Von Neumann's initial design was founded upon the notion of one robot building another robot. This design is known as the kinematic model. As he developed this design, von Neumann came to realize the great difficulty of building a self replicating robot, and of the great cost in providing the robot with a "sea of parts" from which to build its replicant. Neumann wrote a paper entitled "The general and logical theory of automata" for the Hixon Symposium in 1948. Nils Aall Barricelli performed many of the earliest explorations of these models of artificial life. Ulam and von Neumann created a method for calculating liquid motion in the late 1950s. The driving concept of the method was to consider a liquid as a group of discrete units and calculate the motion of each based on its neighbors' behaviors. Thus was born the first system of cellular automata. Like Ulam's lattice network, von Neumann's cellular automata are two dimensional, with his self replicator implemented algorithmically. The result was a universal copier and constructor working within a cellular automaton with a small neighborhood (only those cells that touch are neighbors; for von Neumann's cellular automata, only orthogonal cells), and with 29 states per cell. Von Neumann gave an existence proof that a particular pattern would make endless copies of itself within the given cellular universe by designing a 200,000 cell configuration that could do so. Also in the 1940s, Norbert Wiener and Arturo Rosenblueth developed a model of excitable media with some of the characteristics of a cellular automaton. Their specific motivation was the mathematical description of impulse conduction in cardiac systems. However their model is not a cellular automaton because the medium in which signals propagate is continuous, and wave fronts are curves. A true cellular automaton model of excitable media was developed and studied by J. M. Greenberg and S. P. Hastings in 1978; see Greenberg Hastings cellular automaton. The original work of Wiener and Rosenblueth contains many insights and continues to be cited in modern research publications on cardiac arrhythmia and excitable systems. In the 1960s, cellular automata were studied as a particular type of dynamical system and the connection with the mathematical field of symbolic dynamics was established for the first time. In 1969, Gustav A. Hedlund compiled many results following this point of view in what is still considered as a seminal paper for the mathematical study of cellular automata. The most fundamental result is the characterization in the Curtis–Hedlund–Lyndon theorem of the set of global rules of cellular automata as the set of continuous endomorphisms of shift spaces. In 1969, German computer pioneer Konrad Zuse published his book Calculating Space, proposing that the physical laws of the universe are discrete by nature, and that the entire universe is the output of a deterministic computation on a single cellular automaton; "Zuse's Theory" became the foundation of the field of study called digital physics. Also in 1969 computer scientist Alvy Ray Smith completed a Stanford PhD dissertation on Cellular Automata Theory, the first mathematical treatment of CA as a general class of computers. Many papers came from this dissertation: He showed the equivalence of neighborhoods of various shapes, how to reduce a Moore to a von Neumann neighborhood or how to reduce any neighborhood to a von Neumann neighborhood. He proved that two dimensional CA are computation universal, introduced 1 dimensional CA, and showed that they too are computation universal, even with simple neighborhoods. He showed how to subsume the complex von Neumann proof of construction universality (and hence self reproducing machines) into a consequence of computation universality in a 1 dimensional CA. Intended as the introduction to the German edition of von Neumann's book on CA, he wrote a survey of the field with dozens of references to papers, by many authors in many countries over a decade or so of work, often overlooked by modern CA researchers. In the 1970s a two state, two dimensional cellular automaton named Game of Life became widely known, particularly among the early computing community. Invented by John Conway and popularized by Martin Gardner in a Scientific American article, its rules are as follows:
Any live cell with fewer than two live neighbours dies, as if caused by underpopulation. Any live cell with two or three live neighbours lives on to the next generation. Any live cell with more than three live neighbours dies, as if by overpopulation. Any dead cell with exactly three live neighbours becomes a live cell, as if by reproduction. Despite its simplicity, the system achieves an impressive diversity of behavior, fluctuating between apparent randomness and order. One of the most apparent features of the Game of Life is the frequent occurrence of gliders, arrangements of cells that essentially move themselves across the grid. It is possible to arrange the automaton so that the gliders interact to perform computations, and after much effort it has been shown that the Game of Life can emulate a universal Turing machine. It was viewed as a largely recreational topic, and little follow up work was done outside of investigating the particularities of the Game of Life and a few related rules in the early 1970s. Stephen Wolfram independently began working on cellular automata in mid 1981 after considering how complex patterns seemed formed in nature in violation of the Second Law of Thermodynamics. The unexpected complexity of the behavior of these simple rules led Wolfram to suspect that complexity in nature may be due to similar mechanisms. and suggested that rule 110 may be universal—a fact proved later by Wolfram's research assistant Matthew Cook in the 1990s.

Жіктеу

Вольфрам, «Ғылымның жаңа түрі» еңбегінде және 1980-ші жылдардың ортасына дейінгі бірнеше мақаласында, ұялы автоматтар мен басқа да бірнеше қарапайым есептеу модельдерін олардың мінез-құлқына байланысты бөлуге болатын төрт сыныпты анықтады. Жасушалық автоматтардағы бұрынғы зерттеулер белгілі бір ережелерге сәйкес келетін үлгілерді анықтауға бағытталған болса, Вольфрамның жіктемесі ережелердің өзіне жіктеме жасауға жасалған алғашқы әрекет болды. Күрделілік деңгейі бойынша сыныптар: 1-сынып: Дерлік барлық бастапқы үлгілер тез арада тұрақты, біртекті күйге келеді. Бастапқы үлгідегі кез келген кездейсоқтық жоғалады. 2-сынып: Дерлік барлық бастапқы үлгілер тез арада тұрақты немесе тербелісті құрылымдарға дамиды. Бастапқы үлгідегі кездейсоқтықтың бір бөлігі жойылуы мүмкін, бірақ қалған бөлігі сақталады. Бастапқы үлгідегі жергілікті өзгерістер жергілікті сипатта қалады. 2-сыныпқа тән тұрақты немесе тербелісті құрылымдардың пайда болуы мүмкін, бірақ осы күйге жету үшін қажетті қадамдар саны бастапқы үлгі салыстырмалы түрде қарапайым болған жағдайда да өте көп болуы мүмкін. Бастапқы үлгідегі жергілікті өзгерістер шексіздікке дейін таралуы мүмкін. Вольфрам көптеген, мүмкін барлық 4-сынып ұялы автоматтарының әмбебап есептеуге қабілетті екенін болжады. Бұл 110-шы қағида және Конвейдің «Өмір» ойыны үшін дәлелденген. Бұл анықтамалар сапалық сипатта және интерпретацияға орын береді. Вольфрамның айтуынша, «кез келген жалпы жіктеу схемасында бір анықтама бойынша бір сыныпқа, ал екінші анықтама бойынша басқа сыныпқа жататын жағдайлар болатыны сөзсіз. Ұялы автоматтарда да осылай: кейде бір кластың кейбір ерекшеліктерін, ал екінші кластың кейбір ерекшеліктерін көрсететін ережелер кездеседі». Вольфрамның жіктемесі ұялы автоматтардың шығыстарының сығылған ұзындығының кластерленуімен эмпирикалық түрде сәйкес келеді. Вольфрамның жіктемесіне сүйене отырып, ұялы автоматтарды ресми түрде қатаң сыныптарға жіктеуге бірнеше әрекеттер жасалды. Мысалы, Кулик және Ю үш анықталған сыныпты (және осылардың ешқайсысына сәйкес келмейтін төртінші сыныпты) ұсынды, олар кейде Кулик-Ю сыныптары деп аталады; осы сыныптарға жататындығын анықтау шешілмейтін мәселе болып табылады. Вольфрамның 2-сыныбын тұрақты (тұрақты нүкте) және тербелісті (периодтық) ережелердің екі кіші тобына бөлуге болады. Динамикалық жүйелердің 4 класы бар деген идеяны бастапқыда Нобель сыйлығының иегері, химик Илья Пригожин ұсынған. Ол термодинамикалық жүйелердің 4 класын анықтады: (1) термодинамикалық тепе-теңдіктегі жүйелер, (2) кеңістік және уақыт бойынша біртекті жүйелер, (3) хаотикалық жүйелер және (4) тепе-теңдіктен алыс орналасқан, диссипативтік құрылымдары бар күрделі жүйелер (Николис, Пригожиннің шәкірті, 1974 жылғы 1-суретті қараңыз).

Wolfram, in A New Kind of Science and several papers dating from the mid 1980s, defined four classes into which cellular automata and several other simple computational models can be divided depending on their behavior. While earlier studies in cellular automata tended to try to identify types of patterns for specific rules, Wolfram's classification was the first attempt to classify the rules themselves. In order of complexity the classes are:
Class 1: Nearly all initial patterns evolve quickly into a stable, homogeneous state. Any randomness in the initial pattern disappears. Class 2: Nearly all initial patterns evolve quickly into stable or oscillating structures. Some of the randomness in the initial pattern may filter out, but some remains. Local changes to the initial pattern tend to remain local. Class 2 type stable or oscillating structures may be the eventual outcome, but the number of steps required to reach this state may be very large, even when the initial pattern is relatively simple. Local changes to the initial pattern may spread indefinitely. Wolfram has conjectured that many class 4 cellular automata, if not all, are capable of universal computation. This has been proven for Rule 110 and Conway's Game of Life. These definitions are qualitative in nature and there is some room for interpretation. According to Wolfram, " with almost any general classification scheme there are inevitably cases which get assigned to one class by one definition and another class by another definition. And so it is with cellular automata: there are occasionally rules that show some features of one class and some of another." Wolfram's classification has been empirically matched to a clustering of the compressed lengths of the outputs of cellular automata. There have been several attempts to classify cellular automata in formally rigorous classes, inspired by Wolfram's classification. For instance, Culik and Yu proposed three well defined classes (and a fourth one for the automata not matching any of these), which are sometimes called Culik–Yu classes; membership in these proved undecidable. Wolfram's class 2 can be partitioned into two subgroups of stable (fixed point) and oscillating (periodic) rules. The idea that there are 4 classes of dynamical system came originally from Nobel prize winning chemist Ilya Prigogine who identified these 4 classes of thermodynamical systems: (1) systems in thermodynamic equilibrium, (2) spatially/temporally uniform systems, (3) chaotic systems, and (4) complex far from equilibrium systems with dissipative structures (see figure 1 in the 1974 paper of Nicolis, Prigogine's student).

Қайталанатын

Ұялы автомат қайтымды болады, егер ұялы автоматтың әрбір ағымдағы конфигурациясы үшін дәл бір өткен конфигурация (алдын ала бейне) болса. Егер жасушалық автоматты конфигурацияларды конфигурацияларға бейнелейтін функция ретінде қарастырсақ, қайтымдылық бұл функцияның биективті екенін білдіреді. Әрбір конфигурацияның алдын ала бейнесі жоқ жасушалық автоматтар үшін, алдын ала бейнесі жоқ конфигурациялар Едем бағының үлгілері деп аталады. Бір өлшемді жасушалық автоматтар үшін ереженің қайтымды немесе қайтымсыз екенін анықтауға арналған белгілі алгоритмдер бар. Дегенмен, екі немесе одан көп өлшемді жасушалық автоматтар үшін қайтымдылық шешілмейді; яғни, автомат ережесін кіріс ретінде қабылдап, автоматтың қайтымды екенін дұрыс анықтауға кепілдік беретін алгоритм жоқ. Жаркко Каридің дәлелі Ван плиткаларының мозаикалау мәселесімен байланысты. Термодинамика заңдарына бағынатын қайтымды жасушалық автоматтар көбінесе газ және сұйық динамикасы сияқты физикалық құбылыстарды модельдеу үшін қолданылады. Мұндай жасушалық автоматтардың ерекше қайтымды ережелері болады. Мұндай жүйелерді Томмазо Тоффоли, Норман Марголус және басқалар зерттеген. Белгілі керісі бар қайтымды жасушалық автоматтарды нақты құру үшін бірнеше техникаларды қолдануға болады. Екі кең таралғаны – екінші реттік жасушалық автомат және блок жасушалық автомат, екеуі де жасушалық автоматтың анықтамасын бір жолмен өзгертуді қамтиды. Мұндай автоматтар жоғарыда келтірілген анықтаманы қатаң түрде орындамаса да, оларды жеткілікті үлкен маңайлар мен күйлер саны бар дәстүрлі жасушалық автоматтармен модельдеуге болатынын көрсетуге болады, сондықтан оларды дәстүрлі жасушалық автоматтардың ішкі жиыны деп санауға болады. Керісінше, әрбір қайтымды жасушалық автоматты блок жасушалық автоматпен модельдеуге болатыны көрсетілді.

Тоталистік

Ұялы автоматтардың ерекше класы – тотальді ұялы автоматтар. Тотальді ұялы автоматта әрбір жасушаның күйі санмен (әдетте шекті жиынтықтан алынған бүтін сан) көрсетіледі, ал t уақытындағы жасушаның мәні тек t-1 уақытындағы оның айналасындағы жасушалардың мәндерінің қосындысына ғана байланысты (мүмкін, жасушаның өзі де кіретін). Егер жасушаның t уақытындағы күйі оның өзінің күйіне де, сондай-ақ t-1 уақытындағы көршілерінің қосындысына да байланысты болса, онда бұл ұялы автомат толық тотальді деп аталады.

Қатысушы автоматтар

Ұялы автомат тұжырымдамасының көптеген мүмкін жалпыламалары бар. Бір жолы – тік төртбұрышты (кубтық, т.б.) емес, басқа нәрсені пайдалану. Мысалы, егер жазықтық тұрақты алтыбұрыштармен қапталса, онда осы алтыбұрыштар ұяшықтар ретінде қолданылуы мүмкін. Көп жағдайда пайда болатын ұялы автоматтар, арнайы жасалған көршіліктер мен ережелері бар тік төртбұрышты торларға тең келеді. Тағы бір нұсқасы – тордың өзін, мысалы, Пенроуз плиткалары сияқты, ретсіз ету. Сондай-ақ, ережелер детерминистік емес, ықтималдық болуы мүмкін. Мұндай ұялы автоматтар ықтималдық ұялы автоматтар деп аталады. Ықтималдық ереже t уақытындағы әрбір үлгі үшін орталық ұяшықтың t+1 уақытындағы әрбір мүмкін жағдайға көшу ықтималдығын көрсетеді. Кейде қарапайым ереже қолданылады; мысалы: «Ереже – «Өмір ойыны», бірақ әр қадамда әрбір ұяшықтың қарама-қарсы түске өту ықтималдығы 0,001% құрайды». Көршілік немесе ережелер уақыт пен кеңістікте өзгеруі мүмкін. Мысалы, бастапқыда ұяшықтың жаңа күйін көлденең орналасқан ұяшықтар анықтаса, келесі буында тік орналасқан ұяшықтар қолданылуы мүмкін. Ұялы автоматтарда ұяшықтың жаңа күйі басқа ұяшықтардың жаңа күйіне әсер етпейді. Бұл өзгертілуі мүмкін, мысалы, 2x2 ұяшықтар блогының өзі және оған іргелес ұяшықтар оны анықтауы мүмкін. Үздіксіз автоматтар да бар. Олар тоталистік ұялы автоматтарға ұқсас, бірақ ереже мен күйлер дискретті (мысалы, {0,1,2} күйлерін пайдаланатын кесте) болғанның орнына, үздіксіз функциялар қолданылады және күйлер үздіксіз болады (әдетте [0,1] аралығындағы мәндер). Орналасудың күйі – нақты сандардың шекті саны. Кейбір ұялы автоматтар осылай сұйық үлгілерде диффузияны тудыра алады. Үздіксіз кеңістіктік автоматтарда орналасулардың үздіксіздігі бар. Орналасудың күйі – нақты сандардың шекті саны. Уақыт та үздіксіз, ал күй дифференциалдық теңдеулерге сәйкес эволюциялайды. Маңызды мысал – реакция-диффузиялық текстуралар, Алан Тьюрингтің химиялық реакциялар зебралардағы жолақтарды және барыстардағы дақтарды қалай құратынын түсіндіру үшін ұсынған дифференциалдық теңдеулер. Бұл теңдеулер ұялы автоматтармен жуықтағанда көбінесе ұқсас үлгілер береді. МакЛеннан үздіксіз кеңістіктік автоматтарды есептеу моделі ретінде қарастырады. «Өмір ойынындағы» жылғыштарға ұқсас таралу құбылыстарын көрсететін үздіксіз кеңістіктік автоматтардың белгілі мысалдары бар. Графты қайта жазу автоматтары – графты қайта жазу жүйелеріне негізделген ұялы автоматтардың кеңейтілген түрі.

There are many possible generalizations of the cellular automaton concept. One way is by using something other than a rectangular (cubic, etc.) grid. For example, if a plane is tiled with regular hexagons, those hexagons could be used as cells. In many cases the resulting cellular automata are equivalent to those with rectangular grids with specially designed neighborhoods and rules. Another variation would be to make the grid itself irregular, such as with Penrose tiles. Also, rules can be probabilistic rather than deterministic. Such cellular automata are called probabilistic cellular automata. A probabilistic rule gives, for each pattern at time t, the probabilities that the central cell will transition to each possible state at time t + 1. Sometimes a simpler rule is used; for example: "The rule is the Game of Life, but on each time step there is a 0.001% probability that each cell will transition to the opposite color." The neighborhood or rules could change over time or space. For example, initially the new state of a cell could be determined by the horizontally adjacent cells, but for the next generation the vertical cells would be used. In cellular automata, the new state of a cell is not affected by the new state of other cells. This could be changed so that, for instance, a 2 by 2 block of cells can be determined by itself and the cells adjacent to itself. There are continuous automata. These are like totalistic cellular automata, but instead of the rule and states being discrete (e. g. a table, using states {0,1,2}), continuous functions are used, and the states become continuous (usually values in [0,1]). The state of a location is a finite number of real numbers. Certain cellular automata can yield diffusion in liquid patterns in this way. Continuous spatial automata have a continuum of locations. The state of a location is a finite number of real numbers. Time is also continuous, and the state evolves according to differential equations. One important example is reaction–diffusion textures, differential equations proposed by Alan Turing to explain how chemical reactions could create the stripes on zebras and spots on leopards. When these are approximated by cellular automata, they often yield similar patterns. MacLennan considers continuous spatial automata as a model of computation. There are known examples of continuous spatial automata, which exhibit propagating phenomena analogous to gliders in the Game of Life. Graph rewriting automata are extensions of cellular automata based on graph rewriting systems.

Элементар жасуша автоматтары

Ең қарапайым тривиалды емес жасушалық автомат бір өлшемді болады, әр жасушаның екі мүмкін күйі болады, ал жасушаның көршілері оның екі жағындағы жасушалар ретінде анықталады. Жасуша және оның екі көршісі 3 жасушадан тұратын аймақты құрайды, сондықтан аймақтың 2³ = 8 мүмкін үлгісі бар. Ереже әр үлгі үшін жасушаның келесі буында 1 немесе 0 болатынын шешуден тұрады. Онда 2⁸ = 256 мүмкін ереже бар. 2004 жылы Кук дәлелі ақыры Вольфрамның "Комплекс жүйелер" журналында (15-том, 1-номер) жарияланды, Кук оны ойлап тапқаннан кейін он жылдан астам уақыт өткен соң. 110-қағида кейбір ең кішкентай универсалды Тьюринг машиналарының негізі болып табылады.

Ереже кеңістігі

Элементарлы жасушалық автомат ережесі 8 битпен сипатталады, ал барлық элементарлы жасушалық автомат ережелерін 8 өлшемді бірлік гиперкубтың төбелерінде орналасқан деп қарастыруға болады. Бұл гиперкуб – жасушалық автоматтың ереже кеңістігі. Келесі жақын көрші жасушалық автоматтар үшін ереже 25 = 32 битпен сипатталады, ал жасушалық автоматтың ереже кеңістігі 32 өлшемді бірлік гиперкуб болып табылады. Екі ереже арасындағы қашықтық гиперкубтың қабырғасы бойынша бір төбеден (бірінші ережені көрсетеді) екінші төбеге (екінші ережені көрсетеді) жетуге қажетті қадамдар санымен анықталады. Бұл ережеден ережеге қашықтық Хамминг қашықтығы деп те аталады. Жасушалық автоматтың ереже кеңістігі, ұқсас динамикалық қасиеттері бар ережелердің бір-біріне «жақын» болатыны туралы сұрақ тудырады. Жоғары өлшемді гиперкубты 2 өлшемді жазықтықта графикалық түрде көрсету қиын міндет болып қалады, ал гиперкубтағы ереженің шамамен орналасқан жерін анықтаудың қарапайым жолы – элементарлы ережелер үшін 8 биттік тізбектегі 1-дің саны (немесе келесі жақын көрші ережелер үшін 32 биттік тізбек). Ереже кеңістігінің осы кесінділерінде әртүрлі Вольфрам сыныптарындағы ережелерді көрсету арқылы 1-сыныптағы ережелерде 1-дің саны аз болады, яғни олар кеңістіктің бір аймағында орналасады, ал 3-сыныптағы ережелерде 1-дің саны жоғары (50%) болады. Бұл байқау «хаостың шегі» терминінің негізі болып табылады және термодинамикадағы фазалық өтуді еске түсіреді.

Биология

[[Файл:Текстильді конус. JPG|thumb|left|Текстильді конус қабығында жасушалық автомат үлгісі байқалады. Жасушалық жолақ қабық өскенде түсті үлгі қалдырады. Мысалы, кең таралған текстильді конус түрлері Вольфрамның 30-қағидасына сәйкес жасушалық автомат үлгісін көрсетеді. Бас аяқты моллюскалардың терісіндегі қозғалатын толқын үлгілерін екі күйлі, екі өлшемді жасушалық автоматтар арқылы модельдеуге болады, мұнда әр күй кеңейтілген немесе жирылған хроматофорға сәйкес келеді. Нейрондарды модельдеу үшін шекті автоматтар ойлап табылды, сондай-ақ тану және оқыту сияқты күрделі мінез-құлықтарды модельдеу мүмкін. Фибробластар жасушалық автоматтарға ұқсас, себебі әрбір фибробласт тек көршілерімен ғана өзара әрекеттеседі. Сонымен қатар, агенттердің жылдамдықтарын нақты модельдеуді талап ететін биологиялық процестер (мысалы, ұжымдық жасушалардың қозғалысына қатыстылар) биологиялық торлы газ жасушалық автоматтары сияқты күрделі күй кеңістігі мен ережелері бар жасушалық автоматтармен модельденуі мүмкін. Бұған зор медициналық маңызы бар құбылыстар жатады, мысалы:

Метастаздық инвазияның әртүрлі түрлерін сипаттау. Агрессивті карциномалардың дамуындағы әртүрліліктің (гетерогендіктің) рөлі. Ісік көбеюі кезіндегі фенотиптік өзгерістер.

Химия

Белоусов-Жаботинский реакциясы – жасушалық автомат арқылы модельдеуге болатын кеңістік-уақыттық химиялық осциллятор. 1950 жылдары А. М. Жаботинский (Б. П. Белоусовтың зерттеулерін дамыта отырып) малон қышқылы, қышқылданған бромат және церий тұзының жұқа, біртекті қабаты қосылғанда және тыныш қалдырылғанда, концентрлі шеңберлер мен спиральдар сияқты әдемі геометриялық үлгілер ортада таралатынын анықтады. 1988 жылғы тамыз айындағы Scientific American журналының «Компьютерлік ойын-сауық» бөлімінде А. К. Дьюдни Бьелефельд университетінің (Германия) Мартин Герхардт пен Хайке Шустер жасаған жасушалық автоматты талқылады. Бұл автомат Белоусов-Жаботинский реакциясындағыдай толқынды үлгілерді тудырады.

Физика

thumb|300px|оң|Торлы газ автоматтысын визуализациялау. Жеке пикселдердің сұр түстері сол пикселдегі газ бөлшектерінің тығыздығына (0 мен 4 арасында) пропорционалды. Газ сары жасушалармен қоршалған, олар жабық кеңістік құру үшін шағылыстырғыштар ретінде әрекет етеді. Ықтималдық жасушалық автоматтар статистикалық және конденсирленген заттар физикасында сұйық динамикасы және фазалық өтулер сияқты құбылыстарды зерттеу үшін қолданылады. Исинг моделі – бұл классикалық мысал, онда әрбір жасуша "жоғары" және "төмен" деп аталатын екі күйдің бірінде болуы мүмкін, бұл магниттің идеализацияланған бейнесін құрайды. Модельдің параметрлерін реттеу арқылы бірдей күйдегі жасушалардың үлесін өзгертуге болады, бұл ферромагниттердің қыздырылғанда қалай демагнетизацияланатынын түсіндіруге көмектеседі. Сонымен қатар, демагнетизация фазалық өтуін зерттеу нәтижелері сұйықтың газға айналуы сияқты басқа фазалық өтулерге қолданылуы мүмкін; бұл ыңғайлы өзара қолданылу универсалдылық деп аталады. Екі өлшемді Исинг моделіндегі және оның универсалдық класындағы басқа жүйелердегі фазалық өту ерекше қызығушылық тудырады, себебі оны толық түсіну үшін конформдық өріс теориясы қажет. Физикада маңызды болып табылатын басқа жасушалық автоматтарға сұйық ағындарын модельдеуге арналған торлы газ автоматтары жатады.