Игра «Жизнь»
Игра «Жизнь» (англ. Conway's Game of Life) — клеточный автомат, придуманный английским математиком Джоном Конвеем в 1970.
Содержание
Правила
- Правило 1. Действие происходит на бесконечной плоскости, разделенной на клетки, которую можно иногда представить как зацикленную конечную.
- Правило 2. Каждая клетка может находиться в двух состояниях: быть живой или быть мёртвой.
- Правило 3. У каждой клетки соседей.
- Правило 4. Если клетка жива и у нее живых соседа, то она остается живой, иначе умирает.
- Правило 5. Если клетка мертва и у нее живых соседа, то она становится живой, иначе остается мертвой.
- Правило 6. Игра прекращается, если на поле не останется ни одной живой клетки.
- Правило 7. Игра прекращается, если при очередном шаге ни одна из клеток не меняет своего состояния.
- Правило 8. Игра прекращается, если конфигурация на очередном шаге в точности повторит себя же на одном из более ранних шагов.
Универсальность
Теорема: |
Игра «Жизнь» вычисляет то же множество функций, что и МТ. |
Доказательство: |
Для того, чтобы доказать этот факт, докажем возможность построения всех возможных машин Тьюринга.
Базовые конструкцииРассмотрим базовые конструкции необходимые для построения этих элементов МТ.
ПамятьЯчейки памяти можно построить с помощью стабильныx конструкций, т.е. мы можем построить ленту МТ. Булевы функцииЗаметим, что управляющая часть МТ считывает с ленты входную строчку и завершается, записав на ленту выходную строчку. Без ограничения общности, будем рассматривать бинарные строки. Следовательно, управляющая часть МТ есть функция вида
Так как штрих Шеффера или NAND) является полной системой, то достаточно построить и . (Построение NOTРассмотрим поток данных, состоящий из планеров. Наличие планера — Построение ANDСм. рисунок. Пусть ![]() |
Следствие
Теорема (Следствие): |
Проблема останова игры «Жизнь» неразрешима. |
Доказательство: |
Заметим, что если существует МТ, которая по начальной конфигурации игры «Жизнь» может определить, завершается ли она, то та же МТ может определить останавливается ли любая МТ, что противоречит неразрешимости проблемы останова для МТ. |
См.также
- Неразрешимость исчисления предикатов первого порядка
- Задача о выводе в полусистеме Туэ
- Задача о замощении
- Однозначность грамматики
- Неразрешимость задачи об эквивалентности КС-грамматик
- Неразрешимость проблемы существования решения диофантова уравнения в целых числах