102
правки
Изменения
Нет описания правки
== Правила ==
== Универсальность ==
Если показать, что мы можем построить в игре "Жизнь" любую булеву функцию, то мы сможем построить булеву функцию УМТ.
Из курса дискретной математики [[Полные системы функций. Теорема Поста о полной системе функций |известно]], что <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>