: '''Правило 8.''' Игра прекращается, если конфигурация на очередном шаге в точности повторит себя же на одном из более ранних шагов.
== Универсальность Булевы функции ==
{{Теорема
|statement = Игра В игре «Жизнь» вычисляет то же множество функций, что и МТможно построить любую булеву функцию.
|proof =
[[Файл:Types.png|250px|thumb|right|Базовые конструкции]]
[[Файл:Eater.png|150px|thumb|right| Glider eater]]
Для того, чтобы доказать этот факт, докажем возможность построения всех возможных [[Машина_Тьюринга |машин Тьюринга]].
<br>
В состав МТ входит:
* неограниченная в обе стороны лента, разделённая на ячейки,
* управляющее устройство, способное находиться в одном из множества состояний.
<br>
Доказательство строится на том, что простая логика, необходимая для построения МТ, может быть построена в игре «Жизнь»<ref>[http://eprints.uwe.ac.uk/22323 Rendell, P. (2014) Turing machine universality of the game of life. PhD, University of the West of England]</ref>.
<br>
===Базовые конструкции===
Рассмотрим базовые конструкции необходимые для построения этих элементов МТ.
<br><br>
В игры «Жизнь» можно построить различные конструкции (см. рис.):
* glider gun {{---}} фигура, бесконечно производящая планер каждые <tex>30</tex> итераций,
* glider eater {{---}} фигура, поглощающая планеры.
<br><br><br>
<br><br>
===Память===
[[Файл:Memory.png|200px|thumb|right|Стабильная ячейка]]
[[Файл:Datatransmission.png|150px|thumb|right|Передача данных]]
Ячейки памяти можно построить с помощью стабильныx конструкций, т.е. мы можем построить ленту МТ.<br>
Передачу данных можно осуществлять c помощью планеров: наличие планера {{---}} <tex>1</tex>, отсутствие {{---}} <tex>0</tex>.
<br>
===Булевы функции===
Заметим, что управляющая часть МТ считывает с ленты входную строчку и завершается, записав на ленту выходную строчку. Без ограничения общности, будем рассматривать бинарные строки. Следовательно, управляющая часть МТ есть функция вида <tex>f:\{0, 1\}^n \rightarrow \{0, 1\}^m </tex>, т.е. из бинарной строки в бинарную строку.Заметим, что можно построить функции такого вида из булевых функций <tex>f_i:\{0, 1\}^n \rightarrow \{0, 1\}</tex>:<tex>f(x_1, x_2, x_3 ... x_n) = f(f_1(x_1, x_2, x_3 ... x_n), f_2(x_1, x_2, x_3 ... x_n), ... f_m(x_1, x_2, x_3 ... x_n) </tex>.<br><br>Каждая МТ вычисляет определенную вычислимую функцию. Так как мы можем записать управляющий автомат в виде строки, можно подать МТ и входные данные на вход другой МТ. Следовательно, достаточно построить универсальную МТ.<br>Если показать, что мы можем построить в игре «Жизнь» любую булеву функцию, то мы сможем построить булеву функцию УМТ. Так как <tex>\triangledown</tex> ([[Определение_булевой_функции#.D0.91.D0.B8.D0.BD.D0.B0.D1.80.D0.BD.D1.8B.D0.B5_.D1.84.D1.83.D0.BD.D0.BA.D1.86.D0.B8.D0.B8|штрих Шеффера]] или NAND) является [[Полные системы функций. Теорема Поста о полной системе функций |полной системой]], то достаточно построить <tex>NOT</tex> и <tex>AND</tex>, чтобы показать возможность построения любой булевой функции.
===Построение NOT===
Рассмотрим поток данных, состоящий из планеров. Наличие планера {{---}} <tex>1</tex>, отсутствие {{---}} <tex>0</tex>. Добавим поток планеров, состоящий только из <tex>1</tex>. При столкновении планеры исчезают, следовательно на месте <tex>1</tex> образуется <tex>0</tex> и наоборот.<br>
}}
{{УтверждениеТеорема
|statement=
Проблема останова игры «Жизнь» неразрешима.
|proof = Заметим, что если существует МТ, которая по начальной конфигурации игры «Жизнь» может определить, завершается ли она, то та же МТ может определить останавливается ли любая МТ, что противоречит неразрешимости проблемы останова для МТ.
<br>
Покажем схему построения МТ в игре Жизнь.
}}
== См.также ==
