Игра «Жизнь»

Игра «Жизнь» (англ. Conway's Game of Life) — клеточный автомат, придуманный английским математиком Джоном Конвеем в 1970.

Правила

Правило 1. Действие происходит на бесконечной плоскости, разделенной на клетки, которую можно иногда представить как зацикленную конечную.

Правило 2. Каждая клетка может находиться в двух состояниях: быть живой или быть мёртвой.

Правило 3. У каждой клетки [math]8[/math] соседей.

Правило 4. Если клетка жива и у нее [math]2-3[/math] живых соседа, то она остается живой, иначе умирает.

Правило 5. Если клетка мертва и у нее [math]3[/math] живых соседа, то она становится живой, иначе остается мертвой.

Правило 6. Игра прекращается, если на поле не останется ни одной живой клетки.

Правило 7. Игра прекращается, если при очередном шаге ни одна из клеток не меняет своего состояния.

Правило 8. Игра прекращается, если конфигурация на очередном шаге в точности повторит себя же на одном из более ранних шагов.

Булевы функции

Теорема:

В игре «Жизнь» можно построить любую булеву функцию.

Доказательство:

[math]\triangleright[/math]

Базовые конструкции Glider gun Glider eater Базовые конструкции Рассмотрим базовые конструкции необходимые для построения. В игры «Жизнь» можно построить различные конструкции (см. рис.): стабильные — не меняются с течением времени (первые два ряда), циклические — принимают исходное положение каждые [math]n[/math] итераций (третий ряд), планер (glider) — фигура, которая смещается на одну клетку вниз и в право каждые [math]4[/math] итерации (четвертый ряд), космический корабль — фигура, которая смещается ортогонально на [math]1[/math] клетку каждые [math]4[/math] итерации, glider gun — фигура, бесконечно производящая планер каждые [math]30[/math] итераций, glider eater — фигура, поглощающая планеры. Булевы функции Так как [math]\triangledown[/math] (штрих Шеффера или NAND) является полной системой, то достаточно построить [math]NOT[/math] и [math]AND[/math], чтобы показать возможность построения любой булевой функции. Построение NOT Рассмотрим поток данных, состоящий из планеров. Наличие планера — [math]1[/math], отсутствие — [math]0[/math]. Добавим поток планеров, состоящий только из [math]1[/math]. При столкновении планеры исчезают, следовательно на месте [math]1[/math] образуется [math]0[/math] и наоборот. Построение AND См. рисунок. Пусть [math]AND(x, y)[/math], тогда y соударяется с [math]NOT(x)[/math]. Если [math]NOT(x) = 1[/math], то на выходе ничего не попадет, если [math]NOT( x) = 0[/math], то просто пройдет [math]y[/math].

[math]\triangleleft[/math]

Теорема:

Проблема останова игры «Жизнь» неразрешима.

Доказательство:

[math]\triangleright[/math]

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

[math]\triangleleft[/math]

См.также

• Неразрешимость исчисления предикатов первого порядка
• Задача о выводе в полусистеме Туэ
• Задача о замощении
• Однозначность грамматики
• Неразрешимость задачи об эквивалентности КС-грамматик
• Неразрешимость проблемы существования решения диофантова уравнения в целых числах

Источники информации

• Википедия — Жизнь (игра)
• Proving Life is Universal