Изменения

== Универсальность Булевы функции ==

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

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

Заметим, что управляющая часть МТ считывает с ленты входную строчку и завершается, записав на ленту выходную строчку. Без ограничения общности, будем рассматривать бинарные строки. Следовательно, управляющая часть МТ есть функция вида Так как <tex>f:\{0, 1\}^n \rightarrow \{0, 1\}^m 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>f_i:\{0, 1\}^n \rightarrow \{0, 1\}NOT</tex>:и <tex>AND</tex>f(x_1, x_2, x_3 чтобы показать возможность построения любой булевой функции... x_n) ===Построение NOT=== f(f_1(x_1Рассмотрим поток данных, x_2, x_3 состоящий из планеров... x_n)Наличие планера {{---}} <tex>1</tex>, f_2(x_1, x_2, x_3 отсутствие {{---}} <tex>0</tex>... x_n)Добавим поток планеров, состоящий только из <tex>1</tex>... f_m(x_1При столкновении планеры исчезают, x_2, x_3 ... x_n) следовательно на месте <tex>1</tex>.образуется <brtex>0<br/tex>Каждая МТ вычисляет определенную вычислимую функцию. Так как мы можем записать управляющий автомат в виде строки, можно подать МТ и входные данные на вход другой МТнаоборот. Следовательно, достаточно построить универсальную МТ.<br>Если показать, что мы можем построить в игре «Жизнь» любую булеву функцию, то мы сможем построить булеву функцию УМТ.

См. рисунок. Пусть <tex>AND(x, y)</tex>, тогда y соударяется с <tex>NOT(x)</tex>. Если <tex>NOT(x) = 1</tex>, то на выходе ничего не попадет, если <tex>NOT( x) = 0</tex>, то просто пройдет <tex>y</tex>.<br>

==Неразрешимость=={{УтверждениеТеорема

|proof = [[Файл:TM.png|300px|thumb|right| МТ в игре «Жизнь»]][[Файл:TM_diagram.png|300px|thumb|right| Схема МТ в игре «Жизнь»]][[Файл:Finite_state_control.png|300px|thumb|right| Схема конечного автомата в игре «Жизнь»]]Заметим, что если существует МТ, которая по начальной конфигурации игры «Жизнь» может определить, завершается ли она, то та же МТ может определить останавливается ли любая МТ, что противоречит неразрешимости проблемы останова для МТ. Следовательно, необходимо описать процесс построения МТ в игре «Жизнь». МТ будет состоять из следующих элементов (см.рисунок):* [[Детерминированные_конечные_автоматы |детерминированный конечный автомат]],* детектор сигнала,* [[Стек|стек]],* контроллер стека.Мы рассмотрим только общие свойства частей МТ и конструкций, нужных для их построения, так как при построении МТ возникает большое количество технически сложных вспомогательных элементов<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>.=== Конечный автомат ===Конечный автомат представляет собой двумерный массив с двумя входами: предыдущее состояние, получаемое от детектора сигнала, и считанный символ от одного из стеков {{---}} для выбора ряда и колонки ячейки, в которой лежит информация о переходе.=== Детектор сигнала ===Детектор сигнала распознает информацию, полученную от конечного автомата, и передает ее дальше: информацию о следующем состоянии {{---}} обратно в автомат (с задержкой), где она используется для выбора адреса ряда; информацию о символе для записи {{---}} на один из стеков.=== Стек ===Лента МТ представлена в виде двух стеков, которые могут эмулировать передвижение головки чтения записи по ленте: в каждом цикле один стек делает push символа, другой {{---}} pop.=== Контроллер стека ===Контроллер стека производит конструкцию из планеров, необходимую стекам для произведения push или pop, осуществляет перемещение символов.===Некоторые конструкции===Ниже приведены некоторые конструкций игры, с помощью которых построены вышеупомянутые элементы. ====Пчелиная королева====[[Файл:Queen_bee.png|350px]] Небольшая конструкция передвигающаяся туда-обратно, при развороте оставляет стабильную конструкцию, называемую ульем. Умирает, если при возвращении улей не исчез. Используется для построения glider gun. ====Buckaroo====Пчелиная королева с eater. Эта конструкция примечательная тем, что при исчезновении улья возникает "вспышка", которая может менять направление планера. ====Pentadecathlon====[[Файл:Pentadecathlon.png|500px]] Циклическая конструкция, генерирующая небольшую конструкцию, которая может отражать планеры.