Изменения

* : '''Правило 1.''' Действие происходит на бесконечной плоскости, разделенной на клетки, которую можно иногда представить как зацикленную конечную.* : '''Правило 2.''' Каждая клетка может находиться в двух состояниях: быть живой или быть мёртвой.* : '''Правило 3.''' У каждой клетки <tex>8</tex> соседей.* : '''Правило 4.''' Если клетка жива и у нее <tex>2-3</tex> живых соседа, то она остается живой, иначе умирает.* : '''Правило 5.''' Если клетка мертва и у нее <tex>3</tex> живых соседа, то она становится живой, иначе остается мертвой.* : '''Правило 6.''' Игра прекращается, если на поле не останется ни одной живой клетки.* : '''Правило 7.''' Игра прекращается, если при очередном шаге ни одна из клеток не меняет своего состояния.* : '''Правило 8.''' Игра прекращается, если конфигурация на очередном шаге в точности повторит себя же на одном из более ранних шагов.

== Универсальность Булевы функции ==

|statement = Игра "Жизнь" вычисляет то же множество функций, что и МТВ игре «Жизнь» можно построить любую булеву функцию.|proof = Для того, чтобы доказать этот факт, докажем возможность построения всех возможных [[Машина_Тьюринга Файл:Types.png|машин Тьюринга250px|thumb|right|Базовые конструкции]]. В состав МТ входит[[Файл:* неограниченная в обе стороны лента, разделённая на ячейки* управляющее устройство, способное находиться в одном из множества состоянийGlidergun. png|200px|thumb|right| Glider gun]]<br>Доказательство строится на том, что простая логика, необходимая для построения МТ, может быть построена в игре "Жизнь"[[Файл:Eater.png|150px|thumb|right| Glider eater]]* детерминированный конечный автомат(с часами)* ленту(с ячейками памяти)* головку записи-чтения

Рассмотрим базовые конструкции необходимые для построения этих элементов МТ.[[Файл:Types.png|250px|thumb|right]][[Файл:Glidergun.png|200px|thumb|right| Glider gun]][[Файл:Eater.png|200px|thumb|right| 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>===Часы=== В клеточных автоматах изначально есть часы, так как время увеличивается. Но в МТ необходимо, например, через определенное время передвигать головку записи, передавать информацию и пр. Для этой цели можно использовать планеры или космические корабли, так как они двигаются с известной скоростью. Следовательно, в качестве часов используем glider gun.

 Заметим, что управляющая часть МТ считывает с ленты входную строчку и завершается, записав на ленту выходную строчкуТак как <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.<br>Каждая МТ вычисляет определенную вычислимую функцию86. Так как мы можем записать управляющий автомат в виде строки, можно подать МТ и входные данные на вход другой МТD0. Следовательно, достаточно построить универсальную МТB8.<br>Если показать, что мы можем построить в игре "Жизнь" любую булеву функцию, то мы сможем построить булеву функцию УМТD0.Из курса дискретной математики B8|штрих Шеффера]] или NAND) является [[Полные системы функций. Теорема Поста о полной системе функций |известнополной системой]], что <tex>NAND</tex> - полная система, т.е. с его помощью можно построить любую. Следовательно, чтобы построить любую булеву функцию, нам нужно просто то достаточно построить <tex>NAND</tex>, то есть <tex>NOT</tex> и <tex>AND</tex> в игре "Жизнь", чтобы показать возможность построения любой булевой функции.<br> 

== См.также ==* [[Неразрешимость исчисления предикатов первого порядка]]* [[Примеры неразрешимых задач: задача о выводе в полусистеме Туэ|Задача о выводе в полусистеме Туэ]]* [[Примеры неразрешимых задач: задача о замощении|Задача о замощении]]* [[Примеры неразрешимых задач: однозначность грамматики|Однозначность грамматики]]* [[Неразрешимость задачи об эквивалентности КС-грамматик]]* [[Неразрешимость проблемы существования решения диофантова уравнения в целых числах]]== Примечания ==<br><br><br><br><br><br><br><brreferences/>== Построение Источники информации ==Подробное описание построения МТ можно найти здесь* [https:Rendell, P//ru.wikipedia. org/wiki/%D0%96%D0%B8%D0%B7%D0%BD%D1%8C_(2014%D0%B8%D0%B3%D1%80%D0%B0) Turing machine universality of the game of life. PhD, University of the West of England. Available from: Википедия {{---}} Жизнь (игра)]* [http://eprintsacademic.uweregis.acedu/dbahr/generalpages/CellularAutomata/CA_part14_files/frame.uk/22323htm Proving Life is Universal] [[Категория: Теория формальных языков]][[Категория: Теория вычислимости]][[Категория: Примеры неразрешимых задач]]