Обсуждение участницы:Mariashka - История изменений

Mariashka: Удалено содержимое страницы

2016-01-13T08:10:57Z

Удалено содержимое страницы

Mariashka в 17:31, 12 января 2016

2016-01-12T17:31:47Z

Mariashka: Новая страница: «{{Определение |id=def1 |definition='''Игра "Жизнь''' (англ. ''Conway's Game of Life'') — клеточный автомат, придум...»

2016-01-12T14:22:55Z

Новая страница: «{{Определение |id=def1 |definition='''Игра "Жизнь''' (англ. ''Conway's Game of Life'') — клеточный автомат, придум...»

Новая страница

{{Определение
|id=def1
|definition='''Игра "Жизнь''' (англ. ''Conway's Game of Life'') — клеточный автомат, придуманный английским математиком Джоном Конвеем в 1970 году.
}}

== Правила ==
* Действие происходит на бесконечной плоскости, разделенной на клетки
* Каждая клетка может находиться в двух состояниях: быть живой или быть мёртвой
* У каждой клетки 8 соседей
* Если клетка жива и у нее 2-3 живых соседа, то она остается живой, иначе умирает
* Если клетка мертва и у нее 3 живых соседа, то она становится живой, иначе остается мертвой
* Игра прекращается, если на поле не останется ни одной живой клетки
* Игра прекращается, если при очередном шаге ни одна из клеток не меняет своего состояния
* Игра прекращается, если конфигурация на очередном шаге в точности повторит себя же на одном из более ранних шагов

== Универсальность ==
{{Теорема
|statement = Игра "Жизнь" универсальна.
|proof =
Для того, чтобы доказать этот факт, докажем возможность построения всех возможных Машин Тьюринга.

В состав машины Тьюринга входит:
* неограниченная в обе стороны лента, разделённая на ячейки
* управляющее устройство, способное находиться в одном из множества состояний.
 
Доказательство строится на том, что простая логика, необходимая для построения МТ, может быть построена в игре "Жизнь":
* детерминированный конечный автомат(с часами)
* ленту(с ячейками памяти)
* головку записи-чтения
===Базовые конструкции===
Рассмотрим базовые конструкции необходимые для построения этих элементов МТ.
[[Файл: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 - фигура, поглощающая планеры
 
 
===Память===
Ячейки памяти можно построить с помощью стабильныx конструкций. [[Файл:Memory.png|150px]] 
Можно также построить c помощью планеров: наличие планера - 1, отсутствие - 0. [[Файл:Datatransmission.png|150px]]
 
===Часы===

В клеточных автоматах изначально есть часы, так как время увеличивается. Но в МТ необходимо, например, через определенное время передвигать головку записи, передавать информацию и пр. Для этой цели можно использовать планеры или космические корабли, так как они двигаются с известной скоростью. Следовательно, в качестве часов используем glider gun.

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

Заметим, что управляющая часть МТ считывает с ленты входную строчку и завершается, записав на ленту выходную строчку. Без ограничения общности, будем рассматривать бинарные строки. Следовательно, управляющая часть МТ есть булева функция.
 
Каждая Машина Тьюринга вычисляет определенную вычислимую функцию. Так как мы можем записать управляющий автомат в виде строки, можно подать Машину Тьюринга и входные данные на вход другой Машине Тьюринга. Следовательно, достаточно построить универсальную МТ.
 
Если показать, что мы можем построить в игре "Жизнь" любую булеву функцию, то мы сможем построить булеву функцию УМТ.
Из курса дискретной математики [[Полные системы функций. Теорема Поста о полной системе функций |известно]], что NAND - полная система, т.е. с его помощью можно построить любую. Следовательно, чтобы построить любую булеву функцию, нам нужно просто построить NAND, то есть NOT и AND в игре "Жизнь".
 

===Построение NOT===
[[Файл:Not.png|250px|thumb|right]]
Рассмотрим поток данных, состоящий из планеров. Наличие планера - 1, отсутствие - 0. Добавим поток планеров, состоящий только из 1. При столкновении планеры исчезают, следовательно на месте 1 образуется 0 и наоборот.
 
===Построение AND===
[[Файл:And.png|250px|thumb|right]]
См. рисунок. Пусть x AND y, тогда y соударяется с NOT(x). Если NOT x = 1, то на выходи ничего не попадет, если NOT x = 0, то просто пройдет y.

}}
 
== Построение ==
Подробное описание построения МТ можно найти здесь:
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

← Предыдущая		Версия 08:10, 13 января 2016
Строка 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~~

@@ Строка 67: / Строка 67: @@
 ===Построение AND===
 [[Файл:And.png|250px|thumb|right]]
-См. рисунок. Пусть x AND y, тогда y соударяется с NOT(x). Если NOT x = 1, то на выходи ничего не попадет, если NOT x = 0, то просто пройдет y.
+См. рисунок. Пусть x AND y, тогда y соударяется с NOT(x). Если NOT x = 1, то на выходе ничего не попадет, если NOT x = 0, то просто пройдет y.
 }}