Одновимірні кліткові автомати

В одновимірному (лінійному) КА решітка представляє собою ланцюжок клітинок (одновимірний масив), в якій для кожної з них, крім крайніх, є по два сусіди. Для усунення крайових ефектів решітка «загортається» у тор. Це дозволяє використовувати наступне співвідношення для всіх клітин автомата

y '[i] = f (y [i-1], y [i], y [i +1]),

де f – функція переходів клітинки;

y '[i] – стан i-ої клітинки в наступний момент часу;

y [i-1] – стан (i-1)-ої клітинки в даний момент часу;

y [i] – стан i-ої клітинки в даний момент часу;

y [i +1] – стан (i +1)-ої клітинки в даний момент часу.

Розглянемо три автомати, що відрізняються функцією переходів клітини. Решітка кожного з цих автоматів є ланцюжком з 61 клітинки, кожна з яких може перебувати в одному з двох станів.

Приклад 1. Нехай функція переходів клітини має наступний вигляд:

y '[i] = y [i-1]  y [i]  y [i +1],

Як вихідні значення виберемо одиницю для центральної клітини і нуль – для всіх інших клітин.

Можна представити поведінку КА у часі. Назвемо її «піраміда».

Приклад 2. Якщо, зберігаючи функцію переходів, у початковій конфігурації решітки змінити стан ще однієї клітинки з нуля на одиницю, то поведінка автомата стає іншою. Вона може бути названо «гори».

Приклад 3. Другий КА характеризується наступного функцією переходів:

y '[i] = y [i-1]  y [i]  y [i +1],

де  – символ логічної операції «сума по модулю два».

Вибираючи в якості початкового таке саме заповнення решітки, що й у прикладі 1, отримаємо поведінку, яка може бути названо «проділ».

Приклад 4. Виберемо для третього КА наступну функцію переходів:

y '[i] = y [i-1]  y [i]  y [i +1].

Цей автомат, при тих же початкових умовах, що і в попередньому прикладі, породжує фрактальну поведінку. Він є досить простою моделлю, яка демонструє самовідтворення.

Двовимірні кліткові автомати

Окіл з восьми клітинок

У двовимірному (площинному) КА решітка реалізується двовимірним масивом. У ній кожна клітина має вісім сусідів. Для усунення крайових ефектів решітка так само, як і в попередньому випадку, «загортається» у тор. Це дозволяє використовувати наступне співвідношення для всіх клітинок автомата:

y '[i] [j] = f (y [i] [j], y [i-1] [j], y [i-1] [j +1], y [i] [j +1] , y [i +1] [j +1], y [i +1] [j], y [i +1] [j-1], y [i] [j-1], y [i-1] [j-1]).

Приклад 5. Найбільш відомим із двовимірних КА є автомат, що моделює гру «Життя». У цьому автоматі, як і у всіх, розглянутих вище, клітинки можуть знаходитися в двох станах. Функція переходів клітинок реалізує наступні умови:

• якщо дана клітинка мертва (знаходиться у стані «нуль»), то вона оживе (перейде в стан «одиниця») за умови, що у неї є рівно три живих сусіда;

• якщо дана клітина жива, то вона залишиться живою тільки за умови, що у неї є два або три живі сусіда і помре в іншому випадку.

У цій грі інтерес представляє спостереження за розвитком популяції клітин при різних початкових умовах.

Приклад 6. Як приклад фрактальної поведінки розглянемо КА, що функціонує за правилом:

y '[i] [j] = y [i] [j]  y [i-1] [j]  y [i-1] [j +1] y [i] [j +1] 

y [i +1] [j +1]  y [i +1] [j]  y [i +1] [j-1]  y [i] [j-1]  y [i-1] [j-1].

Ця функція принципово не відрізняється від функції, наведеної в прикладі 4, так як вони обидві обчислюють суму за модулем два від станів всіх сусідів і самої клітинки.

Приведемо початкову конфігурацію решітки та результат її самовідтворення через вісім кроків.

Необхідно зазначити, що в силу властивостей функції «сума за модулем два», самовідтворення має місце після будь-якого числа кроків, що є степенем двох, починаючи зі значення, яке визначається співвідношенням

де a і b – ширина і висота «зародка», відповідно.