Изменения

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

Игра «Жизнь»

2315 байт добавлено, 14:30, 14 января 2016
Нет описания правки
: '''Правило 8.''' Игра прекращается, если конфигурация на очередном шаге в точности повторит себя же на одном из более ранних шагов.
== Универсальность Булевы функции ==
{{Теорема
|statement = Игра В игре «Жизнь» вычисляет то же множество функций, что и МТможно построить любую булеву функцию.
|proof =
[[Файл:Types.png|250px|thumb|right|Базовые конструкции]]
[[Файл:Glidergun.png|200px|thumb|right| Glider gun]]
[[Файл:Eater.png|150px|thumb|right| Glider eater]]
Для того, чтобы доказать этот факт, докажем возможность построения всех возможных [[Машина_Тьюринга |машин Тьюринга]].
<br>
В состав МТ входит:
* неограниченная в обе стороны лента, разделённая на ячейки,
* управляющее устройство, способное находиться в одном из множества состояний.
<br>
Доказательство строится на том, что простая логика, необходимая для построения МТ, может быть построена в игре "Жизнь":
* [[Детерминированные_конечные_автоматы|детерминированный конечный автомат]],
* ленту(с ячейками памяти),
* головку записи-чтения.
<br>
===Базовые конструкции===
Рассмотрим базовые конструкции необходимые для построения этих элементов МТ.<br><br>В игры "Жизнь" «Жизнь» можно построить различные конструкции (см. рис.):* стабильные {{---}} не меняются с течением времени(первые два ряда),
* циклические {{---}} принимают исходное положение каждые <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>
===Память===
[[Файл:Memory.png|200px|thumb|right|Стабильная ячейка]]
[[Файл:Datatransmission.png|150px|thumb|right|Передача данных]]
Ячейки памяти можно построить с помощью стабильныx конструкций<br>
Можно также построить c помощью планеров: наличие планера {{---}} <tex>1</tex>, отсутствие {{---}} <tex>0</tex>.<br>
===Булевы функции===
ЗаметимТак как <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.86.D0.B8.D0.B8|штрих Шеффера]] или NAND) является [[Полные системы функций. Теорема Поста о полной системе функций |полной системой]], что управляющая часть МТ считывает с ленты входную строчку то достаточно построить <tex>NOT</tex> и завершается<tex>AND</tex>, записав на ленту выходную строчкучтобы показать возможность построения любой булевой функции. Без ограничения общности===Построение NOT===Рассмотрим поток данных, будем рассматривать бинарные строкисостоящий из планеров. СледовательноНаличие планера {{---}} <tex>1</tex>, управляющая часть МТ есть булева функцияотсутствие {{---}} <tex>0</tex>.Добавим поток планеров, состоящий только из <tex>1<br/tex>Каждая МТ вычисляет определенную вычислимую функцию. Так как мы можем записать управляющий автомат в виде строкиПри столкновении планеры исчезают, можно подать МТ и входные данные следовательно на вход другой МТ. Следовательно, достаточно построить универсальную МТ.месте <tex>1</tex> образуется <tex>0<br/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>
[[Файл:Not.png|300px]]
===Построение AND===
См. рисунок. Пусть <tex>AND(x, y)</tex>, тогда y соударяется с <tex>NOT(x)</tex>. Если <tex>NOT(x) = 1</tex>, то на выходе ничего не попадет, если <tex>NOT( x) = 0</tex>, то просто пройдет <tex>y</tex>.<br>
[[Файл:And.png|300px]]
}}
==Неразрешимость==
{{Теорема
|statement=
Проблема останова игры «Жизнь» неразрешима.
|proof =
[[Файл:TM.png|300px|thumb|right| МТ в игре «Жизнь»]]
[[Файл:TM_diagram.png|300px|thumb|right| Схема МТ в игре «Жизнь»]]
[[Файл:Finite_state_control.png|300px|thumb|right| Схема конечного автомата в игре «Жизнь»]]
Заметим, что если существует МТ, которая по начальной конфигурации игры «Жизнь» может определить, завершается ли она, то та же МТ может определить останавливается ли любая МТ, что противоречит неразрешимости проблемы останова для МТ. Следовательно, необходимо описать процесс построения МТ в игре «Жизнь».
 
МТ будет состоять из следующих элементов (см.рисунок):
* [[Детерминированные_конечные_автоматы |детерминированный конечный автомат]],
* детектор сигнала,
* [[Стек|стек]],
* контроллер стека.
Мы рассмотрим только общие свойства частей МТ и конструкций, нужных для их построения, так как при построении МТ возникает большое количество технически сложных вспомогательных элементов<ref>[http://eprints.uwe.ac.uk/22323 Rendell, P. (2014) Turing machine universality of the game of life. PhD, University of the West of England]</ref>.
=== Конечный автомат ===
Конечный автомат представляет собой двумерный массив с двумя входами: предыдущее состояние, получаемое от детектора сигнала, и считанный символ от одного из стеков {{---}} для выбора ряда и колонки ячейки, в которой лежит информация о переходе.
=== Детектор сигнала ===
Детектор сигнала распознает информацию, полученную от конечного автомата, и передает ее дальше: информацию о следующем состоянии {{---}} обратно в автомат (с задержкой), где она используется для выбора адреса ряда; информацию о символе для записи {{---}} на один из стеков.
=== Стек ===
Лента МТ представлена в виде двух стеков, которые могут эмулировать передвижение головки чтения записи по ленте: в каждом цикле один стек делает push символа, другой {{---}} pop.
=== Контроллер стека ===
Контроллер стека производит конструкцию из планеров, необходимую стекам для произведения push или pop, осуществляет перемещение символов.
===Некоторые конструкции===
Ниже приведены некоторые конструкций игры, с помощью которых построены вышеупомянутые элементы.
 
====Пчелиная королева====
[[Файл:Queen_bee.png|350px]]
 
Небольшая конструкция передвигающаяся туда-обратно, при развороте оставляет стабильную конструкцию, называемую ульем. Умирает, если при возвращении улей не исчез. Используется для построения glider gun.
 
====Buckaroo====
Пчелиная королева с eater. Эта конструкция примечательная тем, что при исчезновении улья возникает "вспышка", которая может менять направление планера.
 
====Pentadecathlon====
[[Файл:Pentadecathlon.png|500px]]
 
Циклическая конструкция, генерирующая небольшую конструкцию, которая может отражать планеры.
}}
== См.также ==
* [[Неразрешимость проблемы существования решения диофантова уравнения в целых числах]]
== Примечания ==
* Rendell, P. (2014) Turing machine universality of the game of life. PhD, University of the West of England. Available from: http:<references//eprints.uwe.ac.uk/22323>
== Источники информации ==
* [https://ru.wikipedia.org/wiki/%D0%96%D0%B8%D0%B7%D0%BD%D1%8C_(%D0%B8%D0%B3%D1%80%D0%B0) Википедия {{---}} Жизнь (игра)]
102
правки

Навигация