Изменения

Перейти к: навигация, поиск

Игра «Жизнь»

261 байт добавлено, 13:16, 13 января 2016
Нет описания правки
{{Теорема
|statement = Игра "Жизнь" вычисляет то же множество функций, что и МТ.
|proof = [[Файл:Types.png|250px|right]][[Файл:Glidergun.png|200px|thumb|right| Glider gun]][[Файл:Eater.png|150px|thumb|right| Glider eater]]
Для того, чтобы доказать этот факт, докажем возможность построения всех возможных [[Машина_Тьюринга |машин Тьюринга]].
<br>
В состав МТ входит:
* неограниченная в обе стороны лента, разделённая на ячейки
* ленту(с ячейками памяти)
* головку записи-чтения
<br>
===Базовые конструкции===
Рассмотрим базовые конструкции необходимые для построения этих элементов МТ.
[[Файл:Types.png|250px|thumb|right]][[Файл:Glidergun.png|200px|thumb|right| Glider gun]][[Файл:Eater.png|200px|thumb|right| Glider eater]]<br><br>
В игры "Жизнь" можно построить различные конструкции (см. рис.):
* стабильные {{---}} не меняются с течением времени(первые два ряда)
<br><br>
===Память===
Ячейки памяти можно построить с помощью стабильныx конструкций[[Файл:Memory. png|200px|thumb|right|Стабильная ячейка]][[Файл:MemoryDatatransmission.png|150px|thumb|right|Передача данных]]Ячейки памяти можно построить с помощью стабильныx конструкций<br>Можно также построить c помощью планеров: наличие планера {{---}} <tex>1</tex>, отсутствие {{---}} <tex>0</tex>. [[Файл:Datatransmission.png|150px]]<br> 
===Часы===
 
В клеточных автоматах изначально есть часы, так как время увеличивается. Но в МТ необходимо, например, через определенное время передвигать головку записи, передавать информацию и пр. Для этой цели можно использовать планеры или космические корабли, так как они двигаются с известной скоростью. Следовательно, в качестве часов используем glider gun.
===Булевы функции===
 
Заметим, что управляющая часть МТ считывает с ленты входную строчку и завершается, записав на ленту выходную строчку. Без ограничения общности, будем рассматривать бинарные строки. Следовательно, управляющая часть МТ есть булева функция.
<br>
Если показать, что мы можем построить в игре "Жизнь" любую булеву функцию, то мы сможем построить булеву функцию УМТ.
Из курса дискретной математики [[Полные системы функций. Теорема Поста о полной системе функций |известно]], что <tex>NAND</tex> - полная система, т.е. с его помощью можно построить любую. Следовательно, чтобы построить любую булеву функцию, нам нужно просто построить <tex>NAND</tex>, то есть <tex>NOT</tex> и <tex>AND</tex> в игре "Жизнь".
<br>
===Построение NOT===
[[Файл:Not.png|250px|thumb]]Рассмотрим поток данных, состоящий из планеров. Наличие планера {{---}} <tex>1</tex>, отсутствие {{---}} <tex>0</tex>. Добавим поток планеров, состоящий только из <tex>1</tex>. При столкновении планеры исчезают, следовательно на месте <tex>1</tex> образуется <tex>0</tex> и наоборот.<br>[[Файл:Not.png|300px]]
===Построение 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>.<br>[[Файл:And.png|300px]]
}}
<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== Источники информации ==* [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]
102
правки

Навигация