Prírodou inšpirované algoritmy

Výpočet druhej mocniny prirodzených čísel

Podkapitoly:

Applet

Nasledovný príklad demonštruje počítanie druhej mocniny prirodzeného čísla zredukovaný na zadanie vstupu – čiže počiatočnej podmienky celulárneho automatu a posúdenie stavu po konečnom počte krokov – čiže odčítanie počtu tmavozelených buniek v poslednej generácii. O jednoduchosti automatu vykonávajúceho takýto sofistikovaný výpočet sa môžeme presvedčiť na základe počiatočných podmienok a pravidiel tvoriacich lokálnu prechodovú funkciu.

Počiatočné podmienky

Tvorí ich reťazec: {..., 0, 0, 1, ..., 1, 3, 0, 0, ...} – Počet jednotiek je ekvivalentný hodnote prirodzeného čísla, z ktorého chceme počítať druhú mocninu. Sprava je pripojené jedno číslo 3 a celý tento reťazec je obkolesený nulami.

Lokálna prechodová funkcia (Wolfram, 2002)

{{0,_,3}->0, {_,2,3}->3, {1,1,3}->4, {_,1,4}->4, {1|2,3,_}->5, {p:0|1,4,_}->7-p, {7,2,6}->3, {7,_,_}->7, {_,7,p:1|2}->p, {_,p:5|6,_}->7-p, {5|6,p:1|2,_}->7-p, {5|6,0,0}->1, {_,p:1|2,_}->p, {_,_,_}->0}

Vysvetlivky k zápisu:

Zápis ,,{0,_,3}->0“ znamená: Ľavý sused bunky s ľubovoľnou hodnotou je 0, pravý sused je 3, hodnota bunky v nasledujúcej generácii na tej istej pozícii je 0.

Zápis „1|2“ znamená: 1 alebo 2

Zápis „p:0|1“ znamená: Ak p = 0 alebo p = 1

Počítanie prvočísel celulárnym automatom si môžete vyskúšať v demonštračnom applete.