Целуларни аутомат

Госперов једрилица пиштољ створен у "једрилици" ћелијског аутомата Конвејеве игре живота

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

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

Концепт је првобитно откривен 1940 од стране Станислава Уламови и Џон фон Нојмана док су били савременици у Лос Аламос Националној Лабораторији. Док су студирали током 1950-их и 1960-их , није га било све до 1970-тих и Конвејева Игра живота, дводимензионални ћелијски аутомат ,интересовање за ову тему се проширило изван академских кругова. Током 1980-их , Стивен Волфрам ангажован на систематичној студији једно-димензионалног ћелијског аутомата , или оно што он назива основном Ћелијског Аутомата ; његов асистент Матеј Кук је показао да један од тих правила је Тјурингова потпуност. Волфрам је објавио нову врсту науке 2002. године , тврдећи да ћелијски аутомати имају примену у многим областима науке. Ово укључује компјутерске процесоре и криптографију.

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

Преглед

Један од начина да се симулира дводимензионални ћелијски аутомат је са бесконачним листом граф папира заједно са сетом правила за ћелије које треба да се прате. Сваки квадрат се зове "ћелија" и свака ћелија има два могућа стања, црно и бело. Насеље ћелије је у близини, обично поред ћелије. Два најчешћа типа насеља су насеља фон Нојмана и комшилук Мур. Бивши, назван по оснивању ћелијског аутомата теоретичар, састоји се од четири ортогонално суседне ћелије. The latter includes the von Neumann neighborhood as well as the four remaining cells surrounding the cell whose state is to be calculated. Последња обухвата насеље фон Нојмана, као и четири преостале ћелије окружујући ћелију чије стање је да се обрачунава. За такве ћелије и њихова Мурова окружења, постоје 512 (= 2⁹) могућих образаца. За сваку од 512 могућих образаца, правило је да се изјасни да ли ће центар бити ћелија црна или бела на следећем временском интервалу. Конвејева игра живота је популарна верзија овог модела. Други уобичајени тип насеља је проширено фон Нојманово насеље, који обухвата две најближе ћелије у сваком смеру ортогонално, за укупно осам. Општа једначина за такав систем правила је к^кs, где је к број могућих стања за ћелију, а s је број суседних ћелија (укључујући ћелију да се израчунава) користи се за одређивање следећих стања у ћелијама. Тако, у дводимензионалном систему са суседство Мура, укупан број аутомата могућ би био 2²⁹ или 1,34 × 10¹⁵⁴.

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

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

Ћелијски аутомати су чешће симулирани на коначну мрежу него бесконачно један. У две димензије, универзум ће бити правоугаоник уместо бесконачног авиона. Очигледан проблем са ограниченом мрежа је како да се одрже ћелије на ивицама. Како су рукуван то ће утицати на вредности свих ћелија у мрежи. Један могући метод је да се дозволи вредност у тим ћелијама да остане константна. Други метод је различито дефинисање окружења за ове ћелије. Могло би се рећи да имају мање суседе, али онда би такође морало да се дефинишу нова правила за ћелије које се налазе на ивицама. Ове ћелије се обично рукује са тороидалним аранжманима: када иде са врха, долази у на одговарајућу позицију на дну, а када се угаси са леве стране, долази у десно. (Ово у суштини симулира бескрајне периодичне плочице, а у области парцијалних диференцијалних једначина се понекад назива и периодични гранични услови.) То може да се сагледа као да снима са леве и десне ивице правоугаоника да формира тубу, затим снима врх и доња ивица цеви да се формира торус (крофна облик). Универзуми других димензија су на сличан начин поступали. Ово решава граничне проблеме са насељима, али још једна предност је у томе што се лако програмира помоћу модуларне аритметичке функције. На пример, код 1-димензионалног ћелијског аутомата као примери испод, насеље ћелије xit је {xi−1t−1, xit−1, xi+1t−1},где t је време корака (вертикално), и i је индекс (хоризонтални) у једној генерацији.

Историја

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

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

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

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

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

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

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

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

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

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

Волфрам, у новој врсти науке и неколико радова који датирају из средине 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. Број радова су анализирали и упоредили ових 256 ћелијских Аутомата.Правило 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-димензионалних јединица хиперкуба. Ова јединица Хиперкуба је простор правила ћелијског аутомата. За следећи најближи сусед ћелијског аутомата, правило је одређено са 25 = 32 бита, а правило простора 32- димензионалне јединице хиперкуба. Удаљеност између два правила може се дефинисати по броју корака потребних за прелазак са једног темена, што представља прво правило , и другог темена , представљајући још једно правило, дуж ивице хиперкуба. Ово правило-ка-правилу удаљености се назива и Хамингова удаљеност.

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

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

Биологија

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

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

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

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

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

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

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

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

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

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

Апликације

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Види такође

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

Напомене

• 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 0-19-853100-1. 
• Chopard, Bastien; Droz, Michel (2005). Cellular Automata Modeling of Physical Systems. Cambridge University Press. ISBN 0-521-46168-5. 
• 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., Univ. 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
• A.M. Turing. 1952. The Chemical Basis of Morphogenesis. Phil. Trans. Royal Society, vol. B237. pp. 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"

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

• Cellular Automata entry by Francesco Berto & Jacopo Tagliabue in the Stanford Encyclopedia of Philosophy
• Mirek's Cellebration – Home to free MCell and MJCell cellular automata explorer software and rule libraries. The software supports a large number of 1D and 2D rules. The site provides both an extensive rules lexicon and many image galleries loaded with examples of rules. MCell is a Windows application, while MJCell is a Java applet. Source code is available.
• Modern Cellular Automata – Easy to use interactive exhibits of live color 2D cellular automata, powered by Java applet. Included are exhibits of traditional, reversible, hexagonal, multiple step, fractal generating, and pattern generating rules. Thousands of rules are provided for viewing. Free software is available.
• Self-replication loops in Cellular Space – Java applet powered exhibits of self replication loops.
• A collection of over 10 different cellular automata applets (in Monash University's Virtual Lab)
• Golly supports von Neumann, Nobili, GOL, and a great many other systems of cellular automata. Developed by Tomas Rokicki and Andrew Trevorrow. This is the only simulator currently available that can demonstrate von Neumann type self-replication.
• Wolfram Atlas – An atlas of various types of one-dimensional cellular automata.
• Conway Life
• First replicating creature spawned in life simulator
• The Mathematics of the Models of Reference, featuring a general tutorial on CA, interactive applet, free code and resources on CA as model of fundamental physics
• Fourmilab Cellular Automata Laboratory
• Busy Boxes, a 3-D, reversible, SALT-architecture CA
• Cellular Automata Repository (CA researchers, historic links, free software, books and beyond)