102
правки
Изменения
Нет описания правки
== Правила ==
== Универсальность ==
{{Теорема
|statement = Игра "Жизнь" универсальнавычисляет то же множество функций, что и МТ.
|proof =
Для того, чтобы доказать этот факт, докажем возможность построения всех возможных Машин [[Машина_Тьюринга |машин Тьюринга]].
В состав машины Тьюринга МТ входит:
* неограниченная в обе стороны лента, разделённая на ячейки
* управляющее устройство, способное находиться в одном из множества состояний.
Заметим, что управляющая часть МТ считывает с ленты входную строчку и завершается, записав на ленту выходную строчку. Без ограничения общности, будем рассматривать бинарные строки. Следовательно, управляющая часть МТ есть булева функция.
<br>
Каждая Машина Тьюринга МТ вычисляет определенную вычислимую функцию. Так как мы можем записать управляющий автомат в виде строки, можно подать Машину Тьюринга МТ и входные данные на вход другой Машине ТьюрингаМТ. Следовательно, достаточно построить универсальную МТ.
<br>
Если показать, что мы можем построить в игре "Жизнь" любую булеву функцию, то мы сможем построить булеву функцию УМТ.
