Вікіпедія

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

дискретна модель, що вивчається у інформатиці
(Перенаправлено з Теорія клітинних автоматів)

Кліти́нний автома́т (КА) — дискретна математична модель, яка визначає сукупність та описується набором клітинок, що утворюють періодичну решітку, та заданими правилами переходу, що визначають стан клітини за теперішнім станом самої клітинки та тих її сусідів, що знаходяться від неї на певній відстані, яка не перевищує максимальну.

Гармата планерів у грі «життя»[1]

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

Можливі визначення

ред.

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

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

Критерії КА

ред.

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

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

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

Властивості КА

ред.

Стани елементів

ред.

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

Геометрія

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

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

Сусідство

ред.

Сусіди — це елементи, від яких залежить елемент КА. Можна назвати поняття сусідства ключовим для КА. При тому сусідство розуміється не в геометричному сенсі, а в інформаційному. Хоча зазвичай інформаційний сенс накладається на геометричний. Сусідство одиничних автоматів встановлюється постійним для кожного одиничного автомата решітки і визначається спеціальним вектором — індексом сусідства. Як правило, розглядаються 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

Література

ред.
Отримано з https://uk.wikipedia.org/w/index.php?title=Клітинний_автомат&oldid=36277808