Обратимые клеточные автоматы

• Автор: Кучеренко, Игорь Викторович
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2012
• Место защиты: Москва
• Количество страниц: 147 с. : ил.

Содержание
Введение

Глава 1. Обратимые клеточные автоматы в функциональных

классах

1.1. Введение

1.2. Основные результаты главы

1.3. Неразрешимость свойства обратимости клеточных автоматов

в двумерном случае

1.4. Клеточные автоматы с фиксированным числом состояний ячейки

1.5. Бинарные клеточные автоматы с локальной функцией переходов из класса Поста

1.6. Невычислимость функции числа обратимых клеточных автоматов относительно конструктивной параметризации
1.7. Оценки числа обратимых клеточных автоматов. Вычислительные возможности обратимых клеточных автоматов
Глава 2. Обратимые клеточные автоматы в геометрических классах
2.1. Введение
2.2. Основные результаты главы
2.3. Клеточные автоматы с одномерным шаблоном соседства
2.4. Бинарные клеточные автоматы с переменной структурой и по-луплоскостным шаблоном соседства
2.5. Бинарные клеточные автоматы с переменной структурой и Т-шаб-
лоном соседства
2.6. Клеточные автоматы с Г-шаблоном соседства
2.7. Клеточные автоматы с фиксированным шаблоном соседства
Глава 3. Монофункциональные классы булевых клеточных ав-

томатов с неразрешимым свойством обратимости
3.1. Введение
3.2. Основные результаты главы
3.3. Оценка числа состояний головки МТ с неразрешимой проблемой остановки на унитарных словах
3.4. Построение монофункционального класса КА с неразрешимым свойством обратимости
Литература

Введение
Актуальность темы
Клеточные автоматы (КА) являются дискретными математическими моделями широкого класса реальных систем вместе с протекающими в них процессами. Важное семейство клеточных автоматов образуют обратимые КА, то есть такие, в которых не происходит потери информации в процессе их функционирования. Эти объекты имеют много приложений, в том числе в вопросах защиты информации.
Содержательно клеточный автомат представляет собой бесконечную автоматную схему, построенную следующим образом. Рассмотрим &-мерное евклидово пространство. Разобьем его на гиперкубы с единичным ребром, ребра которых параллельны осям координат. В каждый гиперкуб поместим один и тот же конечный автомат А с т входами и одним выходом. Разветвим выход автомата и соединим с входами его соседей одинаковым образом для всех гиперкубов в пространстве. Получим бесконечную однородным образом устроенную автоматную схему, которая и называется клеточным автоматом. Последовательность состояний отдельных автоматов А, содержащую состояния всех автоматов схемы, будет образовывать состояние клеточного автомата. Последовательность состояний клеточного автомата, возникающая при синхронной работе всех составляющих его конечных автоматов, называется функционированием клеточного автомата.
Понятие клеточного автомата возникло в результате усовершенствования модели Дж. фон Неймана [32], [33], [14], предложенной им для описания процессов самовоспроизведения в биологии и технике, и в описанном выше виде использовалось А. Берксом [25], Э. Муром [13], В. Б. Кудрявцевым,
А. С. Подколзиным, А. А. Болотовым [1] и другими исследователями. При этом данное понятие описывает достаточно широкий класс отображений -Ричардсон Д. показал, что любое вычислимое однородное отображение множества состояний некоторого клеточного автомата в себя само является клеточным автоматом [34].

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 0 0 0 0 1 1 0 0 0 0 1 1 0 0
1 0 Ьх л 0 1 1 0 Ьх л 0 1 1 0 Ьх л
1 0 0 0 0 1 1 0 0 0 0 1 1 0 0
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 0 0 0 0 1 1 0 0 0 0 1 1 0 0
1 0 Ьх л 0 1 1 0 Ьх л 0 1 1 0 Ьх л
1 0 0 0 0 1 1 0 0 0 0 1 1 0 0
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 0 0 0 0 1 1 0 0 0 0 1 1 0 0
1 0 Ьх л 0 1 1 0 л 0 1 1 0 Ьх л
1 0 0 0 0 1 1 0 0 0 0 1 1 0 0
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
Рис. 1.4. Пример фрагмента моделирующей конфигурации
2) Проверяем, что клетка, в которой находится ячейка, является моделирующей, иначе полагаем значение состояния ячейки неизменным.
3) Вычисляем значение локальной функции переходов КА <т(т) для битовой компоненты в соответствии со значениями состояний ячеек сг(т), представленных в окрестных клетках.
Возьмем некоторую конфигурацию д КА сг(т). Рассмотрим множество ячеек А КА <т(т), представленных в моделирующих клетках конфигурации д. Выберем некоторую связную компоненту А' в множестве А (соседними считаются ячейки, у которых координаты отличаются не более чем на единицу). Нетрудно видеть, что функционирование клеток, сопоставленных ячейкам А', моделирует поведение конфигурации клеточного автомата сг(т) “с поломками”, у которого в “возможно функционирующем” состоянии находятся ячейки, моделирующиеся в А1. В силу приведенного выше замечания, моделирующий КА <у(т)' будет обратим тогда и только тогда, когда обратим сг(т). Из того, что сг(т)' конструктивно строится по а(т) и свойство обратимости для КА вида ег(т) неразрешимо, получаем, что в классе СА(2, п) свойство обратимости также неразрешимо. Доказательство теоремы 2 закончено.