|
|
| Строка 1: |
Строка 1: |
| − | {{Определение
| |
| − | |id=def1
| |
| − | |definition='''Игра "Жизнь''' (англ. ''Conway's Game of Life'') — клеточный автомат, придуманный английским математиком Джоном Конвеем в 1970 году.
| |
| − | }}
| |
| | | | |
| − | == Правила ==
| |
| − | * Действие происходит на бесконечной плоскости, разделенной на клетки
| |
| − | * Каждая клетка может находиться в двух состояниях: быть живой или быть мёртвой
| |
| − | * У каждой клетки 8 соседей
| |
| − | * Если клетка жива и у нее 2-3 живых соседа, то она остается живой, иначе умирает
| |
| − | * Если клетка мертва и у нее 3 живых соседа, то она становится живой, иначе остается мертвой
| |
| − | * Игра прекращается, если на поле не останется ни одной живой клетки
| |
| − | * Игра прекращается, если при очередном шаге ни одна из клеток не меняет своего состояния
| |
| − | * Игра прекращается, если конфигурация на очередном шаге в точности повторит себя же на одном из более ранних шагов
| |
| − |
| |
| − | == Универсальность ==
| |
| − | {{Теорема
| |
| − | |statement = Игра "Жизнь" универсальна.
| |
| − | |proof =
| |
| − | Для того, чтобы доказать этот факт, докажем возможность построения всех возможных Машин Тьюринга.
| |
| − |
| |
| − | В состав машины Тьюринга входит:
| |
| − | * неограниченная в обе стороны лента, разделённая на ячейки
| |
| − | * управляющее устройство, способное находиться в одном из множества состояний.
| |
| − | <br>
| |
| − | Доказательство строится на том, что простая логика, необходимая для построения МТ, может быть построена в игре "Жизнь":
| |
| − | * детерминированный конечный автомат(с часами)
| |
| − | * ленту(с ячейками памяти)
| |
| − | * головку записи-чтения
| |
| − | ===Базовые конструкции===
| |
| − | Рассмотрим базовые конструкции необходимые для построения этих элементов МТ.
| |
| − | [[Файл:Types.png|250px|thumb|right]]
| |
| − | [[Файл:Glidergun.png|100px|thumb|left| Glider gun]]
| |
| − | [[Файл:Eater.png|100px|thumb|left| Glider eater]]
| |
| − |
| |
| − | В игры "Жизнь" можно построить различные конструкции:
| |
| − | * стабильные - не меняются с течением времени(первые два ряда - рисунок)
| |
| − | * циклические - принимают исходное положение каждые n итераций (третий ряд - рисунок)
| |
| − | * планер(glider) - фигура, которая смещается на одну клетку вниз и в право каждые 4 итерации(4 ряд - рисунок)
| |
| − | * космический корабль - фигура, которая смещается ортогонально на 1 клетку каждые 4 итерации
| |
| − | * glider gun - фигура, бесконечно производящая планер каждые 30 итераций
| |
| − | * glider eater - фигура, поглощающая планеры
| |
| − | <br><br><br>
| |
| − | <br><br>
| |
| − | ===Память===
| |
| − | Ячейки памяти можно построить с помощью стабильныx конструкций. [[Файл:Memory.png|150px]]<br>
| |
| − | Можно также построить c помощью планеров: наличие планера - 1, отсутствие - 0. [[Файл:Datatransmission.png|150px]]
| |
| − | <br>
| |
| − | ===Часы===
| |
| − |
| |
| − | В клеточных автоматах изначально есть часы, так как время увеличивается. Но в МТ необходимо, например, через определенное время передвигать головку записи, передавать информацию и пр. Для этой цели можно использовать планеры или космические корабли, так как они двигаются с известной скоростью. Следовательно, в качестве часов используем glider gun.
| |
| − |
| |
| − | ===Булевы функции===
| |
| − |
| |
| − | Заметим, что управляющая часть МТ считывает с ленты входную строчку и завершается, записав на ленту выходную строчку. Без ограничения общности, будем рассматривать бинарные строки. Следовательно, управляющая часть МТ есть булева функция.
| |
| − | <br>
| |
| − | Каждая Машина Тьюринга вычисляет определенную вычислимую функцию. Так как мы можем записать управляющий автомат в виде строки, можно подать Машину Тьюринга и входные данные на вход другой Машине Тьюринга. Следовательно, достаточно построить универсальную МТ.
| |
| − | <br>
| |
| − | Если показать, что мы можем построить в игре "Жизнь" любую булеву функцию, то мы сможем построить булеву функцию УМТ.
| |
| − | Из курса дискретной математики [[Полные системы функций. Теорема Поста о полной системе функций |известно]], что NAND - полная система, т.е. с его помощью можно построить любую. Следовательно, чтобы построить любую булеву функцию, нам нужно просто построить NAND, то есть NOT и AND в игре "Жизнь".
| |
| − | <br>
| |
| − |
| |
| − | ===Построение NOT===
| |
| − | [[Файл:Not.png|250px|thumb|right]]
| |
| − | Рассмотрим поток данных, состоящий из планеров. Наличие планера - 1, отсутствие - 0. Добавим поток планеров, состоящий только из 1. При столкновении планеры исчезают, следовательно на месте 1 образуется 0 и наоборот.
| |
| − | <br><br><br><br><br><br><br><br><br><br><br>
| |
| − | ===Построение AND===
| |
| − | [[Файл:And.png|250px|thumb|right]]
| |
| − | См. рисунок. Пусть x AND y, тогда y соударяется с NOT(x). Если NOT x = 1, то на выходе ничего не попадет, если NOT x = 0, то просто пройдет y.
| |
| − |
| |
| − | }}
| |
| − | <br><br><br><br><br><br><br>
| |
| − | == Построение ==
| |
| − | Подробное описание построения МТ можно найти здесь:
| |
| − | 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
| |
