Обсуждение участницы:Mariashka — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «{{Определение |id=def1 |definition='''Игра "Жизнь''' (англ. ''Conway's Game of Life'') — клеточный автомат, придум...»)
 
(Удалено содержимое страницы)
 
(не показана 1 промежуточная версия этого же участника)
Строка 1: Строка 1:
{{Определение
 
|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>
 
===Построение 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>
 
== Построение ==
 
Подробное описание построения МТ можно найти здесь:
 
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
 

Текущая версия на 11:10, 13 января 2016