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

Материал из Викиконспекты
Перейти к: навигация, поиск
м
Строка 15: Строка 15:
 
|statement = Игра «Жизнь» вычисляет то же множество функций, что и МТ.
 
|statement = Игра «Жизнь» вычисляет то же множество функций, что и МТ.
 
|proof =
 
|proof =
[[Файл:Types.png|250px|right]]
+
[[Файл:Types.png|250px|thumb|right|Базовые конструкции]]
 
[[Файл:Glidergun.png|200px|thumb|right| Glider gun]]
 
[[Файл:Glidergun.png|200px|thumb|right| Glider gun]]
 
[[Файл:Eater.png|150px|thumb|right| Glider eater]]
 
[[Файл:Eater.png|150px|thumb|right| Glider eater]]
Строка 25: Строка 25:
 
* управляющее устройство, способное находиться в одном из множества состояний.   
 
* управляющее устройство, способное находиться в одном из множества состояний.   
 
<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>.
 
<br>
 
<br>
 
===Базовые конструкции===
 
===Базовые конструкции===
 
Рассмотрим базовые конструкции необходимые для построения этих элементов МТ.
 
Рассмотрим базовые конструкции необходимые для построения этих элементов МТ.
 
<br><br>
 
<br><br>
В игры "Жизнь" можно построить различные конструкции (см. рис.):
+
В игры «Жизнь» можно построить различные конструкции (см. рис.):
* стабильные {{---}} не меняются с течением времени(первые два ряда),
+
* стабильные {{---}} не меняются с течением времени (первые два ряда),
 
* циклические {{---}} принимают исходное положение каждые <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> итераций,
Строка 53: Строка 53:
 
Каждая МТ вычисляет определенную вычислимую функцию. Так как мы можем записать управляющий автомат в виде строки, можно подать МТ и входные данные на вход другой МТ. Следовательно, достаточно построить универсальную МТ.
 
Каждая МТ вычисляет определенную вычислимую функцию. Так как мы можем записать управляющий автомат в виде строки, можно подать МТ и входные данные на вход другой МТ. Следовательно, достаточно построить универсальную МТ.
 
<br>
 
<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>.
 
Так как <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>.
Строка 63: Строка 63:
 
[[Файл:And.png|300px]]
 
[[Файл:And.png|300px]]
 
}}
 
}}
== Следствие ==
+
 
{{Теорема
+
{{Утверждение
|about=
 
Следствие
 
 
|statement=
 
|statement=
 
Проблема останова игры «Жизнь» неразрешима.
 
Проблема останова игры «Жизнь» неразрешима.
Строка 79: Строка 77:
 
* [[Неразрешимость проблемы существования решения диофантова уравнения в целых числах]]
 
* [[Неразрешимость проблемы существования решения диофантова уравнения в целых числах]]
 
== Примечания ==
 
== Примечания ==
[http://eprints.uwe.ac.uk/22323 Rendell, P. (2014) Turing machine universality of the game of life. PhD, University of the West of England.]
+
<references/>
 
== Источники информации ==
 
== Источники информации ==
 
* [https://ru.wikipedia.org/wiki/%D0%96%D0%B8%D0%B7%D0%BD%D1%8C_(%D0%B8%D0%B3%D1%80%D0%B0) Википедия {{---}} Жизнь (игра)]
 
* [https://ru.wikipedia.org/wiki/%D0%96%D0%B8%D0%B7%D0%BD%D1%8C_(%D0%B8%D0%B3%D1%80%D0%B0) Википедия {{---}} Жизнь (игра)]

Версия 17:25, 13 января 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

Для того, чтобы доказать этот факт, докажем возможность построения всех возможных машин Тьюринга.
В состав МТ входит:

  • неограниченная в обе стороны лента, разделённая на ячейки,
  • управляющее устройство, способное находиться в одном из множества состояний.


Доказательство строится на том, что простая логика, необходимая для построения МТ, может быть построена в игре «Жизнь»[1].

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

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

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

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






Память

Стабильная ячейка
Передача данных

Ячейки памяти можно построить с помощью стабильныx конструкций, т.е. мы можем построить ленту МТ.
Передачу данных можно осуществлять c помощью планеров: наличие планера — [math]1[/math], отсутствие — [math]0[/math].

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

Заметим, что управляющая часть МТ считывает с ленты входную строчку и завершается, записав на ленту выходную строчку. Без ограничения общности, будем рассматривать бинарные строки. Следовательно, управляющая часть МТ есть функция вида [math]f:\{0, 1\}^n \rightarrow \{0, 1\}^m [/math]. Заметим, что можно построить функции такого вида из булевых функций [math]f_i:\{0, 1\}^n \rightarrow \{0, 1\}[/math]: [math]f(x_1, x_2, x_3 ... x_n) = f(f_1(x_1, x_2, x_3 ... x_n), f_2(x_1, x_2, x_3 ... x_n), ... f_m(x_1, x_2, x_3 ... x_n) [/math].

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

Так как [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]
Заметим, что если существует МТ, которая по начальной конфигурации игры «Жизнь» может определить, завершается ли она, то та же МТ может определить останавливается ли любая МТ, что противоречит неразрешимости проблемы останова для МТ.
[math]\triangleleft[/math]

См.также

Примечания

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