Предварительная программа курса.

Клеточные автоматы вошли в научно-популярную литературу, пожалуй с появлением Конвеевской игры «Жизнь». Простые правила описывают состояние каждой клетки доски на следующем шаге в зависимости от её состояния и состояний её соседей. С тех пор в одной только игре «Жизнь» было найдено очень много красивых конфигураций, а кроме того получили известность несколько наборов похожих правил.

В математике это понятие изучается или применяется в достаточно разных областях и с разными целями. Я попытаюсь показать примеры этого, рассказать используемые при этом понятия, объяснить смысл некоторых вопросов.

1. Наглядные примеры

   Игра Конвея «Жизнь». Стандартные конфигурации. Периодические конфигурации, глайдеры и глайдерные ружья, сады Эдема, вычисления на поле игры.

   Другие известные клеточные автоматы на клетчатой бумаге. Правила Seeds, Billiard Ball Machine, Falling Sand..

2. Клеточные автоматы как модель — вычислений, передачи информации или кристалла.

   Задача о синхронном выстреле в шеренге стрелков. Судороги простого клеточного автомата. Клеточные автоматы для несложных вычислений. Вопросы синхронизации обновления состояния для клеточных автоматов.

   Модель Изинга.

3. Статистический подход.

   Вероятностные правила.

   Склеивает ли автомат состояния? Можно ли в нём хранить информацию? Как меняется его поведение при изменении параметров?

   Фазовые переходы между стабильностью и случайностью при изменении вероятностей переходов. Как выглядят фазовые переходы на конечных и бесконечных решётках.

4. Использование клеточных автоматов и вычислений для замощений плоскости.

   Как создать набор раскрашенных плиток, чтобы все замощения плоскости этими плитками с согласованием цветов на касающихся сторонах были непериодическими? Один из способов, которые хорошо обобщаются на более сложные задачи такого рода — встроить в сами правила согласования цветов правила некоторого вычисления с помощью клеточного автомата.

В начале курса я постараюсь показать красивые сюжеты, не опираясь ни на какие знания. К концу курса понадобятся начальные знания теории вероятностей и какие-то представления про алгоритмы.