102
правки
Изменения
Нет описания правки
* Действие происходит на бесконечной плоскости, разделенной на клетки
* Каждая клетка может находиться в двух состояниях: быть живой или быть мёртвой
* У каждой клетки <tex>8 </tex> соседей* Если клетка жива и у нее <tex>2-3 </tex> живых соседа, то она остается живой, иначе умирает* Если клетка мертва и у нее <tex>3 </tex> живых соседа, то она становится живой, иначе остается мертвой
* Игра прекращается, если на поле не останется ни одной живой клетки
* Игра прекращается, если при очередном шаге ни одна из клеток не меняет своего состояния
Рассмотрим базовые конструкции необходимые для построения этих элементов МТ.
[[Файл:Types.png|250px|thumb|right]]
[[Файл:Glidergun.png|100px200px|thumb|leftright| Glider gun]][[Файл:Eater.png|100px200px|thumb|leftright| Glider eater]]
В игры "Жизнь" можно построить различные конструкции(см. рис.):* стабильные {{- --}} не меняются с течением времени(первые два ряда - рисунок)* циклические {{- --}} принимают исходное положение каждые <tex>n </tex> итераций (третий ряд - рисунок)* планер(glider) {{- --}} фигура, которая смещается на одну клетку вниз и в право каждые <tex>4 </tex> итерации(<tex>4 </tex> ряд - рисунок)* космический корабль {{--- }} фигура, которая смещается ортогонально на <tex>1 </tex> клетку каждые <tex>4 </tex> итерации* glider gun {{--- }} фигура, бесконечно производящая планер каждые <tex>30 </tex> итераций * glider eater {{--- }} фигура, поглощающая планеры
<br><br><br>
<br><br>
===Память===
Ячейки памяти можно построить с помощью стабильныx конструкций. [[Файл:Memory.png|150px]]<br>
Можно также построить c помощью планеров: наличие планера {{- --}} <tex>1</tex>, отсутствие {{--- }} <tex>0</tex>. [[Файл:Datatransmission.png|150px]]
<br>
===Часы===
<br>
Если показать, что мы можем построить в игре "Жизнь" любую булеву функцию, то мы сможем построить булеву функцию УМТ.
Из курса дискретной математики [[Полные системы функций. Теорема Поста о полной системе функций |известно]], что <tex>NAND </tex> - полная система, т.е. с его помощью можно построить любую. Следовательно, чтобы построить любую булеву функцию, нам нужно просто построить <tex>NAND</tex>, то есть <tex>NOT </tex> и <tex>AND </tex> в игре "Жизнь".
<br>
===Построение NOT===
[[Файл:Not.png|250px|thumb|right]]Рассмотрим поток данных, состоящий из планеров. Наличие планера {{- --}} <tex>1</tex>, отсутствие {{-- -}} <tex>0</tex>. Добавим поток планеров, состоящий только из <tex>1</tex>. При столкновении планеры исчезают, следовательно на месте 1 образуется 0 и наоборот.<brtex>1<br/tex>образуется <brtex>0<br><br><br><br><br><br><br><br><br/tex>и наоборот.
===Построение AND===
[[Файл:And.png|250px|thumb|right]]См. рисунок. Пусть <tex>AND(x AND , y)</tex>, тогда y соударяется с <tex>NOT(x)</tex>. Если <tex>NOT (x ) = 1</tex>, то на выходе ничего не попадет, если <tex>NOT ( x ) = 0</tex>, то просто пройдет <tex>y</tex>.
}}
