Ћелијски аутомат () је дискретни модел који се проучава унутар теорија информатике, математике, физике, сложеног адаптивног система, теоријске биологије и микроструктуре моделирања.
За ћелијске аутомате се такође користе и називи ћелијски простори (), мозаични аутомати (), хомогене структуре (), ћелијске структуре (), мозаичне структуре (), учестали низови () итд.
Ћелијски аутомат се састоји од правилне мреже ћелија, од којих је свака у једном од стања чији је број ограничен (није бесконачан) као што су укључено (1) и искључено (0), за разлику од комбинованих решетки пресликавања). Мрежа може бити у било којој од димензија, с тим да број тих димензија такође није бесконачан. За сваку ћелију, низ ћелија који се назива њеним суседством дефинисан је у односу на поменуту ћелију. Почетно стање (време ) одређује се бирањем стања за сваку од ћелија. Нова генерација се ствара (што повећава време функцијом ) према неком фиксном тј. тачно одређеном и непроменљивом правилу (углавном, математичка функција) које одређује ново стање сваке од ћелија зависно од тренутног стања ћелије и стања ћелија у њеном суседству. Најчешће, правило за „ажурирање” стања ћелија исто је за сваку ћелију и не мења се временом, а примењује се на целу мрежу истовремено (одједном). Међутим, изузеци постоје; на пример, стохастични ћелијски аутомат и асинхрони ћелијски аутомат.
десно|мини|400п|Госперова глидерска пушка () која ствара глидере у ћелијском аутомату Конвејева „Игра живота”
Концепт су први открили Станислав Мартин Улам и Џон фон Нојман 1940-их година, и то док су радили заједно у Националној лабораторији у Лос Аламосу (Нови Мексико, САД). Док су студирали током 1950-их и 1960-их, концепта није било, а све до 1970-их и појаве Конвејеве „Игре живота”, дводимензионалног ћелијског аутомата. Интересовање за ову тему тада се проширило и изван академских кругова. Стивен Волфрам је током 1980-их радио на систематској студији једнодимензионалног ћелијског аутомата, или како га он назива — елементарни ћелијски аутомат. Његов асистент Метју Кук показао је да је једно од тих правила Тјуринг-потпуно (рачунски универзално). Волфрам је објавио Нову врсту науке () 2002. године, тврдећи да ћелијски аутомати имају примену у многим областима науке. Ово укључује рачунарске процесоре и криптографију.
Класификација ћелијских аутомата Примарна класификација ћелијских аутомата, према ономе што је Волфрам навео, обележена је бројевима од 1 до 4. Чине је следеће класе (по наведеном реду): аутомати у којима се обрасци генерално стабилизују у хомогеност аутомати у којима обрасци еволуирају у углавном стабилне или осцилирајуће структуре аутомати у којима обрасци еволуирају на наизглед хаотичан начин аутомати у којима обрасци постају изузетно сложени и могу да трају дуго времена, са стабилним локалним структурама
Ова последња класа сматра се да је рачунски универзална тј. способна за симулацију Тјурингове машине.
Посебне врсте ћелијских аутомата су и реверзибилни аутомати (где само једна конфигурација води директно до оне следеће, узастопне) те тоталистички аутомати (у којима будућа вредност појединих ћелија зависи од укупне вредности групе суседних ћелија).
Ћелијски аутомати могу да симулирају разне системе из стварног живота, укључујући и биолошке и хемијске.
Преглед
Један од начина да се симулира дводимензионални ћелијски аутомат је коришћењем бесконачног листа граф папира, заједно са сетом правила за ћелије која треба да се прате. Сваки квадрат се зове ћелија, а свака ћелија има два могућа стања, црно и бело. Суседство ћелије чине оне најближе, обично околне ћелије које су непосредно уз ону која се посматра. Два најчешћа типа суседства су Фон Нојманово суседство и Мурово суседство.Kier, Seybold, Cheng . Мурово суседство је име добило по теоретичару-оснивачу ћелијског аутомата, а састоји се од четири ортогонално суседне ћелије. Последња обухвата Фон Нојманово суседство, као и четири преостале ћелије које окружују ћелију чије стање треба да се израчуна. За такву ћелији и њено Мурово суседство, постоји 29 = 512 могућих образаца. За сваки од 512 могућих образаца, табела са правилима одређивала би да ли ће централна ћелија бити црна или бела на следећем временском интервалу. Конвејева „Игра живота” је популарна верзија овог модела. Други уобичајен тип суседства је проширено Фон Нојманово суседство, које укључује две најближе ћелије у сваком од ортогоналних смерова, што даје укупно 8 ћелија. Општа једначина за такав систем правила је , где је број могућих стања за ћелију, а број суседних ћелија (укључујући и ћелију која се посматра) који се користи за одређивање следећег стања посматране ћелије.Bialynicki-Birula, Bialynicka-Birula . Према томе, у дводимензионалном систему са Муровим суседством, укупан могући број аутомата био би 229 ≈ 1,34 × 10154.
Обично се претпоставља да свака ћелија у свемиру на почетку има исто стање, осим за тачно одређен број ћелија у другим стањима; придруживање вредности стања зове се конфигурација. Уопштено говорећи, понекад се претпоставља да свемир започиње прекривен периодичним обрасцем, док тај образац нарушава само тачно одређен број ћелија. Ова друга хипотеза уобичајена је у једнодимензионалним ћелијским аутоматима.
лево|мини|320п|Торус, тороидални облик
Ћелијски аутомати се чешће симулирају на ограниченој мрежи него на мрежи која је бесконачна. У две димензије, свемир би био правоугаоник, а не (бесконачна) раван. Очигледан проблем са ограниченом мрежом је како да се интерпретирају крајње ћелије. То како се интерпретирају ове ћелије утицаће на вредности свих ћелија у мрежи. Једно могуће решење је да се омогући да вредност у тим ћелијама буде константна. Други метод је различито дефинисање суседстава за ове ћелије. Могло би се рећи да имају мање суседа, али онда би се такође морала дефинисати нова правила за ћелије које се налазе на крајевима. Ове ћелије се обично интерпретирају тороидалним принципом: када једна ћелија с врха нестане, друга — као замена — долази на одговарајућу позицију на дну; када нестане ћелија с леве стране, друга долази на десну страну. (Овиме се у суштини симулира бескрајно периодично „поплочавање”, а у области парцијалних диференцијалних једначина понекад се назива и периодичним граничним условима.) Ово може да се визуализира замишљањем приљубљивања леве и десне ивице правоугаоника чиме би се формирала цев, чије би се ивице (два круга на крајевима) потом спојиле формирајући торус (облик америчке крофне). Са свемирима других димензија поступа се на сличан начин. Овиме се решавају гранични проблеми са суседствима, а још једна предност је у томе што се ово да лако програмирати помоћу функција модуларне аритметике. На пример, код једнодимензионалног ћелијског аутомата приказаног испод, суседство ћелије је: , где је временски корак (вертикално), а индекс (хоризонтално) у једној генерацији.
Историја мини|Џон фон Нојман, Лос Аламос ознака ИД Станислав Улам, док је радио у Националној лабораторији Лос Аламос 1940, студирао је раст кристала, користећи једноставну мрежу решетке као његов модел. Истовремено, Џон фон Нојман, Уламов колега у Лос Аламосу, ради на проблему само-реплицираних система. Почетни дизајн, фон Нојман је основао на идеји једног робота градећи још један робот. Овај дизајн је познат као кинематички модел.. Cerebral Mechanisms in Behavior – The Hixon Symposium, John Wiley & Sons, New York. . Како је развио овај дизајн, фон Нојман је дошао да оствари велику тешкоћу изградње само-реплицираног робота, и на великој цени у пружању робота са „морем делова” из којих изграђује свој репликант. Нојман чита новине под називом „Генерална и логична теорија аутомата” на Хиксон симпозијуму 1948. године. Улам је био тај који предлаже коришћење дискретног система за стварање редукованог модела понављања самог себе. Нилс Ал Барицели обавља многе од најранијих истраживања ових модела вештачког живота.
Улам и фон Нојман су створили метод за израчунавање течног кретања крајем 1950-их. Покретачки Концепт методе је био да се размотри течност као група дискретних јединица и да се израчуна кретање сваког од њих на основу понашања својих суседа. Тако је рођен први систем ћелијског аутомата. Као Уламове решетке мреже, фон Нојманови ћелијски аутомати су дводимензионални, са својим само-репликаторима спроведеним алгоритмички. Резултат је био универзални копир и конструктор који ради у ћелијском аутомату са малим окружењем (само оне ћелије које се додирују су суседи; за фон Нојманов ћелијски аутомат, само ортогоналне ћелије), и са 29 стања по ћелији. Фон Нојман је дао доказ постојања, да ће посебан образац учинити бескрајне копије себе у оквиру датог ћелијског универзума пројектовањем конфигурације 200.000 ћелија које би могао да уради. Овај пројекат је познат као теселациони модел, и назива се фон Нојманов универзални конструктор.
Такође, 1940. Норберт Винер и Артуро Росенблуетх су развили модел ексцитабилног медија са неким од карактеристика ћелијског аутомата. Њихова специфична мотивација је математички опис импулса проводљивости у срцима система. Међутим њихов модел није ћелијски аутомат, јер медиј у којем се сигнали простиру је континуиран, а махање фронтова су криве. Прави ћелијски аутомат модел ексцитабилне медије је развијен и студиран од стране Ј. М. Гренберг и С. П. Хастингс 1978. године; види Гринберг-Хастингсов ћелијски аутомат. Оригинални рад Виенер и Росенблуетх садржи многе увиде и наставља да буде цитиран у савременим истраживачким публикацијама о срчаној аритмији и екситаблним системима.
Године 1960, ћелијски аутомати су проучавани као одређена врста динамичког система и повезивани са математичким пољем симболичке динамике по први пут. 1969. Густав О’Хедлунд, сабрао је многе резултате пратећи ове тачке гледишта у оно што се и даље сматра основним папиром за математичку студију ћелијског аутомата. Најосновнији резултат је карактеризација у Кертис - Хедлунд - Линдон теореми низа глобалних правила ћелијског аутомата као скуп непрекидних функција ендоморфских смена простора.
Године 1969. немачки компјутерски пионир Конрад Цузе је објавио своју књигу Прорачунати простор, предлажући да су физички закони универзума дискретни по природи, и да је цео универзум излаз детерминистичким рачунањима на једном ћелијском аутомату; „Цизе теорија” је постала темељ области студија под називом дигитална физика.
Године 1970, са два стања, дводимензионални ћелијски аутомат под називом Игра Живота постао је познат, посебно почетком рачунарске заједнице. Измислио их је Џон Конвеј и популаризовао Мартин Гарднер у чланку у часопису Scientific American, њена правила су следећа: Ако ћелија има два црна суседа, она остају иста. Ако има три црна суседа, постаје црна. У свим другим ситуацијама постаје бела. Упркос својој једноставности, систем постиже импресивну разноврсност понашања, променљивих између привидних случајности. Један од очигледних карактеристика игре живота је честа појава једрилица, аранжмана ћелија које у суштини се крећу преко мреже. Могуће је договорити аутомат тако да једрилица интеракцију обавља прорачунато, а после много труда је показано да Игра Живота може имитирати универзалну Тјурингову машину.Paul Chapman. То се посматра као углавном рекреативна тема, и мало праћених радова ван истражују специфичности игре живота и неколико повезаних правила почетком 1970-их.