102
правки
Изменения
м
Нет описания правки
* стабильные {{---}} не меняются с течением времени(первые два ряда),
* циклические {{---}} принимают исходное положение каждые <tex>n</tex> итераций (третий ряд),
* планер(glider) {{---}} фигура, которая смещается на одну клетку вниз и в право каждые <tex>4</tex> итерации (<tex>4</tex> ряд),
* космический корабль {{---}} фигура, которая смещается ортогонально на <tex>1</tex> клетку каждые <tex>4</tex> итерации,
* glider gun {{---}} фигура, бесконечно производящая планер каждые <tex>30</tex> итераций,
<br>
Если показать, что мы можем построить в игре "Жизнь" любую булеву функцию, то мы сможем построить булеву функцию УМТ.
Из курса дискретной математики [[Полные системы функций. Теорема Поста о полной системе функций |известно]], что <tex>NAND</tex> {{- --}} полная система, т.е. с его помощью можно построить любую. Следовательно, чтобы построить любую булеву функцию, нам нужно просто построить <tex>NAND</tex>, то есть <tex>NOT</tex> и <tex>AND</tex> в игре "Жизнь".
===Построение NOT===
Рассмотрим поток данных, состоящий из планеров. Наличие планера {{---}} <tex>1</tex>, отсутствие {{---}} <tex>0</tex>. Добавим поток планеров, состоящий только из <tex>1</tex>. При столкновении планеры исчезают, следовательно на месте <tex>1</tex> образуется <tex>0</tex> и наоборот.<br>
