Изменения

{{Теорема

|statement = Игра "Жизнь" вычисляет то же множество функций, что и МТ.

Для того, чтобы доказать этот факт, докажем возможность построения всех возможных [[Машина_Тьюринга |машин Тьюринга]].

В состав МТ входит:

* неограниченная в обе стороны лента, разделённая на ячейки

* ленту(с ячейками памяти)

* головку записи-чтения

===Базовые конструкции===

Рассмотрим базовые конструкции необходимые для построения этих элементов МТ.

В игры "Жизнь" можно построить различные конструкции (см. рис.):

* стабильные {{---}} не меняются с течением времени(первые два ряда)

<br><br>

===Память===

===Часы===

В клеточных автоматах изначально есть часы, так как время увеличивается. Но в МТ необходимо, например, через определенное время передвигать головку записи, передавать информацию и пр. Для этой цели можно использовать планеры или космические корабли, так как они двигаются с известной скоростью. Следовательно, в качестве часов используем glider gun.

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

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

<br>

Если показать, что мы можем построить в игре "Жизнь" любую булеву функцию, то мы сможем построить булеву функцию УМТ.

Из курса дискретной математики [[Полные системы функций. Теорема Поста о полной системе функций |известно]], что <tex>NAND</tex> - полная система, т.е. с его помощью можно построить любую. Следовательно, чтобы построить любую булеву функцию, нам нужно просто построить <tex>NAND</tex>, то есть <tex>NOT</tex> и <tex>AND</tex> в игре "Жизнь".

===Построение NOT===

===Построение AND===

}}