Игра «Жизнь» — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 39: Строка 39:
 
[[Файл:And.png|300px]]
 
[[Файл:And.png|300px]]
 
}}
 
}}
 
+
==Неразрешимость==
 
{{Теорема
 
{{Теорема
 
|statement=
 
|statement=
Строка 46: Строка 46:
 
[[Файл:TM.png|300px|thumb|right| МТ в игре «Жизнь»]]
 
[[Файл:TM.png|300px|thumb|right| МТ в игре «Жизнь»]]
 
[[Файл:TM_diagram.png|300px|thumb|right| Схема МТ в игре «Жизнь»]]
 
[[Файл:TM_diagram.png|300px|thumb|right| Схема МТ в игре «Жизнь»]]
Заметим, что если существует МТ, которая по начальной конфигурации игры «Жизнь» может определить, завершается ли она, то та же МТ может определить останавливается ли любая МТ, что противоречит неразрешимости проблемы останова для МТ.
+
[[Файл:Finite_state_control.png|300px|thumb|right| Схема конечного автомата в игре «Жизнь»]]
 +
Заметим, что если существует МТ, которая по начальной конфигурации игры «Жизнь» может определить, завершается ли она, то та же МТ может определить останавливается ли любая МТ, что противоречит неразрешимости проблемы останова для МТ. Следовательно, необходимо описать процесс построения МТ в игре «Жизнь».
 
<br>
 
<br>
Покажем схему построения МТ в игре Жизнь (см.рисунок):
+
МТ будет состоять из следующих элементов (см.рисунок):
 
* конечный автомат,
 
* конечный автомат,
 
* детектор сигнала,
 
* детектор сигнала,
* стек,
+
* [[Стек|стек]],
 
* контроллер стека.
 
* контроллер стека.
 
+
Мы рассмотрим только общие свойства частей МТ и конструкций, нужных для их построения, так как при построении МТ возникает большое количество технически сложных вспомогательных элементов<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.
 +
==Некоторые конструкции==
 +
<b>Пчелиная королева</b><br>
 +
[[Файл:Queen_bee.png|350px]]<br>
 +
Небольшая конструкция передвигающаяся туда-обратно, при развороте оставляет стабильную конструкцию, называемую ульем. Умирает, если при возвращении улей не исчез. Используется для построения glider gun.<br><br>
 +
<b>Buckaroo</b><br>
 +
Пчелиная королева с eater. Эта конструкция примечательная тем, что при исчезновении улья возникает "вспышка", которая может менять направление планера.<br><br>
 +
<b>Pentadecathlon</b><br>
 +
[[Файл:Pentadecathlon.png|500px]]<br>
 +
Циклическая конструкция, генерирующая небольшую конструкцию, которая может отражать планеры.
 +
<br>
 
}}
 
}}
 
== См.также ==
 
== См.также ==

Версия 13:55, 14 января 2016

Игра «Жизнь» (англ. Conway's Game of Life) — клеточный автомат, придуманный английским математиком Джоном Конвеем в 1970.

Правила

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

Булевы функции

Теорема:
В игре «Жизнь» можно построить любую булеву функцию.
Доказательство:
[math]\triangleright[/math]
Базовые конструкции
Glider gun
Glider eater

Базовые конструкции

Рассмотрим базовые конструкции необходимые для построения.

В игры «Жизнь» можно построить различные конструкции (см. рис.):

  • стабильные — не меняются с течением времени (первые два ряда),
  • циклические — принимают исходное положение каждые [math]n[/math] итераций (третий ряд),
  • планер (glider) — фигура, которая смещается на одну клетку вниз и в право каждые [math]4[/math] итерации (четвертый ряд),
  • космический корабль — фигура, которая смещается ортогонально на [math]1[/math] клетку каждые [math]4[/math] итерации,
  • glider gun — фигура, бесконечно производящая планер каждые [math]30[/math] итераций,
  • glider eater — фигура, поглощающая планеры.


Булевы функции

Так как [math]\triangledown[/math] (штрих Шеффера или NAND) является полной системой, то достаточно построить [math]NOT[/math] и [math]AND[/math], чтобы показать возможность построения любой булевой функции.

Построение NOT

Рассмотрим поток данных, состоящий из планеров. Наличие планера — [math]1[/math], отсутствие — [math]0[/math]. Добавим поток планеров, состоящий только из [math]1[/math]. При столкновении планеры исчезают, следовательно на месте [math]1[/math] образуется [math]0[/math] и наоборот.
Not.png

Построение AND

См. рисунок. Пусть [math]AND(x, y)[/math], тогда y соударяется с [math]NOT(x)[/math]. Если [math]NOT(x) = 1[/math], то на выходе ничего не попадет, если [math]NOT( x) = 0[/math], то просто пройдет [math]y[/math].

And.png
[math]\triangleleft[/math]

Неразрешимость

Теорема:
Проблема останова игры «Жизнь» неразрешима.
Доказательство:
[math]\triangleright[/math]
МТ в игре «Жизнь»
Схема МТ в игре «Жизнь»
Схема конечного автомата в игре «Жизнь»

Заметим, что если существует МТ, которая по начальной конфигурации игры «Жизнь» может определить, завершается ли она, то та же МТ может определить останавливается ли любая МТ, что противоречит неразрешимости проблемы останова для МТ. Следовательно, необходимо описать процесс построения МТ в игре «Жизнь».
МТ будет состоять из следующих элементов (см.рисунок):

  • конечный автомат,
  • детектор сигнала,
  • стек,
  • контроллер стека.

Мы рассмотрим только общие свойства частей МТ и конструкций, нужных для их построения, так как при построении МТ возникает большое количество технически сложных вспомогательных элементов[1].

Конечный автомат

Конечный автомат представляет собой двумерный массив с двумя входами: предыдущее состояние, получаемое от детектора сигнала, и считанный символ от одного из стеков — для выбора ряда и колонки.

Детектор сигнала

Детектор сигнала распознает информацию, полученную от конечного автомата, и передает ее дальше: информацию о следующем состоянии — обратно в автомат(с задержкой), где она используется для выбора адреса ряда; информацию о символе для записи — на один из стеков.

Стек

Лента МТ представлена в виде двух стеков, чтобы можно было эмулировать передвижение головки чтения записи по ленте: в каждом цикле один стек делает push символа, другой — pop. МТ не дожидается сдвига всех ячеек стека.

Контроллер стека

Контроллер стека производит конструкцию из планеров, необходимую стека для произведения push или pop.

Некоторые конструкции

Пчелиная королева
Queen bee.png
Небольшая конструкция передвигающаяся туда-обратно, при развороте оставляет стабильную конструкцию, называемую ульем. Умирает, если при возвращении улей не исчез. Используется для построения glider gun.

Buckaroo
Пчелиная королева с eater. Эта конструкция примечательная тем, что при исчезновении улья возникает "вспышка", которая может менять направление планера.

Pentadecathlon
Pentadecathlon.png
Циклическая конструкция, генерирующая небольшую конструкцию, которая может отражать планеры.


[math]\triangleleft[/math]

См.также

Примечания

Источники информации