Що таке клітинний автомат
Клітинний автомат — це поле з клітинок, кожна з яких перебуває в певному стані (тут — жива або мертва) і змінюється кроками, що називаються поколіннями. На кожному кроці всі клітинки оновлюються одночасно за одним правилом, яке враховує лише вісьмох сусідів навколо кожної клітинки.
У «Життя» не можна виграти чи програти: ви вибираєте початкове положення, а решту роблять правила. Цікаво те, що з таких простих правил виникає дуже складна й непередбачувана поведінка, тому гру вивчають у математиці, інформатиці й навіть біології.
Правила простими словами
Дивляться на кількість живих сусідів кожної клітинки (вісім навколо неї, разом із діагональними) і застосовують такі правила одночасно по всьому полю:
- Жива клітина, що має менше двох живих сусідів, помирає від самотності.
- Жива клітина з двома або трьома живими сусідами залишається живою.
- Жива клітина, що має більше трьох живих сусідів, помирає від перенаселення.
- Мертва клітинка, що має рівно трьох живих сусідів, оживає.
Скорочений запис цих правил — B3/S23: B (від birth, народження) 3 означає, що клітина народжується за трьох сусідів, а S (від survival, виживання) 23 означає, що вона виживає за двох або трьох. Альтернативні правила інструмента використовують той самий запис, наприклад HighLife — це B36/S23, а «Насіння» — B2/S.
Одне покоління, обчислене вручну
Візьмімо блінкер: три живі клітини в горизонтальному ряду. Центральна має 2 живих сусідів, тож виживає. Крайні мають лише 1 сусіда, тож помирають. Клітинки прямо над центром і прямо під ним мають по 3 живих сусіди (усі три з ряду), тож оживають. Результат: вертикальний ряд із трьох клітин.
У наступному поколінні процес повторюється, і ряд знову стає горизонтальним. Тому блінкер — осцилятор із періодом 2. Спробуйте те саме з блоком, квадратом 2 × 2: кожна клітина має 3 сусідів, тож усі виживають, а жодна порожня клітинка не має 3 живих сусідів. Він не змінюється ніколи, тому його називають натюрмортом.
Історія: Конвей, Гарднер і журнал
Британський математик Джон Конвей вигадав гру 1970 року. Її популяризував Мартін Гарднер у своїй колонці математичних ігор у Scientific American, у жовтневому номері 1970 року, і відтоді вона породила величезну спільноту ентузіастів, які шукають і каталогізують візерунки.
З часом було доведено, що гра повна за Тюрингом: з відповідними фігурами вона в принципі може обчислити все, що обчислює комп'ютер. Це одна з причин, чому вона залишається відомою: необмежена складність із мінімальних правил.
Родини візерунків і які з них спробувати
Візерунки класифікують за поведінкою. Усі вони є в меню «Візерунок» інструмента під такими назвами:
| Родина | Візерунок | Що робить |
|---|---|---|
| Натюрморт | Блок, Вулик | Не змінюється ніколи: 4 клітини в блоку, 6 у вулика |
| Осцилятор | Блінкер, Жаба, Маяк | Період 2: починає спочатку кожні 2 покоління |
| Осцилятор | Пульсар | Період 3, 48 клітин у початковій фазі |
| Осцилятор | Пентадекатлон | Період 15 |
| Корабель | Глайдер | 5 клітин; просувається на 1 клітинку по діагоналі кожні 4 покоління |
| Корабель | Легкий космічний корабель | Перетинає поле по прямій, період 4 |
| Гармата | Гармата глайдерів Госпера | Випускає новий глайдер кожні 30 поколінь |
| Початковий хаос | R-пентаміно | 5 клітин, яким потрібно 1103 покоління, щоб стабілізуватися на нескінченній площині |
Гармату Госпера знайшов Білл Госпер 1970 року, і вона стала першим доказом того, що популяція може зростати без обмежень. Окрім цих візерунків, в інструменті є «Жолудь» і «Живучий (Diehard)», два крихітні візерунки, яким потрібно дуже багато часу, щоб визначитися.
Як користуватися інструментом «Гра «Життя»»
- Торкайтеся поля або проводьте по ньому, щоб малювати живі клітини (торкніться живої клітинки ще раз, щоб прибрати її), або виберіть візерунок у меню «Візерунок».
- Натисніть «Запустити». Кнопка «Одне покоління» просуває на один крок, щоб спокійно стежити за розвитком, а «Пауза» зупиняє все. Також можна користуватися клавіатурою, коли поле вибране: пропуск запускає або ставить на паузу, N робить один крок, R заповнює випадково, а C очищає.
- Налаштуйте «Швидкість», «Розмір поля» і «Правило», а також спробуйте «Випадково» (із налаштуванням «Щільність випадкового заповнення»), щоб почати з полем, повним клітин. «Очистити» робить поле порожнім.
- Увімкніть «Розфарбовувати за віком кожної клітини», щоб побачити, які ділянки стабільні довше. Угорі показано покоління та живі клітини, а інструмент повідомляє, коли поле стабілізується, входить у цикл або лишається без життя.
Усе обчислюється на вашому пристрої, і нічого не надсилається на сервер. Інструмент зберігає у вашому браузері налаштування (розмір, швидкість, правило), але не малюнок.
Експерименти, які варто зробити
- Завантажте глайдер і порахуйте, за скільки поколінь він зсувається на одну клітинку по діагоналі: це 4. Із з'єднаними краями він обходить поле й з'являється з іншого боку.
- Запустіть два глайдери на траєкторію зіткнення й подивіться, чим усе закінчиться: залежно від того, як вони зійдуться, вони можуть знищити одне одного або залишити натюрморт.
- Завантажте гармату Госпера на поле розміром щонайменше 48 × 48 і порахуйте, скільки часу їй потрібно, щоб випустити кожен глайдер: 30 поколінь.
- Завантажте R-пентаміно на велике поле й порівняйте результат із з'єднаними краями та без них. На нескінченній площині йому потрібно 1103 покоління, щоб стабілізуватися, але на скінченному полі результат змінюється.
- Змініть правило з тим самим малюнком. За правилом «Насіння» (B2/S) кожна клітина помирає на кожному поколінні, і лишаються тільки народження, тож малюнок розширюється назовні; за правилом «Лабіринт» (B3/S12345) з'являються структури на кшталт коридорів.
Обмеження скінченного поля
Оригінальна гра відбувається на нескінченній площині. Поле інструмента має фіксований розмір, тому те, що досягає краю, поводиться інакше: із з'єднаними краями воно знову входить з протилежного боку (поле стає чимось на кшталт бублика), а без з'єднання гасне об стінку.
Тому великим візерункам потрібне місце (гармата Госпера потребує щонайменше 48 × 48), а деякі, як-от R-пентаміно, можуть закінчити інакше, ніж на необмеженій площині. Якщо візерунок не вміщується, інструмент пропонує вибрати більше поле.
Поширені запитання
Які правила гри «Життя» Конвея?
Жива клітина з 2 або 3 живими сусідами залишається живою; з менше ніж 2 помирає від самотності, а з більше ніж 3 — від перенаселення. Мертва клітинка з рівно 3 живими сусідами оживає. Коротко це записують як B3/S23.
Що означає B3/S23?
B — це народження (birth), а S — виживання (survival). B3 означає, що клітина народжується за 3 живих сусідів, а S23 — що виживає та, що має 2 або 3.
Що таке глайдер?
Це фігура з п'яти клітин, що рухається по діагоналі, на одну клітинку кожні 4 покоління. Це найвідоміший візерунок гри.
Хто винайшов гру «Життя»?
Британський математик Джон Конвей, 1970 року. Мартін Гарднер оприлюднив її того ж року в журналі Scientific American.
Чому мій малюнок зникає або завмирає?
Це найчастіше: багато малих фігур згасають або стабілізуються за кілька поколінь. Спробуйте іншу початкову позицію, більше поле або «Випадково».