102
правки
Изменения
Новая страница: «{{Определение |id=def1 |definition='''Игра "Жизнь"''' (англ. ''Conway's Game of Life'') — клеточный автомат, приду...»
{{Определение
|id=def1
|definition='''Игра "Жизнь"''' (англ. ''Conway's Game of Life'') — клеточный автомат, придуманный английским математиком Джоном Конвеем в 1970 году.
}}
== Правила ==
* Действие происходит на бесконечной плоскости, разделенной на клетки
* Каждая клетка может находиться в двух состояниях: быть живой или быть мёртвой
* У каждой клетки 8 соседей
* Если клетка жива и у нее 2-3 живых соседа, то она остается живой, иначе умирает
* Если клетка мертва и у нее 3 живых соседа, то она становится живой, иначе остается мертвой
* Игра прекращается, если на поле не останется ни одной живой клетки
* Игра прекращается, если при очередном шаге ни одна из клеток не меняет своего состояния
* Игра прекращается, если конфигурация на очередном шаге в точности повторит себя же на одном из более ранних шагов
== Универсальность ==
{{Теорема
|statement = Игра "Жизнь" универсальна.
|proof =
Для того, чтобы доказать этот факт, докажем возможность построения всех возможных Машин Тьюринга.
В состав машины Тьюринга входит:
* неограниченная в обе стороны лента, разделённая на ячейки
* управляющее устройство, способное находиться в одном из множества состояний.
<br>
Доказательство строится на том, что простая логика, необходимая для построения МТ, может быть построена в игре "Жизнь":
* детерминированный конечный автомат(с часами)
* ленту(с ячейками памяти)
* головку записи-чтения
===Базовые конструкции===
Рассмотрим базовые конструкции необходимые для построения этих элементов МТ.
[[Файл:Types.png|250px|thumb|right]]
[[Файл:Glidergun.png|100px|thumb|left| Glider gun]]
[[Файл:Eater.png|100px|thumb|left| Glider eater]]
В игры "Жизнь" можно построить различные конструкции:
* стабильные - не меняются с течением времени(первые два ряда - рисунок)
* циклические - принимают исходное положение каждые n итераций (третий ряд - рисунок)
* планер(glider) - фигура, которая смещается на одну клетку вниз и в право каждые 4 итерации(4 ряд - рисунок)
* космический корабль - фигура, которая смещается ортогонально на 1 клетку каждые 4 итерации
* glider gun - фигура, бесконечно производящая планер каждые 30 итераций
* glider eater - фигура, поглощающая планеры
<br><br><br>
<br><br>
===Память===
Ячейки памяти можно построить с помощью стабильныx конструкций. [[Файл:Memory.png|150px]]<br>
Можно также построить c помощью планеров: наличие планера - 1, отсутствие - 0. [[Файл:Datatransmission.png|150px]]
<br>
===Часы===
В клеточных автоматах изначально есть часы, так как время увеличивается. Но в МТ необходимо, например, через определенное время передвигать головку записи, передавать информацию и пр. Для этой цели можно использовать планеры или космические корабли, так как они двигаются с известной скоростью. Следовательно, в качестве часов используем glider gun.
===Булевы функции===
Заметим, что управляющая часть МТ считывает с ленты входную строчку и завершается, записав на ленту выходную строчку. Без ограничения общности, будем рассматривать бинарные строки. Следовательно, управляющая часть МТ есть булева функция.
<br>
Каждая Машина Тьюринга вычисляет определенную вычислимую функцию. Так как мы можем записать управляющий автомат в виде строки, можно подать Машину Тьюринга и входные данные на вход другой Машине Тьюринга. Следовательно, достаточно построить универсальную МТ.
<br>
Если показать, что мы можем построить в игре "Жизнь" любую булеву функцию, то мы сможем построить булеву функцию УМТ.
Из курса дискретной математики [[Полные системы функций. Теорема Поста о полной системе функций |известно]], что NAND - полная система, т.е. с его помощью можно построить любую. Следовательно, чтобы построить любую булеву функцию, нам нужно просто построить NAND, то есть NOT и AND в игре "Жизнь".
<br>
===Построение NOT===
[[Файл:Not.png|250px|thumb|right]]
Рассмотрим поток данных, состоящий из планеров. Наличие планера - 1, отсутствие - 0. Добавим поток планеров, состоящий только из 1. При столкновении планеры исчезают, следовательно на месте 1 образуется 0 и наоборот.
<br><br><br><br><br><br><br><br><br><br><br><br>
===Построение AND===
[[Файл:And.png|250px|thumb|right]]
См. рисунок. Пусть x AND y, тогда y соударяется с NOT(x). Если NOT x = 1, то на выходе ничего не попадет, если NOT x = 0, то просто пройдет y.
}}
<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
|id=def1
|definition='''Игра "Жизнь"''' (англ. ''Conway's Game of Life'') — клеточный автомат, придуманный английским математиком Джоном Конвеем в 1970 году.
}}
== Правила ==
* Действие происходит на бесконечной плоскости, разделенной на клетки
* Каждая клетка может находиться в двух состояниях: быть живой или быть мёртвой
* У каждой клетки 8 соседей
* Если клетка жива и у нее 2-3 живых соседа, то она остается живой, иначе умирает
* Если клетка мертва и у нее 3 живых соседа, то она становится живой, иначе остается мертвой
* Игра прекращается, если на поле не останется ни одной живой клетки
* Игра прекращается, если при очередном шаге ни одна из клеток не меняет своего состояния
* Игра прекращается, если конфигурация на очередном шаге в точности повторит себя же на одном из более ранних шагов
== Универсальность ==
{{Теорема
|statement = Игра "Жизнь" универсальна.
|proof =
Для того, чтобы доказать этот факт, докажем возможность построения всех возможных Машин Тьюринга.
В состав машины Тьюринга входит:
* неограниченная в обе стороны лента, разделённая на ячейки
* управляющее устройство, способное находиться в одном из множества состояний.
<br>
Доказательство строится на том, что простая логика, необходимая для построения МТ, может быть построена в игре "Жизнь":
* детерминированный конечный автомат(с часами)
* ленту(с ячейками памяти)
* головку записи-чтения
===Базовые конструкции===
Рассмотрим базовые конструкции необходимые для построения этих элементов МТ.
[[Файл:Types.png|250px|thumb|right]]
[[Файл:Glidergun.png|100px|thumb|left| Glider gun]]
[[Файл:Eater.png|100px|thumb|left| Glider eater]]
В игры "Жизнь" можно построить различные конструкции:
* стабильные - не меняются с течением времени(первые два ряда - рисунок)
* циклические - принимают исходное положение каждые n итераций (третий ряд - рисунок)
* планер(glider) - фигура, которая смещается на одну клетку вниз и в право каждые 4 итерации(4 ряд - рисунок)
* космический корабль - фигура, которая смещается ортогонально на 1 клетку каждые 4 итерации
* glider gun - фигура, бесконечно производящая планер каждые 30 итераций
* glider eater - фигура, поглощающая планеры
<br><br><br>
<br><br>
===Память===
Ячейки памяти можно построить с помощью стабильныx конструкций. [[Файл:Memory.png|150px]]<br>
Можно также построить c помощью планеров: наличие планера - 1, отсутствие - 0. [[Файл:Datatransmission.png|150px]]
<br>
===Часы===
В клеточных автоматах изначально есть часы, так как время увеличивается. Но в МТ необходимо, например, через определенное время передвигать головку записи, передавать информацию и пр. Для этой цели можно использовать планеры или космические корабли, так как они двигаются с известной скоростью. Следовательно, в качестве часов используем glider gun.
===Булевы функции===
Заметим, что управляющая часть МТ считывает с ленты входную строчку и завершается, записав на ленту выходную строчку. Без ограничения общности, будем рассматривать бинарные строки. Следовательно, управляющая часть МТ есть булева функция.
<br>
Каждая Машина Тьюринга вычисляет определенную вычислимую функцию. Так как мы можем записать управляющий автомат в виде строки, можно подать Машину Тьюринга и входные данные на вход другой Машине Тьюринга. Следовательно, достаточно построить универсальную МТ.
<br>
Если показать, что мы можем построить в игре "Жизнь" любую булеву функцию, то мы сможем построить булеву функцию УМТ.
Из курса дискретной математики [[Полные системы функций. Теорема Поста о полной системе функций |известно]], что NAND - полная система, т.е. с его помощью можно построить любую. Следовательно, чтобы построить любую булеву функцию, нам нужно просто построить NAND, то есть NOT и AND в игре "Жизнь".
<br>
===Построение NOT===
[[Файл:Not.png|250px|thumb|right]]
Рассмотрим поток данных, состоящий из планеров. Наличие планера - 1, отсутствие - 0. Добавим поток планеров, состоящий только из 1. При столкновении планеры исчезают, следовательно на месте 1 образуется 0 и наоборот.
<br><br><br><br><br><br><br><br><br><br><br><br>
===Построение AND===
[[Файл:And.png|250px|thumb|right]]
См. рисунок. Пусть x AND y, тогда y соударяется с NOT(x). Если NOT x = 1, то на выходе ничего не попадет, если NOT x = 0, то просто пройдет y.
}}
<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
