Prírodou inšpirované algoritmy

Generovanie prvočísel

Podkapitoly:

Applet

Celulárny automat so šestnástimi možnými stavmi pre každú bunku, ktorý generuje prvočísla, má prechodovú funkciu oveľa komplikovanejšiu ako automat na počítanie druhej mocniny. V princípe sa jedná o ukážku toho, že takéto celulárne systémy majú schopnosť byť použiteľné aj pri zaujímavejších matematických úlohách.

Tento celulárny automat generuje v každej generácii postupne reťazec buniek reprezentujúci postupnosť prirodzených čísel. Prvá modrá bunka vľavo reprezentuje číslo 1. Ďalšie čísla 2, 3, ... nasledujú bezprostredne za ňou. Dĺžka postupnosti prirodzených čísel reprezentovanej takýmto reťazcom je rovná počtu generácií vygenerovaných od spustenia celulárneho automatu.

Počiatočné podmienky

Tvorí ich reťazec: {…, 0, 0, 10, 0, 4, 8, 0, 0, ...}

Lokálna prechodová funkcia (Wolfram, 2002)

{{13, 3, 13} -> 12, {6, _, 4} -> 15, {10, _, 3|11} -> 15, {13, 7, _} -> 8, {13, 8, 7} -> 13, {15, 8, _} -> 1, {8, _, _} -> 7, {15, 1, _} -> 2, {_, 1, _} -> 1, {1, _, _} -> 8, {2|4|5, _, _} -> 13, {15, 2, _} -> 4, {_, 4, 8} -> 4, {_, 4, _} -> 5, {_, 5, _} -> 3,{15, 3, _} -> 12, {_, x:2|3|8, _} -> x, {_, x:11|12, _} -> x-1, {11, _, _} -> 13, {13, _, 1|2|3|5|6|10|11} -> 15, {13, 0, 8} -> 15, {14, _, 6|10} -> 15, {10, 0|9|13, 6|10} -> 15, {6, _, 6} -> 0, {_, _, 10} -> 9, {6|10, 15, 9} -> 14, {_, 6|10, 9|14|15} -> 10, {_, 6|10, _} -> 6, {6|10, 15, _} -> 13, {13|14, _, 9|15} -> 14, {13|14, _, _} -> 13, {_, _, 15} -> 15, {_, _, 9|14} -> 9, {_, _, _} -> 0}

Vysvetlivky k zápisu:

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

Zápis „3|11“ znamená: 3 alebo 11

Zápis „x:11|12“ znamená: Ak x = 11 alebo x = 12