102
правки
Изменения
Нет описания правки
===Базовые конструкции===
Рассмотрим базовые конструкции необходимые для построения.
В игры «Жизнь» можно построить различные конструкции (см. рис.):
* стабильные {{---}} не меняются с течением времени (первые два ряда),
* glider gun {{---}} фигура, бесконечно производящая планер каждые <tex>30</tex> итераций,
* glider eater {{---}} фигура, поглощающая планеры.
===Булевы функции===
Так как <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>
[[Файл:Not.png|300px]]
===Построение AND===
См. рисунок. Пусть <tex>AND(x, y)</tex>, тогда y соударяется с <tex>NOT(x)</tex>. Если <tex>NOT(x) = 1</tex>, то на выходе ничего не попадет, если <tex>NOT( x) = 0</tex>, то просто пройдет <tex>y</tex>.<br>
[[Файл:And.png|300px]]
}}
[[Файл:Finite_state_control.png|300px|thumb|right| Схема конечного автомата в игре «Жизнь»]]
Заметим, что если существует МТ, которая по начальной конфигурации игры «Жизнь» может определить, завершается ли она, то та же МТ может определить останавливается ли любая МТ, что противоречит неразрешимости проблемы останова для МТ. Следовательно, необходимо описать процесс построения МТ в игре «Жизнь».
МТ будет состоять из следующих элементов (см.рисунок):
* [[Детерминированные_конечные_автоматы |детерминированный конечный автомат]],
* детектор сигнала,
* [[Стек|стек]],
=== Контроллер стека ===
Контроллер стека производит конструкцию из планеров, необходимую стекам для произведения push или pop, осуществляет перемещение символов.
===Некоторые конструкции===<b>Ниже приведены некоторые конструкций игры, с помощью которых построены вышеупомянутые элементы. ====Пчелиная королева</b><br>====[[Файл:Queen_bee.png|350px]]<br> Небольшая конструкция передвигающаяся туда-обратно, при развороте оставляет стабильную конструкцию, называемую ульем. Умирает, если при возвращении улей не исчез. Используется для построения glider gun.<br><br><b>====Buckaroo</b><br>====Пчелиная королева с eater. Эта конструкция примечательная тем, что при исчезновении улья возникает "вспышка", которая может менять направление планера.<br><br><b>====Pentadecathlon</b><br>====[[Файл:Pentadecathlon.png|500px]]<br>
Циклическая конструкция, генерирующая небольшую конструкцию, которая может отражать планеры.
}}
== См.также ==
