Окіл з чотирьох клітин

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

Будемо розглядати як околи даної клітини лише ті з них, які мають загальну сторону з нею і називаються «головними сусідами».

Приклад 7. Для ілюстрації фрактальної поведінки автомата з таким околом виберемо наступну функцію переходів:

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

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

При цьому період повного самовідтворення обчислюється на основі співвідношення:

T = max ( ; ).

Для розглянутого «зародка» період самовідтворення по горизонталі , а по вертикалі – . Тому повний період самовідтворення T = 8.

Приведемо конфігурацію через чотири та вісім кроків.

Автомати з клітинами без пам'яті

Звернемо увагу на те, що у всіх розглянутих вище прикладах у функції переходів кожної клітинки, поряд з вхідними змінними, що відповідають її оточенню, входить також і змінна, яка відображає стан самої клітини. Тому цей клас КА може бути названий «автоматами з клітинок з пам'яттю».

Принципово інший клас КА виникає, якщо відмовитися від використання стану даної клітинки в якості вхідної змінної функції переходів. Такий клас назвемо «автоматами з клітинками без пам'яті».

При цьому зазначимо, що, незважаючи на те,що в автоматах цього класу клітинки пам’яттю не володіють, за рахунок перевизначення змінних, такі автомати в цілому мають пам'ять.

Цей клас автоматів є найпростішим, застосування якого забезпечує самовідтворення.

Приклад 8. Наведемо приклад найпростішого КА що забезпечує самовідтворення. Його можна побудувати, якщо у прикладі 4, за тих же початкових умов, спростити функцію переходів:

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

Гра «Життя»

Походження

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

Правила

Місце дії цієї гри – «всесвіт» – це розмічена на клітинки поверхня, безмежна, обмежена, або замкнута. У комп'ютерних реалізаціях гри найчастіше використовують поверхню тора. Кожна клітинка на цій поверхні може знаходитися в двох станах: бути живою або бути мертвою. Клітинка має вісім сусідів. Розподіл живих клітин на початку гри називається першим поколінням. Кожне наступне покоління розраховується на основі попереднього за такими правилами:

• Порожня (мертва) клітинка поруч із трьома живими клітинками‑сусідами оживає;

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

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

Ці прості правила призводять до величезного розмаїття форм, які можуть виникнути у грі.

Фігури

Незабаром після опублікування правил, було виявлено декілька цікавих шаблонів (варіантів розстановки живих клітин в першому поколінні), зокрема: r-пентаміно і планер (glider).

Деякі такі фігури залишаються незмінними в усіх наступних поколіннях, стан інших періодично повторюється, в деяких випадках зі зміщенням всієї фігури. Існує фігура (Diehard) всього з семи живих клітин, нащадки якої існують протягом 130 поколінь, а потім зникають.

Конвей спочатку припустив, що ніяка початкова комбінація не може призвести до необмеженого розмноження і запропонував премію в 50 доларів тому, хто доведе або спростує цю гіпотезу. Приз був отриманий групою з Массачусетського технологічного інституту, яка придумала нерухому повторювану фігуру, яка періодично створювала рухомі «планери». Таким чином, кількість живих клітин могло рости необмежено. Потім були знайдені рухомі фігури, котрі залишають за собою «сміття» з інших фігур.

Дотепер більш-менш склалася наступна класифікація фігур:

• Стійкі фігури: фігури, які залишаються незмінними;

• Періодичні фігури: фігури, у яких стан повторюється через деяку кількість поколінь;

• Рухливі фігури: фігури, у яких стан повторюється, але з деяким зсувом;

• Рушниці: фігури, у яких стан повторюється, але додатково з'являються рухливі фігури фігура;

• Паровози: рухливі фігури, які залишають за собою сліди у вигляді стійких або періодичних фігур;

• Пожирачі: стійкі фігури, які можуть пережити зіткнення з деякими рухливі фігурами.

Райський сад

Райським садом називається таке розташування клітинок, у якого не може бути попереднього покоління. Практично для будь-якої гри, стан клітин в якій визначається декількома сусідами на попередньому кроці, можна довести існування садів Едему, але побудувати конкретну фігуру набагато складніше.