Prírodou inšpirované algoritmy

Von Neumannov Celulárny Automat

Von Neumannov CA

Von Neumann nebol spokojný s konceptom kinematického automatu kvôli tzv. black-box problému (nebolo jasné ako konkrétne vyzerá senzor, ako výkonné rameno atd.). Riešenie ponúkol jeho priateľ a spolupracovník, matematik Stanislaw Ulam - inšpirovaný rastom kryštálov navrhol prostredie, tvorené pravidelnou mriežkou, akúsi šachovnicu, kde každé políčko predstavuje jednu bunku. Každá bunka predstavuje konečný automat, pracujúci so spoločným súborom pravidiel. Súbor takýchto buniek môžeme potom považovať za organizmus. Úloha sa tak dostala do roviny čistej logiky. Na základe Ulamovej schémy pretvoril Von Neumann svoj kinematický model na prvý bunkový - celulárny automat CA. Názov CA pochádza od Arthura Burksa, editora Neumannovych prác z tejto oblasti (Neumann, 1966).

Neumannov CA pozostával z 200 000 buniek, ktoré mohli mať 29 stavov. Tvorilo ho telo 80x400 buniek (obsahovalo zložky A, B a C - továreň, duplikátor a počítač z kinematického modelu) a dlhý výrastok z asi 150 000 buniek (analógia pásky Turingovho stroja). V dynamike CA sa prejavuje emergencia: jednoduché lokálne chovanie buniek sa skladá do zložitého globálneho chovania celého organizmu. Proces replikácie prebieha tak, že sa na jednom konci tela vysunie rameno, na ktorom sa postupne začína vytvárať kópia pôvodnej štruktúry. Celú činnosť riadia príkazy obsiahnuté na zmienenej "páske". Na konci sa celá informácia prenesie do potomka a ten sa potom oddelí.

Von Neumann nedokončil svoj dôkaz existencie takého CA, ten však bol neskôr publikovaný (Thatcher, 1964) na cca 50 stranách. Neumannov CA sa podarilo reálne implementovať až oveľa neskôr (Pesavento, 1995).