Ћелијски аутомат

Ћелијски аутомат (енгл. cellular automaton; CA) је дискретни модел који се проучава унутар теорија информатике, математике, физике, сложеног адаптивног система, теоријске биологије и микроструктуре моделирања.

За ћелијске аутомате се такође користе и називи ћелијски простори (енгл. cellular spaces), мозаични аутомати (енгл. tessellation automata), хомогене структуре (енгл. homogeneous structures), ћелијске структуре (енгл. cellular structure), мозаичне структуре (енгл. tessellation structures), учестали низови (енгл. iterative arrays) итд.

Ћелијски аутомат се састоји од правилне мреже ћелија, од којих је свака у једном од стања чији је број ограничен (није бесконачан) као што су укључено (1) и искључено (0), за разлику од комбинованих решетки пресликавања). Мрежа може бити у било којој од димензија, с тим да број тих димензија такође није бесконачан. За сваку ћелију, низ ћелија који се назива њеним суседством дефинисан је у односу на поменуту ћелију. Почетно стање (време $t=0$) одређује се бирањем стања за сваку од ћелија. Нова генерација се ствара (што повећава време функцијом $f=t+1$) према неком фиксном тј. тачно одређеном и непроменљивом правилу (углавном, математичка функција) које одређује ново стање сваке од ћелија зависно од тренутног стања ћелије и стања ћелија у њеном суседству. Најчешће, правило за „ажурирање” стања ћелија исто је за сваку ћелију и не мења се временом, а примењује се на целу мрежу истовремено (одједном). Међутим, изузеци постоје; на пример, стохастични ћелијски аутомат и асинхрони ћелијски аутомат.

Госперова глидерска пушка (енгл. Gosper's Glider Gun) која ствара глидере у ћелијском аутомату Конвејева „Игра живота”

Концепт су први открили Станислав Мартин Улам и Џон фон Нојман 1940-их година, и то док су радили заједно у Националној лабораторији у Лос Аламосу (Нови Мексико, САД). Док су студирали током 1950-их и 1960-их, концепта није било, а све до 1970-их и појаве Конвејеве „Игре живота”, дводимензионалног ћелијског аутомата. Интересовање за ову тему тада се проширило и изван академских кругова. Стивен Волфрам је током 1980-их радио на систематској студији једнодимензионалног ћелијског аутомата, или како га он назива — елементарни ћелијски аутомат. Његов асистент Метју Кук показао је да је једно од тих правила Тјуринг-потпуно (рачунски универзално). Волфрам је објавио Нову врсту науке (енгл. A New Kind of Science) 2002. године, тврдећи да ћелијски аутомати имају примену у многим областима науке. Ово укључује рачунарске процесоре и криптографију. 

Класификација ћелијских аутомата

Примарна класификација ћелијских аутомата, према ономе што је Волфрам навео, обележена је бројевима од 1 до 4. Чине је следеће класе (по наведеном реду):

1. аутомати у којима се обрасци генерално стабилизују у хомогеност
2. аутомати у којима обрасци еволуирају у углавном стабилне или осцилирајуће структуре
3. аутомати у којима обрасци еволуирају на наизглед хаотичан начин
4. аутомати у којима обрасци постају изузетно сложени и могу да трају дуго времена, са стабилним локалним структурама

Ова последња класа сматра се да је рачунски универзална тј. способна за симулацију Тјурингове машине.

Посебне врсте ћелијских аутомата су и реверзибилни аутомати (где само једна конфигурација води директно до оне следеће, узастопне) те тоталистички аутомати (у којима будућа вредност појединих ћелија зависи од укупне вредности групе суседних ћелија).

Ћелијски аутомати могу да симулирају разне системе из стварног живота, укључујући и биолошке и хемијске. 

Преглед

Црвене ћелије су Мурови суседи за плаву ћелију

Црвене ћелије су Фон Нојманови суседи за плаву ћелију (проширено суседство укључује и ружичасте ћелије, такође)

Један од начина да се симулира дводимензионални ћелијски аутомат је коришћењем бесконачног листа граф папира, заједно са сетом правила за ћелије која треба да се прате. Сваки квадрат се зове ћелија, а свака ћелија има два могућа стања, црно и бело. Суседство ћелије чине оне најближе, обично околне ћелије које су непосредно уз ону која се посматра. Два најчешћа типа суседства су Фон Нојманово суседство и Мурово суседство. Мурово суседство је име добило по теоретичару-оснивачу ћелијског аутомата, а састоји се од четири ортогонално суседне ћелије. Последња обухвата Фон Нојманово суседство, као и четири преостале ћелије које окружују ћелију чије стање треба да се израчуна. За такву ћелији и њено Мурово суседство, постоји 2⁹ = 512 могућих образаца. За сваки од 512 могућих образаца, табела са правилима одређивала би да ли ће централна ћелија бити црна или бела на следећем временском интервалу. Конвејева „Игра живота” је популарна верзија овог модела. Други уобичајен тип суседства је проширено Фон Нојманово суседство, које укључује две најближе ћелије у сваком од ортогоналних смерова, што даје укупно 8 ћелија. Општа једначина за такав систем правила је $k^{k^{s}}$, где је $k$ број могућих стања за ћелију, а $s$ број суседних ћелија (укључујући и ћелију која се посматра) који се користи за одређивање следећег стања посматране ћелије. Према томе, у дводимензионалном систему са Муровим суседством, укупан могући број аутомата био би 2²⁹ ≈ 1,34 × 10¹⁵⁴.

Обично се претпоставља да свака ћелија у свемиру на почетку има исто стање, осим за тачно одређен број ћелија у другим стањима; придруживање вредности стања зове се конфигурација. Уопштено говорећи, понекад се претпоставља да свемир започиње прекривен периодичним обрасцем, док тај образац нарушава само тачно одређен број ћелија. Ова друга хипотеза уобичајена је у једнодимензионалним ћелијским аутоматима.  

Торус, тороидални облик

Ћелијски аутомати се чешће симулирају на ограниченој мрежи него на мрежи која је бесконачна. У две димензије, свемир би био правоугаоник, а не (бесконачна) раван. Очигледан проблем са ограниченом мрежом је како да се интерпретирају крајње ћелије. То како се интерпретирају ове ћелије утицаће на вредности свих ћелија у мрежи. Једно могуће решење је да се омогући да вредност у тим ћелијама буде константна. Други метод је различито дефинисање суседстава за ове ћелије. Могло би се рећи да имају мање суседа, али онда би се такође морала дефинисати нова правила за ћелије које се налазе на крајевима. Ове ћелије се обично интерпретирају тороидалним принципом: када једна ћелија с врха нестане, друга — као замена — долази на одговарајућу позицију на дну; када нестане ћелија с леве стране, друга долази на десну страну. (Овиме се у суштини симулира бескрајно периодично „поплочавање”, а у области парцијалних диференцијалних једначина понекад се назива и периодичним граничним условима.) Ово може да се визуализира замишљањем приљубљивања леве и десне ивице правоугаоника чиме би се формирала цев, чије би се ивице (два круга на крајевима) потом спојиле формирајући торус (облик америчке крофне). Са свемирима других димензија поступа се на сличан начин. Овиме се решавају гранични проблеми са суседствима, а још једна предност је у томе што се ово да лако програмирати помоћу функција модуларне аритметике. На пример, код једнодимензионалног ћелијског аутомата приказаног испод, суседство ћелије $x_{i}^{t}$ је: $\{x_{i-1}^{t-1},x_{i}^{t-1},x_{i+1}^{t-1}\}$, где је $t$ временски корак (вертикално), а $i$ индекс (хоризонтално) у једној генерацији.

Историја

Џон фон Нојман, Лос Аламос ознака ИД

Станислав Улам, док је радио у Националној лабораторији Лос Аламос 1940, студирао је раст кристала, користећи једноставну мрежу решетке као његов модел.Истовремено, Џон фон Нојман, Уламов колега у Лос Аламосу, ради на проблему само-реплицираних система. Почетни дизајн, фон Нојман је основао на идеји једног робота градећи још један робот. Овај дизајн је познат као кинематички модел. Како је развио овај дизајн, фон Нојман је дошао да оствари велику тешкоћу изградње само-реплицираног робота, и на великој цени у пружању робота са „морем делова” из којих изграђује свој репликант. Нојман чита новине под називом „Генерална и логична теорија аутомата” на Хиксон симпозијуму 1948. године. Улам је био тај који предлаже коришћење дискретног система за стварање редукованог модела понављања самог себе. Нилс Ал Барицели обавља многе од најранијих истраживања ових модела вештачког живота. 

Улам и фон Нојман су створили метод за израчунавање течног кретања крајем 1950-их. Покретачки Концепт методе је био да се размотри течност као група дискретних јединица и да се израчуна кретање сваког од њих на основу понашања својих суседа. Тако је рођен први систем ћелијског аутомата. Као Уламове решетке мреже, фон Нојманови ћелијски аутомати су дводимензионални, са својим само-репликаторима спроведеним алгоритмички. Резултат је био универзални копир и конструктор који ради у ћелијском аутомату са малим окружењем (само оне ћелије које се додирују су суседи; за фон Нојманов ћелијски аутомат, само ортогоналне ћелије), и са 29 стања по ћелији. Фон Нојман је дао доказ постојања, да ће посебан образац учинити бескрајне копије себе у оквиру датог ћелијског универзума пројектовањем конфигурације 200.000 ћелија које би могао да уради. Овај пројекат је познат као теселациони модел, и назива се фон Нојманов универзални конструктор.

Такође, 1940. Норберт Винер и Артуро Росенблуетх су развили модел ексцитабилног медија са неким од карактеристика ћелијског аутомата. Њихова специфична мотивација је математички опис импулса проводљивости у срцима система. Међутим њихов модел није ћелијски аутомат, јер медиј у којем се сигнали простиру је континуиран, а махање фронтова су криве. Прави ћелијски аутомат модел ексцитабилне медије је развијен и студиран од стране Ј. М. Гренберг и С. П. Хастингс 1978. године; види Гринберг-Хастингсов ћелијски аутомат. Оригинални рад Виенер и Росенблуетх садржи многе увиде и наставља да буде цитиран у савременим истраживачким публикацијама о срчаној аритмији и екситаблним системима.

Године 1960, ћелијски аутомати су проучавани као одређена врста динамичког система и повезивани са математичким пољем симболичке динамике по први пут. 1969. Густав О’Хедлунд, сабрао је многе резултате пратећи ове тачке гледишта у оно што се и даље сматра основним папиром за математичку студију ћелијског аутомата. Најосновнији резултат је карактеризација у Кертис - Хедлунд - Линдон теореми низа глобалних правила ћелијског аутомата као скуп непрекидних функција ендоморфских смена простора. 

Године 1969. немачки компјутерски пионир Конрад Цузе је објавио своју књигу Прорачунати простор, предлажући да су физички закони универзума дискретни по природи, и да је цео универзум излаз детерминистичким рачунањима на једном ћелијском аутомату; „Цизе теорија” је постала темељ области студија под називом дигитална физика.

Године 1970, са два стања, дводимензионални ћелијски аутомат под називом Игра Живота постао је познат, посебно почетком рачунарске заједнице. Измислио их је Џон Конвеј и популаризовао Мартин Гарднер у Научном Америчком чланку, њена правила су следећа: Ако ћелија има два црна суседа, она остају иста. Ако има три црна суседа, постаје црна. У свим другим ситуацијама постаје бела. Упркос својој једноставности, систем постиже импресивну разноврсност понашања, променљивих између привидних случајности. Један од очигледних карактеристика игре живота је честа појава једрилица, аранжмана ћелија које у суштини се крећу преко мреже. Могуће је договорити аутомат тако да једрилица интеракцију обавља прорачунато, а после много труда је показано да Игра Живота може имитирати универзалну Тјурингову машину. То се посматра као углавном рекреативна тема, и мало праћених радова ван истражују специфичности игре живота и неколико повезаних правила почетком 1970-их.

Стивен Волфрам  је самостално почео да ради на ћелијском аутомату средином 1981. године, након разматрања колико је сложен образац изгледао формиран у природи у супротности са другим законом термодинамике. Његове истраге су у почетку подстакнуте од стране интереса за моделирање система, као што су неуронске мреже. Он је објавио свој први рад у Прегледу модерне физике истражујући основне ћелијске аутомате (правило 30 посебно) у јуну 1983.  Неочекивана сложеност понашања ових једноставних правила довела је Волфрама на сумњу да комплексност у природи може бити због сличних механизама. Његове истраге, међутим, довеле су га до тога да схвати да су ћелијски аутомати били сиромашни у моделирању неуронске мреже. Поред тога, током овог периода Волфрам је формулисао концепте својствене случајности и рачунарској несводивости, и предложио да правило 110 може бити универзално-чињеница доказана касније уз помоћ истраживачког сарадника Волфрама, Матеја Хука 1990.

Године 2002. Волфрам је објавио текст са 1.280 страница нове врсте науке, који интензивно тврди да откриће о ћелијском аутомату није изолована чињеница, али је снажна и има значај за све дисциплине науке. Упркос конфузији у штампи, ова књига се не залаже за фундаменталну теорију физике на основу ћелијског аутомата, и иако је описала неколико конкретних физичких модела на основу ћелијских аутомата, такође доказује моделе базиране на квалитативно различитим апстрактним системима.

Класификација

Волфрам, у новој врсти науке и неколико радова који датирају из средине 1980-их, дефинише четири класе у којима се ћелијски аутомати и неколико других једноставних компјутерских модела могу груписати у зависности од њиховог понашања. Док раније студије о ћелијском аутомату тенденцирају да покушају да идентификују тип образаца за одређена правила, Волфрамова класификација је била први покушај да се класификују сама правила, да би сложеност била разређена: 

• Класа 1: Скоро сви почетни обрасци развијају брзо, стабилно и хомогено стање. Свака случајност у почетном обрасцу нестаје.
• Класа 2: Скоро сви почетни обрасци развијају брзе стабилне или осциловане конструкције. Неки од случајности у почетном обрасцу се могу филтрирати. Локалне промене у почетном обрасцу теже да остану локалне.
• Класа 3: Скоро сви почетни обрасци се развијају псеудо-случајно или на хаотичан начин. Све стабилне структуре које се појављују се брзо уништавају од стране околне буке. Локалне промене у почетном обрасцу имају тенденцију да се шире на неодређено време.
• Класа 4: Скоро сви почетни обрасци се развијају у структуре које реагују на сложене и интересантне начине, уз формирање локалних структура које су у стању да преживе дуже време. Класа тип 2 стабилне или осциловане структуре може бити евентуални исход, али број корака потребних да се постигне ово стање може бити веома велики, чак и када је почетни модел релативно једноставан. Локалне промене у почетном обрасцу могу се ширити унедоглед. Волфрам је претпоставио да су многе, ако не и све 4 класе ћелијских аутомата у стању да се универзално рачунају. Ово је доказано за правило 110 и Конвејеву Игру живота. 

Ове дефиниције су квалитативне у природи и постоје неки простори за тумачење. Према Волфраму, „... са скоро свим генералним пласманима шеме постоје неминовни случајеви који се приписују једној класи једне дефиниције и другој класи од стране друге дефиниције”. Тако је и са ћелијским аутоматом: „Постоје повремена правила... (...) ... која показују неке карактеристике једне класе и неке друге”. "Класификација Волфрам-а је емпиријски упарена на груписање у компримованој дужини излаза ћелијског аутомата.

Било је неколико покушаја да се класификује ћелијски аутомат у формално ригорозне класе, инспирисане класификацијом Волфрама. На пример, Цулик и Ју, су предложили три добро дефинисане класе (и четврту за аутомате који не одговарају било којем од ових), што се понекад зове Цулик-ЈУ настава; Чланство у овоме се показало као неодлучив задатак. Класа Волфрам 2 може бити подељена у две подгрупе стабилних (фиксних тачака) и осцилованих (периодичних) правила.

Реверзибилно

Главни чланак: Reversible cellular automaton

Ћелијски аутомат је са два лица ако за сваку тренутну конфигурацију за ћелијски аутомат, постоји тачно једна протекла конфигурација. Ако неко мисли на ћелијски аутомат као мапирање функција конфигурације до конфигурације, понављање значи да је ова функција бијекција. Ако је ћелијски аутомат реверзибилан, његово време преокрета понашања може се описати као ћелијски аутомат; Ова чињеница је последица Кертис- Хедлунд-Линдонове теореме, а тополошка карактеризација ћелијског аутомата. За ћелијске аутомате у којима свака конфигурација нема слику, конфигурације без слике називају се Обрасцем рајског врта.

За једнодимензионални ћелијски аутомат познати су алгоритми за одлучивање да ли је правило реверзибилно или неповратно. Међутим, за ћелијски аутомат са две или више димензија реверзибилност је неодлучива; не постоји алгоритам који узима као улаз правило аутомата и гарантује прецизно да одреди да ли је аутомат реверзибилан. Доказ Јаркова Карија је у вези са проблемом плочице Ванг плочица.

Реверзибилан ћелијски аутомат се често користи да симулира такве физичке феномене као што су гас и динамика флуида, јер поштују законе термодинамике. Како ћелијски аутомат садржи правила специјално конструисана да буду реверзибилна. Такве системе су проучавали Томасо Тофоли, Норман Марголус и други. Неколико техника се могу користити за експлицитно конструисање реверзибилног ћелијског аутомата са познатим инверзијама. Два честа су други ред ћелијског аутомата и блок ћелијског аутомата, од којих оба укључују модификовану дефиницију ћелијског аутомата на неки начин. Иако такви аутомати не стриктно задовољавају дефиницију дату горе, може се показати да могу бити емулирано конвенционални ћелијски аутомати са довољно великим суседима и бројевима стања, и да се стога могу сматрати подскупом конвенционалних ћелијских аутомата. С друге стране, она је показала да сваки реверзибилни ћелијски аутомат опонаша блок ћелијског аутомата.

Тоталитарно

Посебна класа ћелијских аутомата су тоталитарни ћелијски аутомати. Стање сваке ћелије у тоталитарном ћелијском аутомату је представљено бројем (обично целобројна вредност проистекла из коначног скупа), а вредност ћелије у времену t зависи само од збира вредности ћелија у њеном суседству (евентуално и сама ћелија) у времену t-1. Ако стање ћелије у времену t зависи и од сопственог стања и о укупних својих суседа у времену t-1 потом ћелијски аутомат се правилно зове спољашњи тоталитарни. Конвејева Игра живота је пример спољног тоталитарног ћелијског аутомата са вредностима ћелија 0 и 1; Спољни тоталитарни ћелијски аутомати са истом структуром Моревог суседства као живот се понекад називају живот налик Ћелијском Аутомату.

Аутомати који доводе у везу

Постоји много могућих генерализација концепта Ћелијског Аутомата. 

Ћелијски аутомат на основу хексагоналних ћелија уместо квадрата (правило 34/2)

Један од начина је коришћењем нечег другог осим правоугаоног облика (кубних, итд ) решетка. На пример, ако је раван поплочана са редовним хексагонима, ти хексагони могу се користити као ћелије. У многим случајевима настали ћелијски аутомат је еквивалентан оном са правоугаоне мреже са посебно дизајнираним насељима и правилима. Још једна варијација би била да се направи сама мрежа нерегуларно, као што је са Пенроуз плочицама.

Такође, правила могу бити вероватнија више него детерминистичка. Зато се ћелијски аутомати називају вероватноће ћелијског аутомата. Пробабилистичко правило даје, за сваки узорак у времену t, вероватноћу да ће централна ћелија транзистирати на свако могуће стање у времену t+1. Понекад једноставније правило се користи; На пример: „Правило је Игра живота, али на сваки временски интервал постоји 0,001% вероватноћа да ће свака ћелија прећи на супротну боју.”

Суседи или правила могу се мењати током времена или простора. На пример, у почетку ново стање ћелије може бити одређено хоризонталним суседним ћелијама, али за наредне генерације ће се користити вертикалне ћелије.

У целуларном аутомату, на нова стања ћелије не утичу нова стања друге ћелије. То се може променити тако да, на пример, 2 по 2 блока ћелија могу бити одређени самим собом и ћелијама суседних себи. 

Постоје континуирани аутомати. Ово је као тоталистички ћелијски аутомат, али уместо правила и стања су дискретна (нпр табела, користећи стања {0,1,2 } ), континуиране функције се користе, а стања постају континуирана (обично у вредности 0,1). Стање локације је коначан број реалних бројева. Одређени ћелијски аутомат може да доведе до ширења у течном обрасцу на овај начин. 

Континуирани просторни аутомати имају континуирану локацију. Стање локације је коначан број реалних бројева. Време је такође континуирано, а стање се развија у складу са диференцијалним једначинама. Један важан пример је реакција-дифузија текстуре, диференцијална једначина коју је предложио Алан Тјуринг да објасни како хемијске реакције могу да створе пруге на зебри и тачке на леопарду. Када се они апроксимирају од стране ћелијског аутомата, они често дају сличне моделе. МекЛенан сматра континуирано просторни аутомат као модел обрачуна. 

Постоје познати примери континуираног просторног аутомата, који показују пропагирање феномена аналогно једрилици у Игри живота.

Елементарни ћелијски аутомат

Главни чланак: Elementary cellular automaton

Најједноставнији нетривијални ћелијски аутомат ће бити једнодимензионални, са два могућа стања по ћелији, и суседне ћелије су дефинисане као суседне ћелије са обе стране зида. Ћелија и њена два суседа формирају насеље од 3 ћелије, тако да постоје 2³ = 8 могућих образаца за суседе. Правило се састоји од одлучивања, за сваки узорак, да ли ће ћелија бити 1 или 0 у следећој генерацији. Онда Постоје 2⁸ = 256 могућих правила. Ових 256 ћелијских Аутомата се углавном односе на њихов Волфрамов код, стандардно названа конвенција коју је изумео Волфрам која даје сваком правилу број од 0 до 255. Правило 30 и правило 110 ћелијских аутомата су посебно интересантни. На слици испод је показана историја сваког када започиње конфигурацију која се састоји од 1 (на врху сваке слике) окружен са 0. Сваки ред пиксела представља генерацију у историји аутомата, са t=0 врхом реда. Сваки пиксел је беле боје за 0 и црне за 1. 

Правило 30

Правило 30 ћелијски аутомат

тренутни образац	111	110	101	100	011	010	001	000
ново стање за централну ћелију	0	0	0	1	1	1	1	0

Правило 110

Правило 110 ћелијски аутомат

тренутни образац	111	110	101	100	011	010	001	000
ново стање за централну ћелију	0	1	1	0	1	1	1	0

Правило 30 показује класу 3 понашања, што значи чак и једноставни улазни модели, као што је то приказано доводе до хаотичне, наизглед случајне историје. 

Правило 110, као Игра живота, приказује шта Волфрам назива класа 4 понашања, која није ни потпуно случајна, нити се у потпуности понавља. Локализоване структуре се појављују и интерагују у различитим компликованим начинима. У току развоја нове врсте науке, као асистент Волфраму 1994. године, Метју Кук показује да су неке од ових структура довољно богате да подрже универзалност. Овај резултат је занимљив јер правило 110 је веома једноставан 1-димензионални систем, и тежак за инжењера за обављање специфичног понашања. Овај резултат пружа значајну подршку за Волфрамово мишљење да је класа 4 система инхерентна као и да је универзална. Кук је представио свој доказ на конференцији Санта Фе Института за Целуларни аутомат 1998. године, али је Волфрам блокирао да доказ буде укључен у зборник конференције, зато што Волфрам није желео доказ најављен пре објављивања Нове врсте науке. 2004. години, Куков доказ је коначно објављен у Волфрамовом часопису сложених система (вол. 15, бр 1 ), преко десет година након тога Кук је дошао са њом. Правило 110 је било основа за неке од најмањих универзалних тјурингових машина.

Правило простора

Правило елементарног ћелијског аутомата је одређено са 8 бита, а сва основна правила ћелијског аутомата могу се сматрати да седе на теменима 8-димензионалних јединица хиперкуба. Ова јединица Хиперкуба је правило простора ћелијског аутомата. За следећи најближи сусед ћелијског аутомата, правило је одређено са 2⁵ = 32 бита. Удаљеност између два правила може се дефинисати по броју корака потребних за прелазак са једног темена, што представља прво правило, на друго теме, представљајући још једно правило, дуж ивице хиперкуба. Ово правило-ка-правилу удаљености се назива и Хамингова удаљеност. 

Правило простора ћелијског аутомата дозвољава нам да поставимо питање о томе да ли правила са сличним динамичким понашањима су „близу” сваког од њих. Графичко цртање високо димензионалних хиперкубова на 2-димензионалном подручју остаје тежак задатак, а један сиров локатор правила у хиперкубу је број бита-1 у 8-битном стрингу за елементарна правила (или 32-битни за следећи најближи сусед правила). Цртање правила у различитим класама Волфрама у овим кришкама простора правила показују да класа 1 правила теже да имају мањи број бит-1, чиме се налазе у једној регији простора, док класа 3 правила имају тенденцију да имају већи проценат (50%) од бита-1.

За веће правило простора ћелијског аутомата, она је показала да је класа 4 правила се налази између класа 1 и класа 3 правила. Ово запажање је основа за фразу ивице хаоса, и подсећа на фазе транзиције у термодинамици. 

Биологија

Конус текстил показује ћелијски аутомат образац на својој љусци.

За више информација погледајте: Patterns in nature

Неки биолошки процеси се одвијају или могу бити симулирани уз помоћ ћелијког аутомата.

Обрасци неких шкољки, попут оних у Конусу и роду Симболија, настају природним ћелијским аутоматом. Пигментне ћелије бораве у уском делу дуж усне. Свака ћелија лучи пигменте у складу са активирањем и инхибирањем активности својих суседа пигментних ћелија, поштовањем природне верзије математичких правила. Ћелија оставља обојен образац на љусци док она полако расте. На пример, раширена врста Конус текстила носи образац који подсећа на Волфрамово Правило 30 ћелијског аутомата.

Биљке регулишу њихов унос и губитак гасова путем механизма ћелијског аутомата. Свака стома на листу делује као ћелија.

Шаре таласа померања на кожи главоножаца могу се симулирати са два стања, дводимензионални ћелијски аутомат, сваком стању одговара или проширен или повучен Хроматофор.

Гранични аутомати су  били измишљени да симулирају неуроне, и сложена понашања као што је препознавање и учење које може бити симулирано.

Фибробласти рађају сличности са ћелијским аутоматом, како сваки фибробласт само реагују са својим суседима.

Хемијски типови

Белоусов - Заботинска реакција је просторно-временски хемијски осцилатор који се може симулирати помоћу ћелијског аутомата. Током 1950-их А. М. Заботински (продужује рад Б. П. Белоусова) открива да када танак, хомоген слој мешавине малонске киселине, закисељене броматно, и церијусове соли је помешан заједно и остављен нетакнут, фасцинантне геометријске шаре, као што су концентрични кругови и спирале пропагирају по средини. У „Компјутерској рекреацији”, секцији Аугустовог проблема из 1988. Научне америке, А. К. Девднеј дискутује о ћелијском аутомату, направљеном од стране Мартина Герхардата и Хајке Шустера, Универзитета у Билефелду (Западна Немачка). Овај аутомат ствара талас обрасца који личе онима у Белоусов-Заботинској реакцији. 

Апликације

Компјутерски процесор

Процесори ћелијских аутомата су физичке имплементације концепата CA, који могу да обраде информације рачунски. Обрађени елементи су распоређени у редовној мрежи идентичних ћелија. Мрежа је обично квадрат плочица, или теселација, две или три димензије; друге ствари су могуће, али још увек се не користе. Ћелије стања одређују само интеракцијом са суседним ћелијама. Не постоји начин да директно комуницирају са ћелијама даље. Један такав процесор ћелијског аутомата низа конфигурација је систолни низ. Мобилна интеракција може бити преко електричног набоја, магнетизма, вибрација (фонон и у квантним скалама), или било којег другог физички корисног средства. Ово се може урадити на више начина тако да нису потребне жице између било којих елемената. Ово је веома различито од процесора који се користе у већини рачунара данас, фон Њуманов дизајн, који је подељен у секције са елементима који могу да комуницирају са удаљеним елементима преко жице. 

Криптографија

Правило 30 је првобитно предложено као могућа Блок шифра за употребу у криптографији. Дводимензионални ћелијски аутомат се користио за случајне бројеве генерације.

Ћелијски аутомати су били предлагани за криптографију јавног кључа. Једносмерна функција је еволуција коначног CA, за који се сматра да је тешко наћи. С обзиром на правило, свако може лако израчунати будућа стања, али чини се да је веома тешко израчунати претходна стања. 

Кодирање корекције грешке

CA је применио дизајн исправљања грешке кодова у новинама „Дизајн ЋАЗНИГК — Ћелијски аутомат заснован на исправљању грешке кода”, Д. Рој Чоудари, С. Басу, И. Сен Гупта, П. Пал Чаудари. У раду дефинише нову шему изградње СЕЦ-ДЕД кодова користећи CA, а такође извештава брз хардверски декодер за код.

Моделинг физичке реалности

Главни чланци: Digital physics и digital philosophy

Као што Ендру Илачински истиче у свом ћелијском аутомату, многи научници су поставили питање да ли је универзум ћелијски аутомат. Илачински тврди да значај овог питања може бити боље вреднован са једноставним посматрањем, која се може почети као следеће. Размислите еволуцију правила 110: ако је то нека врста „стране физике”, шта би био разуман опис посматраних образаца? Ако посматрач није знао како су генерисане слике, које посматрач може завршити претпостављањем о кретању неких честица налик објектима. Заиста, физичар Џејмс Крачфилд је изградио ригорозну математичку теорију од те идеје, што доказује статистичком појавом " честица " из ћелијског аутомата. Затим, као аргумент иде, могло би се запитати да ли наш свет, који је тренутно добро описан физиком елементарних честица, може бити ЋA као у свом најосновнијем нивоу. 

Иако није развијена комплетна теорија дуж ове линије, развијање ове хипотезе довело је научнике до занимљивих шпекулација и плодних интуиција о томе како можемо смислити наш свет у дискретним оквирима. Марвин Мински, пионир АИ, истраживао је како да разуме интеракције честица са четвородимензионалним ЋA решеткама; Конрад Цусе — проналазач првог радног рачунара, З3—развијен неправилним организовањем решетке се позабавио питањем садржаја информација честица. У скорије време, Едвард Фредкин изложио је оно што је он изразио на „коначној природи хипотезе”, односно, идеја да „на крају сваког кванта физике, укључујући и простора и времена ће се испоставити да буде дискретан и коначан”. Фредкин и Волфрам су јаки заговорници CA-базираног на физици.

У последњих неколико година, остали предлози у погледу ових линија су се појавили из литературе у нестандардном рачунању. Волфрамова Нова врста науке сматра CA кључним за разумевање различитих субјеката, укључујући и физику. Математика модела референци, створена од стране иЛАБА оснивача Габријела Росија и развијена уз помоћ Францеска Берта и Јакопо Таглиуба, поседује оригиналан2D/3D универзум на основу новог „ромбичног додексадрона заснован на” решетки и јединственом правилу. Овај модел задовољава универзалност (еквивалентан је Тјуринговој машини) и савршену реверзибилност (жеља ако неко жели да лако очува различите количине и никада не изгуби све информације ), и то долази уграђено у теорији првог реда, дозвољавајући могућност рачунања, квалитетних изјава универзалне еволуције.

Специфична правила

Специфични типови ћелијског аутомата укључују:

• Брајанов мозак
• Лангтонов мрав
• Проводни свет
• Правило 90
• Правило 184
• Фон Нојманов ћелијски аутомат
• Нобилов ћелијски аутомат
• Кодов ћелијски аутомат
• Лангтонове петље
• КоДи

Решени проблеми

Проблеми који могу бити решени са ћелисјким аутоматом укључују:

• Проблем фирингове синхронизације тима
• Већински проблем

Види још

• Теорија аутомата
• Двосмерни саобраћај
• Ћелијски аутомат у популарној култури
• Циклични ћелијски аутомат
• Надражива средина
• Миреково славље
• Покретни ћелијски аутомат
• Квантни ћелијски аутомат
• Систем подршке просторне одлуке
• Турмити

Литература

• Dennett, Daniel (1995). Darwin's Dangerous Idea. London: Penguin Books. ISBN 978-0-14-016734-4. 
• Adamatzky, Andrew, ур. (2010). Game of Life Cellular Automata. Springer. ISBN 978-1-84996-216-2. 
• Bialynicki-Birula, Iwo; Bialynicka-Birula, Iwona (2004). Modeling Reality: How Computers Mirror Life. Oxford University Press. ISBN 978-0-19-853100-5. 
• Chopard, Bastien; Droz, Michel (2005). Cellular Automata Modeling of Physical Systems. Cambridge University Press. ISBN 978-0-521-46168-9. 
• Gutowitz, Howard, ур. (1991). Cellular Automata: Theory and Experiment. MIT Press. ISBN 9780262570862. 
• Ilachinski, Andrew (2001). Cellular Automata: A Discrete Universe. World Scientific. ISBN 9789812381835. 
• Kier, Lemont B.; Seybold, Paul G.; Cheng, Chao-Kun (2005). Modeling Chemical Systems using Cellular Automata. Springer. ISBN 9781402036576. 
• Schiff, Joel L. (2011). Cellular Automata: A Discrete View of the World. Wiley & Sons, Inc. ISBN 9781118030639. 
• Wolfram, Stephen (2002). A New Kind of Science. Wolfram Media. ISBN 978-1579550080. 
• Cellular automaton FAQ from the newsgroup comp.theory.cell-automata
• "Neighbourhood Survey" (includes discussion on triangular grids, and larger neighborhood CAs)
• von Neumann, John, 1966, The Theory of Self-reproducing Automata, A. Burks, ed., University of Illinois Press, Urbana, IL.
• Cosma Shalizi's Cellular Automata Notebook contains an extensive list of academic and professional reference material.
• Wolfram's papers on CAs Архивирано на сајту Wayback Machine (27. септембар 2013)
• A.M. Turing. 1952. The Chemical Basis of Morphogenesis. Phil. Trans. Royal Society, vol. B237. стр. 37–72. (proposes reaction-diffusion, a type of continuous automaton).
• Evolving Cellular Automata with Genetic Algorithms: A Review of Recent Work, Melanie Mitchell, James P. Crutchfeld, Rajarshi Das (In Proceedings of the First International Conference on Evolutionary Computation and Its Applications (EvCA'96). Moscow, Russia: Russian Academy of Sciences, 1996)
• The Evolutionary Design of Collective Computation in Cellular Automata, James P. Crutchfeld, Melanie Mitchell, Rajarshi Das (In J. P. Crutch¯eld and P. K. Schuster (editors), Evolutionary Dynamics|Exploring the Interplay of Selection, Neutrality, Accident, and Function. New York: Oxford University Press, 2002)
• The Evolution of Emergent Computation, James P. Crutchfield and Melanie Mitchell (SFI Technical Report 94-03-012)
• Ganguly, Sikdar, Deutsch and Chaudhuri "A Survey on Cellular Automata"

Спољашње везе

• (језик: енглески) Ћелијски аутомати — уноси од стране Франческа Бертоа и Јакопа Таглиабуа у делу Stanford Encyclopedia of Philosophy
• (језик: енглески) Миреково славље — основа за бесплатне претраживачке софтвере и библиотеке правила за MCell и MJCell ћелијске аутомате; софтвер подржава велики број 1D и 2D правила, а веб-сајт омогућава и детаљни лексикон правила и многе галерије слика које се учитавају са примерима за правила; MCell је апликација за Виндоус, док је MJCell Јава аплет; изворни код је доступан
• (језик: енглески) Модерни ћелијски аутомат — лак за коришћење и интерактиван, са живим бојама 2D ћелијских аутомата; покреће га Јава аплет, а укључује и традиционална, реверзибилна, хексагонална, вишекорачна, фракцијска и друга правила за генерисање образаца; хиљаде правила је већ припремљено за употребу, а бесплатан софтвер је тренутно доступан
• (језик: енглески) Петље саморепликације у ћелијском свемиру — Јавин аплет који омогућава прављење петљи саморепликације
• (језик: енглески) Колекција преко 10 различитих аплета за ћелијски аутомат — у виртуелном лабу Монаш универзитета
• (језик: енглески) Golly — подржава Нојманов принцип, Нобили, ГОЛ и многе друге системе ћелијских аутомата (развијен од стране Томаса Рокицког и Ендруа Тревороуа; ово је једини симулатор који је тренутно доступан и може да демонстрира Фон Нојманов тип саморепликације)
• (језик: енглески) Wolfram Atlas — Атлас разних врста једнодимензионалних ћелијских аутомата
• (језик: енглески) „Конвејев живот” — Конвејева „Игра живота”
• (језик: енглески) „Прво реплицирајуће створење настало у симулатору живота”
• (језик: енглески) Математика модела референци — општи водич за CA, интерактивни аплети, бесплатан код и извори за CA као модел фундаменталне физике
• (језик: енглески) Fourmilab лабораторија за ћелијске аутомате
• (језик: енглески) Busy Boxes — 3D реверз. („SALT” архитектура за CA)
• (језик: енглески) Репозиторијум ћелијских аутомата — CA истраживачи, историјске везе, бесплатан софтвер, књиге и још много тога