Игра «Жизнь»
Игра «Жизнь» (англ. Conway's Game of Life) — клеточный автомат, придуманный английским математиком Джоном Конвеем в 1970.
Содержание
Правила
- Правило 1. Действие происходит на бесконечной плоскости, разделенной на клетки, которую можно иногда представить как зацикленную конечную
- Правило 2. Каждая клетка может находиться в двух состояниях: быть живой или быть мёртвой
- Правило 3. У каждой клетки соседей
- Правило 4. Если клетка жива и у нее живых соседа, то она остается живой, иначе умирает
- Правило 5. Если клетка мертва и у нее живых соседа, то она становится живой, иначе остается мертвой
- Правило 6. Игра прекращается, если на поле не останется ни одной живой клетки
- Правило 7. Игра прекращается, если при очередном шаге ни одна из клеток не меняет своего состояния
- Правило 8. Игра прекращается, если конфигурация на очередном шаге в точности повторит себя же на одном из более ранних шагов
Универсальность
Теорема: |
Игра «Жизнь» вычисляет то же множество функций, что и МТ. |
Доказательство: |
Для того, чтобы доказать этот факт, докажем возможность построения всех возможных машин Тьюринга.
Базовые конструкцииРассмотрим базовые конструкции необходимые для построения этих элементов МТ.
ПамятьЯчейки памяти можно построить с помощью стабильныx конструкций Булевы функцииЗаметим, что управляющая часть МТ считывает с ленты входную строчку и завершается, записав на ленту выходную строчку. Без ограничения общности, будем рассматривать бинарные строки. Следовательно, управляющая часть МТ есть булева функция.
Построение NOTРассмотрим поток данных, состоящий из планеров. Наличие планера — Построение ANDСм. рисунок. Пусть ![]() |
См.также
- Rendell, P. (2014) Turing machine universality of the game of life. PhD, University of the West of England. Available from: http://eprints.uwe.ac.uk/22323