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

Материал из Викиконспекты
Перейти к: навигация, поиск
 
(не показано 20 промежуточных версий этого же участника)
Строка 2: Строка 2:
  
 
== Правила ==
 
== Правила ==
* Действие происходит на бесконечной плоскости, разделенной на клетки
+
: '''Правило 1.''' Действие происходит на бесконечной плоскости, разделенной на клетки, которую можно иногда представить как зацикленную конечную.
* Каждая клетка может находиться в двух состояниях: быть живой или быть мёртвой
+
: '''Правило 2.''' Каждая клетка может находиться в двух состояниях: быть живой или быть мёртвой.
* У каждой клетки <tex>8</tex> соседей
+
: '''Правило 3.''' У каждой клетки <tex>8</tex> соседей.
* Если клетка жива и у нее <tex>2-3</tex> живых соседа, то она остается живой, иначе умирает
+
: '''Правило 4.''' Если клетка жива и у нее <tex>2-3</tex> живых соседа, то она остается живой, иначе умирает.
* Если клетка мертва и у нее <tex>3</tex> живых соседа, то она становится живой, иначе остается мертвой
+
: '''Правило 5.''' Если клетка мертва и у нее <tex>3</tex> живых соседа, то она становится живой, иначе остается мертвой.
* Игра прекращается, если на поле не останется ни одной живой клетки
+
: '''Правило 6.''' Игра прекращается, если на поле не останется ни одной живой клетки.
* Игра прекращается, если при очередном шаге ни одна из клеток не меняет своего состояния
+
: '''Правило 7.''' Игра прекращается, если при очередном шаге ни одна из клеток не меняет своего состояния.
* Игра прекращается, если конфигурация на очередном шаге в точности повторит себя же на одном из более ранних шагов
+
: '''Правило 8.''' Игра прекращается, если конфигурация на очередном шаге в точности повторит себя же на одном из более ранних шагов.
  
== Универсальность ==
+
== Булевы функции ==
 
{{Теорема
 
{{Теорема
|statement = Игра "Жизнь" вычисляет то же множество функций, что и МТ.
+
|statement = В игре «Жизнь» можно построить любую булеву функцию.
|proof =  
+
|proof =
Для того, чтобы доказать этот факт, докажем возможность построения всех возможных [[Машина_Тьюринга |машин Тьюринга]].
+
[[Файл:Types.png|250px|thumb|right|Базовые конструкции]]
 
+
[[Файл:Glidergun.png|200px|thumb|right| Glider gun]]
В состав МТ входит:
+
[[Файл:Eater.png|150px|thumb|right| Glider eater]]
* неограниченная в обе стороны лента, разделённая на ячейки
+
* управляющее устройство, способное находиться в одном из множества состояний.
 
<br>
 
Доказательство строится на том, что простая логика, необходимая для построения МТ, может быть построена в игре "Жизнь":
 
* детерминированный конечный автомат(с часами)
 
* ленту(с ячейками памяти)
 
* головку записи-чтения
 
 
===Базовые конструкции===
 
===Базовые конструкции===
Рассмотрим базовые конструкции необходимые для построения этих элементов МТ.
+
Рассмотрим базовые конструкции необходимые для построения.
[[Файл:Types.png|250px|thumb|right]]
 
[[Файл:Glidergun.png|200px|thumb|right| Glider gun]]
 
[[Файл:Eater.png|200px|thumb|right| Glider eater]]
 
  
В игры "Жизнь" можно построить различные конструкции (см. рис.):
+
В игры «Жизнь» можно построить различные конструкции (см. рис.):
* стабильные {{---}} не меняются с течением времени(первые два ряда)
+
* стабильные {{---}} не меняются с течением времени (первые два ряда),
* циклические {{---}} принимают исходное положение каждые <tex>n</tex> итераций (третий ряд)
+
* циклические {{---}} принимают исходное положение каждые <tex>n</tex> итераций (третий ряд),
* планер(glider) {{---}} фигура, которая смещается на одну клетку вниз и в право каждые <tex>4</tex> итерации (<tex>4</tex> ряд)
+
* планер (glider) {{---}} фигура, которая смещается на одну клетку вниз и в право каждые <tex>4</tex> итерации (четвертый ряд),
* космический корабль {{---}} фигура, которая смещается ортогонально на <tex>1</tex> клетку каждые <tex>4</tex> итерации
+
* космический корабль {{---}} фигура, которая смещается ортогонально на <tex>1</tex> клетку каждые <tex>4</tex> итерации,
* glider gun {{---}} фигура, бесконечно производящая планер каждые <tex>30</tex> итераций  
+
* glider gun {{---}} фигура, бесконечно производящая планер каждые <tex>30</tex> итераций,
* glider eater {{---}} фигура, поглощающая планеры
+
* 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.86.D0.B8.D0.B8|штрих Шеффера]] или NAND) является [[Полные системы функций. Теорема Поста о полной системе функций |полной системой]], то достаточно построить <tex>NOT</tex> и <tex>AND</tex>, чтобы показать возможность построения любой булевой функции.
Заметим, что управляющая часть МТ считывает с ленты входную строчку и завершается, записав на ленту выходную строчку. Без ограничения общности, будем рассматривать бинарные строки. Следовательно, управляющая часть МТ есть булева функция.
 
<br>
 
Каждая МТ вычисляет определенную вычислимую функцию. Так как мы можем записать управляющий автомат в виде строки, можно подать МТ и входные данные на вход другой МТ. Следовательно, достаточно построить универсальную МТ.
 
<br>
 
Если показать, что мы можем построить в игре "Жизнь" любую булеву функцию, то мы сможем построить булеву функцию УМТ.
 
Из курса дискретной математики [[Полные системы функций. Теорема Поста о полной системе функций |известно]], что <tex>NAND</tex> - полная система, т.е. с его помощью можно построить любую. Следовательно, чтобы построить любую булеву функцию, нам нужно просто построить <tex>NAND</tex>, то есть <tex>NOT</tex> и <tex>AND</tex> в игре "Жизнь".
 
<br>
 
 
 
 
===Построение NOT===
 
===Построение NOT===
[[Файл:Not.png|250px|thumb]]
 
 
Рассмотрим поток данных, состоящий из планеров. Наличие планера {{---}} <tex>1</tex>, отсутствие {{---}} <tex>0</tex>. Добавим поток планеров, состоящий только из <tex>1</tex>. При столкновении планеры исчезают, следовательно на месте <tex>1</tex> образуется <tex>0</tex> и наоборот.
 
Рассмотрим поток данных, состоящий из планеров. Наличие планера {{---}} <tex>1</tex>, отсутствие {{---}} <tex>0</tex>. Добавим поток планеров, состоящий только из <tex>1</tex>. При столкновении планеры исчезают, следовательно на месте <tex>1</tex> образуется <tex>0</tex> и наоборот.
  
 +
 +
[[Файл:Not.png|300px]]
 
===Построение AND===
 
===Построение AND===
[[Файл:And.png|250px|thumb]]
 
 
См. рисунок. Пусть <tex>AND(x, y)</tex>, тогда y соударяется с <tex>NOT(x)</tex>. Если <tex>NOT(x) = 1</tex>, то на выходе ничего не попадет, если <tex>NOT( x) = 0</tex>, то просто пройдет <tex>y</tex>.
 
См. рисунок. Пусть <tex>AND(x, y)</tex>, тогда y соударяется с <tex>NOT(x)</tex>. Если <tex>NOT(x) = 1</tex>, то на выходе ничего не попадет, если <tex>NOT( x) = 0</tex>, то просто пройдет <tex>y</tex>.
 +
[[Файл: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]]
  
 +
Циклическая конструкция, генерирующая небольшую конструкцию, которая может отражать планеры.
 
}}
 
}}
<br><br><br><br><br><br><br><br>
+
== См.также ==
== Построение ==
+
* [[Неразрешимость исчисления предикатов первого порядка]]
Подробное описание построения МТ можно найти здесь:
+
* [[Примеры неразрешимых задач: задача о выводе в полусистеме Туэ|Задача о выводе в полусистеме Туэ]]
Rendell, P. (2014) Turing machine universality of the game of life. PhD, University of the West of England. Available from: http://eprints.uwe.ac.uk/22323
+
* [[Примеры неразрешимых задач: задача о замощении|Задача о замощении]]
 +
* [[Примеры неразрешимых задач: однозначность грамматики|Однозначность грамматики]]
 +
* [[Неразрешимость задачи об эквивалентности КС-грамматик]]
 +
* [[Неразрешимость проблемы существования решения диофантова уравнения в целых числах]]
 +
== Примечания ==
 +
<references/>
 +
== Источники информации ==
 +
* [https://ru.wikipedia.org/wiki/%D0%96%D0%B8%D0%B7%D0%BD%D1%8C_(%D0%B8%D0%B3%D1%80%D0%B0) Википедия {{---}} Жизнь (игра)]
 +
* [http://academic.regis.edu/dbahr/generalpages/CellularAutomata/CA_part14_files/frame.htm Proving Life is Universal]
 +
 
 +
[[Категория: Теория формальных языков]]
 +
[[Категория: Теория вычислимости]]
 +
[[Категория: Примеры неразрешимых задач]]

Текущая версия на 14:30, 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]

См.также[править]

Примечания[править]

Источники информации[править]