Ячейки памяти можно построить с помощью стабильны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
