Клітинний автомат

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук
Гармата планерів у грі «життя»[1]

Кліти́нний автома́т(КА) — сукупність, до якої входять:

  1. Набір клітинок, які утворюють періодичну решітку
  2. Задані правила переходу, що визначають стан клітини за теперішнім станом самої клітинки та тих її сусідів, що знаходяться від неї на певній відстані, яка не перевищує максимальну.

Основний напрям дослідження клітинних автоматів — алгоритмічна розв'язність якихось задач. Також розглядаються питання побудови початкових станів, при яких клітинний автомат вирішуватиме задану задачу. Залишається відкритим, наприклад, питання про можливість побудови машини Тюринга у грі «Життя».

Можливі визначення[ред.ред. код]

Поняття клітинних автоматів доволі обширне, тому можна знайти доволі багато різних визначень. Найпоширенішими є:

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

Критерії КА[ред.ред. код]

Класичні КА в загальному випадку відповідають наступним критеріям:

  • зміна значень всіх клітинок відбуваються одночасно після обчислення нового стану кожної клітинки решітки. Інакше порядок перебору клітин решітки при проходження ітеративного процесу суттєво впливав би на результат;
  • решітка однорідна. Неможливо відрізнити жодні два місця на решітці по ландшафту. Одна на практиці решітка виявляється кінцевою множиною клітин (адже неможливо виділити необмежений об'єм даних). В результаті можуть мати місце крайові ефекти, клітини, що стоять на межах решітку будуть відрізнятися за кількістю сусідів. Щоб уникнути цього можна ввести періодичні крайові умови;
  • взаємодії локальні. Лише околишні клітинки (як правило, сусідні) здатні вплинути на дану клітинку;
  • множина станів клітинки кінцева. Ця умова потрібна, щоб для отримання нового значення стану клітини треба було виконати кінцеву кількість операцій( але це не заважає використовувати клітини для зберігання чисел із плаваючою комою для розв'язку прикладних задач).

Якщо з будь-якого початкового стану можна привести клітинного автомат в будь-яку задану конфігурацію шляхом варіювання значення загального вхідного параметра, такий КА називають повним.

Властивості КА[ред.ред. код]

Стани елементів[ред.ред. код]

У кожний момент часу кожен елемент КА приймає один стан зі скінченного набору станів. У залежності від цих станів в наступний момент часу набір елементів може прийняти новий стан. Якщо для елементів КА множини можливих станів відрізняються, такий клітинний автомат називається полігенним. Але на практиці використовуються комірки з еквівалентною множинами можливих станів алгебраїчною структурою – лінійні КА.

Геометрія[ред.ред. код]

Клітинний автомат, комірками якого є шестикутники

Елементи можуть бути геометрично розташовані різноманітним чином. Розмірність простору може бути довільною, а число елементів – як безкінечним, так і скінченним. В останньому випадку виникає додаткова міра свободи в граничних умовах. Вони можуть бути різними, але на практиці використовуються постійні у часі (найчастіше – нульові) або періодичні граничних умовах. У динамічних КА геометрія може змінюватися з часом, а якщо геометрія різна на різних ділянках простору, такі кліткові КА називають неоднорідними.

Сусідство[ред.ред. код]

Сусіди – це елементи, від яких залежить елемент КА. Можна назвати поняття сусідства ключовим для КА. При тому сусідство розуміється не в геометричному сенсі, а в інформаційному. Хоча зазвичай інформаційний сенс накладається на геометричний. Сусідство одиничних автоматів встановлюється постійним для кожного одиничного автомата решітки і визначається спеціальним вектором – індексом сусідства. Як правило, розглядаються d-мірні регулярні решітки, в цілочислові точки яких поміщені копії деякого автомата Мура. Стан елемента в наступний момент часу обчислюється із стану самого елементу і його сусідів. Сусідство у більшій мірі визначається геометрією КА. Для різних цілей можлива зміна числа вхідних станів елемента. Якщо для кожного елемента КА число входів і виходів однакове, такий КА називається збалансованим.

Локальне правило[ред.ред. код]

Відповідно до локального правила змінюється стан елемента КА протягом часу. КА, в якому локальні правила різні для різних елементів, називається різнорідним. Локальне правило може бути недетермінованим, тобто змінюватися в часі або мати випадкову природу.

Класифікація[ред.ред. код]

Синхронні та асинхронні кліткові автомати[ред.ред. код]

У синхронних КА всі клітинки переходять у новий стан одночасно за сигналом глобального таймера. При цьому в якості вхідних станів використовуються старі стани сусідніх клітинок. У асинхронних КА клітинки переходять у новий стан у випадковому порядку, причому новий стан клітинки відразу може використовуватися її сусідами як вхідний.

Рухливі і нерухомі кліткові автомати.[ред.ред. код]

Рухливі КА характеризуються можливістю зміни положення клітинки в решітці під час еволюції системи. У нерухомих КА положення клітини під час еволюції залишається постійним.

Детерміновані та імовірносні кліткові автомати[ред.ред. код]

У детермінованих КА стан комірки αin+1 в наступний момент часу однозначно визначається станом цієї клітинки і її найближчих сусідів у попередній момент часу. У цьому випадку стан даного елемента в момент часу n +1 є однозначною функцією F від двох змінних - стану цього елемента і суми станів його найближчих сусідів у попередній момент часу n. При такому визначенні клітинний автомат не має пам'яті. КА з пам'яттю можна отримати, припустивши, що функція F залежить, наприклад, також від стану елемента в ще більш ранній момент часу. КА, в яких стани комірок в наступний момент часу визначаються на основі деяких ймовірностей, називаються імовірнісними КА (ІКА). У класичних ІКА правила переходів мають абстрактний характер і не пов'язані однозначно з реальними процесами, що відбуваються в модельованій системі. У таких автоматах при моделюванні процесу для кожної клітинки датчиком випадкових чисел генерується випадкове число Q (0 < Q < 1), що порівнюється з імовірністю w реалізації цього процесу. Якщо Q < w, то процес реалізується.

КА у вигляді звичайних диференційних рівнянь[ред.ред. код]

Іноді використовуються правила, записані у вигляді звичайних диференціальних рівнянь (клас КА-ЗДР). У цьому випадку стани комірок задаються набором змінних, значеннями яких можуть бути будь-які дійсні числа. Для таких автоматів диференціальні рівняння розв’язуються для кожної комірки окремо протягом фіксованого відрізку часу, при цьому кожна клітинка може мати різні початкові умови. Цей клас КА дуже щільно прилягає до диференціальних рівнянь в частинних похідних. Моделі типу КА-ЗДР займають проміжний стан між КА і ІКА, а також між простими КА і ДР в частинних похідних. Основною ідеєю КА-ЗДР є розбиття модельованої області на рівновеликі комірки і розв’язання системи ЗДР незалежно в кожній клітинці з різними початковими умовами. У деяких моделях просторове розташування комірок неістотне, а в інших кількість сусідніх комірок і розмірність простору відіграють вирішальну роль (випадки поширення хвиль або виникнення стаціонарних просторових структур у нерухомому середовищі). У моделях КА-ЗДР передбачається, що клітинка містить дуже велику кількість частинок, що дозволяє застосовувати ЗДР і неперервні функції. Ця обставина залишає тільки один спосіб для моделювання дифузії, а саме просте опосередкування концентрації по сусіднім коміркам.

За структурою[ред.ред. код]

За структурою КА поділяють в залежності від кількості вимірів. Найбільш вживані одно- та дво-вимірні.
У якості ґратки беруть поле, комірки якого є трикутники, чотирикутники чи шестикутники.

Одновимірні кліткові автомати[ред.ред. код]

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

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)-ої клітинки в даний момент часу.

Двовимірні кліткові автомати[ред.ред. код]

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

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]).

Конфігурації КА[ред.ред. код]

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

  • Мозаїчний автомат. КА, що використовує у локальному правилі кожного елемента не тільки стан елемента та його сусідів, але і значення загального вхідного параметра, який може змінюватися час від часу. Зміна цього параметра веде до перевизначення набору правил зміни станів у всьому просторі елементів КА. Якщо з будь-якого початкового стану можна привести клітковий автомат в будь-яку задану конфігурацію шляхом варіювання значення загального вхідного параметра, такий КА називають повним
  • Ітеративний автомат. КА, в якому лише один елемент використовує для зміни свого стану значення вхідного параметра
  • Односторонній клітковий автомат. Такий автомат припускає лише односторонню взаємодію елементів. Наприклад, в одновимірному масиві елементів значення кожного елемента залежить лише від його стану і від стану лівого (або правого) сусіда. Незважаючи на удавану вироджуваність звичайного КА, односторонні КА досить універсальні і використовуються для розпізнавання мовних форм
  • Л-система. Цей тип КА використовується для моделювання біологічних систем. Це динамічні КА (як правило, одно- чи двовимірні), в яких з часом один елемент може замінятися декількома або може бути видаленим із системи згідно з заданими правилами
  • Відмовостійка система. У таких системах моделюється робота КА в реальних умовах: з деякою ймовірністю кожен елемент КА може перейти в стан, що не відповідає локальному правилом. Завданням є створення алгоритмів, для яких робота КА буде правильною в незалежності від допущених помилок

Посилання[ред.ред. код]

  1. Daniel Dennett (1995), Darwin's Dangerous Idea, Penguin Books, London, ISBN 978-0-14-016734-4, ISBN 0-14-016734-X

Література[ред.ред. код]

  • И. И. Захарчук, «О сложности одномерных универсальных клеточных автоматов» — Дискретный анализ и исследование операций, октябрь—декабрь 2002. серия 1. том 9, № 4, 50-56
  • Лев Наумов, Анатолий Шалыто, «Клеточные автоматы. Реализация и эксперименты»

Див. також[ред.ред. код]