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