Михаил Александрович Раскин
Квадратно-гнездовой подход, или немного про клеточные автоматы
М.А.Раскин планирует провести 4 занятия
Предварительная программа курса.
Клеточные автоматы вошли в научно-популярную литературу, пожалуй с появлением Конвеевской игры «Жизнь». Простые правила описывают состояние каждой клетки доски на следующем шаге в зависимости от её состояния и состояний её соседей. С тех пор в одной только игре «Жизнь» было найдено очень много красивых конфигураций, а кроме того получили известность несколько наборов похожих правил.
В математике это понятие изучается или применяется в достаточно разных областях и с разными целями. Я попытаюсь показать примеры этого, рассказать используемые при этом понятия, объяснить смысл некоторых вопросов.
- 1. Наглядные примеры
Игра Конвея «Жизнь». Стандартные конфигурации. Периодические конфигурации, глайдеры и глайдерные ружья, сады Эдема, вычисления на поле игры.
Другие известные клеточные автоматы на клетчатой бумаге. Правила Seeds, Billiard Ball Machine, Falling Sand..
- 2. Клеточные автоматы как модель — вычислений, передачи информации или кристалла.
Задача о синхронном выстреле в шеренге стрелков. Судороги простого клеточного автомата. Клеточные автоматы для несложных вычислений. Вопросы синхронизации обновления состояния для клеточных автоматов.
Модель Изинга.
- 3. Статистический подход.
Вероятностные правила.
Склеивает ли автомат состояния? Можно ли в нём хранить информацию? Как меняется его поведение при изменении параметров?
Фазовые переходы между стабильностью и случайностью при изменении вероятностей переходов. Как выглядят фазовые переходы на конечных и бесконечных решётках.
- 4. Использование клеточных автоматов и вычислений для замощений плоскости.
Как создать набор раскрашенных плиток, чтобы все замощения плоскости этими плитками с согласованием цветов на касающихся сторонах были непериодическими? Один из способов, которые хорошо обобщаются на более сложные задачи такого рода — встроить в сами правила согласования цветов правила некоторого вычисления с помощью клеточного автомата.
В начале курса я постараюсь показать красивые сюжеты, не опираясь ни на какие знания. К концу курса понадобятся начальные знания теории вероятностей и какие-то представления про алгоритмы.
Organization Committee e-mail:
dubna@mccme.ru