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

Содержание
Введение
Глава 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. остроение монофункционального класса КА с неразрешимым
свойством обратимости
Литература