Клеточные автоматы

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

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

 

Функціонування -вимірних ОС відбувається у дискретній шкалі часу і визначається локальною функцією переходу , яка повертає стан кожного елементарного автомата в момент часу на основі станів всіх його сусідів в момент часу . Іншими словами, локальна функція переходу – це будь-яке відображення  . Для часто використовують позначення . Стабільними структурами називаються ОС, чия локальна функція переходу задовольняє , тобто структури с обмеженням на швидкість передачі інформації, в іншому випадку такі ОС називаються нестабільними.

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

 

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

 

3.  Основні види кліткових автоматів      

 

Для даних , і множина – це будь-яка непуста підмножина множини всіх глобальних функцій переходу, що визначається цими трьома компонентами. Якщо  містить тільки одну функцію , то така ОС називається моногенною або класичною. Функціонування класичної ОС дуже просте : якщо – початкова конфігурація в момент часу , то конфігурація структури в будь-який момент часу буде . У випадку існування більше чим однієї функції глобального переходу, то така -вимірна ОС називається полігенною і у кожен момент часу до поточної конфігурації застосовується одна із функцій глобального переходу з множини . Серед полігенних -вимірних ОС виділяють три основні групи структур:

• Детерміновані (у кожен момент часу застосування глобальної функції переходу відбувається за деяким алгоритмом);
• Недетерміновані (у випадку коли такий алгоритм відсутній);
• Стохастичні (глобальні функції переходу застосовуються за певним стохастичним законом)

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

 

 

де  – стани автомату;  - відповідно праві та ліві вхідні та вихідні імпульси -автомата структури.

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

 

 – це глибина рефрактерності  і  – це поріг збудження.

Символи з алфавіту відповідають певним характеристикам: стан спокою(0), збудження(1), і рефрактерності глибини (). Можна розглядати структури із сталою та змінною глибиною рефрактерності (як функцію числа імпульсів, що перевели автомат в стан збудженості)[1].

 

4.  Класи правил для найпростіших одновимірних кліткових автоматів

 

Найпростіші кліткові автомати – це одновимірні, з двома можливими станами (={0, 1}) і індексом сусідства . Локальну функцію переходу для таких автоматів часто називають просто правилом. Всього існує можливих правил. Кожному правилу відповідає число від 0 до 255 – код Вольфрама. У багатьох своїх роботах С. Вольфрам досліджував поведінку таких найпростіших кліткових автоматів і виділив чотири основних класи[4,5,7]:

• Клас 1: Майже всі початкові конфігурації переходять у стабільний, однорідний стан, будь-яка випадковість у початковій конфігурації зникає (рис. 1).
• Клас 2: Майже всі початкові конфігурації переходять у стабільні структури або структури, що повторюються. Проявляється деяка випадковість. Локальні зміни в початкових конфігураціях залишаються локальними (рис. 2).
• Клас 3: Майже всі початкові конфігурації еволюціонують в псевдовипадковій чи хаотичній манері. Будь-які стабільні структури швидко зникають під дією навколишнього шуму, локальні зміни в початковій конфігурації приводять до невизначених результатів (рис. 3). 
• Клас 4: Майже всі початкові конфігурації розвиваються складними та цікавими шляхами. Стабільні структури чи структури, що повторюються як в Класі 2 можуть появлятися але число кроків потрібне для цього дуже велике, навіть при дуже простих початкових конфігураціях. Локальні зміни в початковій конфігурації приводять до невизначених результатів (рис. 4).    

Рисунок 1 – привило 2

Рисунок 2 – правило 150

Рисунок 3 – правило 30

Рисунок 4 – правило 110

 

5.  Види правил для двовимірних кліткових автоматів

 

Навіть  найпростіші правила можуть створювати досить велике різноманіття явищ, що можуть бути застосовані в моделюванні. Ці правила будемо розглядати на прикладі двовимірних кліткових автоматів з індексом сусідства Мура.

1.5.1 Необмежений ріст 

 

Локальна  функція переходу (правило) може бути записана як:

, де – стан центрального автомата (центральної клітки) в наступний момент часу,  – стани автоматів сусідніх з центральним. Якщо ми почнемо з початкової конфігурації із однієї одиниці і всіх нулів, то ми отримаємо чорний квадрат (якщо інтерпретувати одиниці як чорні точки на екрані, а нулі – як білі), який росте з постійною швидкістю (рис. 5). Це приклад монотонного, необмеженого росту [3].

Рисунок 5

 

1.5.2 Обмежений ріст

 

В попередньому правилі ріст відбувався із максимально  можливою швидкістю. Можна зробити  цей процес росту більш вибірковим. Наприклад, в наступному правилі  клітка перейде в стан 1, якщо серед  її сусідів буде рівно одна клітка в стані 1, в іншому випадку вона залишається незмінною. Ми отримаємо  більш розріджену конфігурацію (рис. 6) чим у попередньому разі, вона матиме регулярний фрактальний характер [3].

Рисунок 6

 

1.5.3 Конкурентний ріст

 

Якщо  при певному числі сусідів  в стані 1 (можна сказати живих  кліток) центральна клітка переходить в стан 0 (вмирає), то такі правила  є правилами конкурентного росту. Відома гра  «Conway's Game of Life» також належить до цього класу правил. Відомо, що навіть прості механізми конкурентного росту здатні підтримувати універсальні в обчислювальному відношенні процеси. Наприклад, реалізуємо правило при якому клітка буде в стані 1, коли сума станів її сусідів дорівнює трьом, семи або восьми, якщо ж сума дорівнює чотирьом, то клітка перейде в стан 0, в іншому випадку клітка залишається незмінною (рис. 7) [3].

Рисунок 7

 

1.5.4 Правила голосування

 

Попередні два правила є правилами підрахунку, в яких поведінка клітки залежить тільки від того, скільки сусідів  знаходиться в певному стані. Наступна спеціалізація виникає, коли вклад кожного сусіда інтерпретується  як «голос» на користь певного  результату; будь-яке число голосів  більше за визначений поріг приведе  до цього результату. Наприклад, правило  «проста більшість»: клітка буде в  стані 1, якщо сума станів її сусідів  включно із нею буде більша або  рівна 5, в іншому випадку клітка перейде в стан 0. Можна дещо ускладнити це правило, ввівши деяку випадковість коли сума станів дорівнює 4 (клітка буде в стані 1 з імовірністю  і в стані 0 з імовірністю ) і 5 (клітка буде в стані 1 з імовірністю і в стані 0 з імовірністю ). Після певного часу кожна клітка починає вести себе так, ніби голосування відображає стан не тільки її сусідів, але, в меншій степені, і стану кліток, все більш далеких від неї. Границі областей знаходяться в стані неперервного переміщення. Кожна клітка може «відчувати» кривизну свого околу і буде динамічно регулювати свій стан так, щоб зробити границю більш прямою (рис. 8, рис. 9, рис. 10). Це можна використати для моделювання поверхневого натягу рідин [3].   

Рисунок 8 – р = 1/32, початковий стан випадковий, 1000 ітерацій

                               

Рисунок 9 – початкова конфігурація        Рисунок 10 – після 10000 ітерацій

1.5.5 Правило експоненціального затухання

 

Це правило  можна інтерпретувати як поведінку  великого числа запалених свічок під час дощу. Як тільки крапля дощу попадає на свічку, та гасне. З часом  число гасінь буде все меншим і  меншим, освітлення буде зменшуватися експоненціально. Суть правила полягає  в тому, що з певною імовірністю  кожна клітка переходить в стан 0 (затухає), а з імовірністю залишається незмінною. Процес затухання, що управляється цим простим стохастичним правилом можна побачити на рис. 11 і рис. 12 [3].

    

               Рисунок 11                                             Рисунок 12

 

 

 

ДЕЯКІ ЗАСТОСУВАННЯ КЛІТИННИХ АВТОМАТІВ 

 

  2.1 Однорідні  структури як формальна модель  обчислювальної техніки

 

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

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

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

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

Більш прикладні  аспекти теорії однорідних структур в обчислювальних науках можна класифікувати  як макрокліткові дослідження і  практичні розробки, коли в якості одиничного автомата ОС-моделі вибирається  структурно більш складніший автомат, взаємопов’язана поведінка якого і визначає структурні та динамічні властивості обчислювальної моделі. Мотивацією для таких досліджень є такі напрямки як кліткова логіка, паралельні обчислювальні пристрої, ітеративні і систолічні мережі, паралельні обчислення в реальному часі, адаптація, розпізнавання образів, обробка сигналів, кліткові процесори, робототехніка.

Е. Кодд, працюючи над клітковою моделлю  фон Неймана, зменшив число внутрішніх станів її одиничного автомата до восьми і зробив модель більш простою  і пригідною для практичних цілей. Подальші дослідження в цьому  напрямку привели до створення практичних реалізацій ОС-моделі у вигляді тка  званих кліткових процесорів Т. Легенді, а потім і кліткових -процесорів для моделей IBM PC/XT/AT. Клітковий -процесор являє собою однорідну матрицю із оючислювальних елементів, кожен із яких може виконувати 16 локальних функцій переходу. З матрицею асоційовано два блоки локальної пам’яті по 256Кб і блок управління. Вони успішно використовуються для вирішення таких задач як розпізнавання образів, обробка сигналів, управління технологічними процесами, всі типи кліткових булевих обчислень, операції з базами даних,  експертними системами і цілого ряду інших.

Інший досить інтересний підхід до практичної реалізації обчислювальної ОС-моделі запропонував Т. Тофоллі[3], створивши серію так званих кліткових машин (Cellular Automata Machines – CAM-5, CAM-6). Ряд авторів уже зараз пропонують практичні підходи до реалізації перспективних надвеликих інтегральних схем на основі ОС-моделей. У зв’язку із розвитком технології інтегральних схем (де сама специфіка виготовлення така, що там зручно створювати пристрої із ітеративною архітектурою) інтерес до теорії однорідних структур весь час зростає. Кліткова логіка має справу з математичними моделями і технікою для аналізу і синтезу цифрових сіток на основі обчислювальних ОС-моделей.