Изменения

Перейти к: навигация, поиск

Игра «Жизнь»

300 байт добавлено, 13:37, 13 января 2016
Нет описания правки
== Правила ==
* : '''Правило 1.''' Действие происходит на бесконечной плоскости, разделенной на клетки, которую можно иногда представить как зацикленную конечную* : '''Правило 2.''' Каждая клетка может находиться в двух состояниях: быть живой или быть мёртвой* : '''Правило 3.''' У каждой клетки <tex>8</tex> соседей* : '''Правило 4.''' Если клетка жива и у нее <tex>2-3</tex> живых соседа, то она остается живой, иначе умирает* : '''Правило 5.''' Если клетка мертва и у нее <tex>3</tex> живых соседа, то она становится живой, иначе остается мертвой* : '''Правило 6.''' Игра прекращается, если на поле не останется ни одной живой клетки* : '''Правило 7.''' Игра прекращается, если при очередном шаге ни одна из клеток не меняет своего состояния* : '''Правило 8.''' Игра прекращается, если конфигурация на очередном шаге в точности повторит себя же на одном из более ранних шагов
== Универсальность ==
Если показать, что мы можем построить в игре "Жизнь" любую булеву функцию, то мы сможем построить булеву функцию УМТ.
Из курса дискретной математики [[Полные системы функций. Теорема Поста о полной системе функций |известно]], что <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>
102
правки

Навигация