102
правки
Изменения
Нет описания правки
== Правила ==
== Универсальность Булевы функции ==
{{Теорема
|statement = Игра "Жизнь" вычисляет то же множество функций, что и МТВ игре «Жизнь» можно построить любую булеву функцию.|proof = Для того, чтобы доказать этот факт, докажем возможность построения всех возможных [[Машина_Тьюринга Файл:Types.png|машин Тьюринга250px|thumb|right|Базовые конструкции]]. В состав МТ входит[[Файл:* неограниченная в обе стороны лента, разделённая на ячейки* управляющее устройство, способное находиться в одном из множества состоянийGlidergun. png|200px|thumb|right| Glider gun]]<br>Доказательство строится на том, что простая логика, необходимая для построения МТ, может быть построена в игре "Жизнь"[[Файл:Eater.png|150px|thumb|right| Glider eater]]* детерминированный конечный автомат(с часами)* ленту(с ячейками памяти)* головку записи-чтения
===Базовые конструкции===
Рассмотрим базовые конструкции необходимые для построения этих элементов МТ.[[Файл: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>===Часы===
В клеточных автоматах изначально есть часы, так как время увеличиваетсяигры «Жизнь» можно построить различные конструкции (см. рис. Но в МТ необходимо):* стабильные {{---}} не меняются с течением времени (первые два ряда), например* циклические {{---}} принимают исходное положение каждые <tex>n</tex> итераций (третий ряд), через определенное время передвигать головку записи* планер (glider) {{---}} фигура, передавать информацию которая смещается на одну клетку вниз и пр. Для этой цели можно использовать планеры или космические кораблив право каждые <tex>4</tex> итерации (четвертый ряд),* космический корабль {{---}} фигура, так как они двигаются с известной скоростью. Следовательнокоторая смещается ортогонально на <tex>1</tex> клетку каждые <tex>4</tex> итерации, в качестве часов используем * glider gun{{---}} фигура, бесконечно производящая планер каждые <tex>30</tex> итераций,* glider eater {{---}} фигура, поглощающая планеры.
===Булевы функции===
Так как <tex>\triangledown</tex> ([[Определение_булевой_функции#.D0.91.D0.B8.D0.BD.D0.B0.D1.80.D0.BD.D1.8B.D0.B5_.D1.84.D1.83.D0.BD.D0.BA.D1.86.D0.B8.D0.B8|штрих Шеффера]] или NAND) является [[Полные системы функций. Теорема Поста о полной системе функций |полной системой]], то достаточно построить <tex>NOT</tex> и <tex>AND</tex>, чтобы показать возможность построения любой булевой функции.
===Построение NOT===
Рассмотрим поток данных, состоящий из планеров. Наличие планера {{---}} <tex>1</tex>, отсутствие {{---}} <tex>0</tex>. Добавим поток планеров, состоящий только из <tex>1</tex>. При столкновении планеры исчезают, следовательно на месте <tex>1</tex> образуется <tex>0</tex> и наоборот.
===Построение AND===
Небольшая конструкция передвигающаяся туда-обратно, при развороте оставляет стабильную конструкцию, называемую ульем. Умирает, если при возвращении улей не исчез. Используется для построения glider gun.
====Buckaroo====
Пчелиная королева с eater. Эта конструкция примечательная тем, что при исчезновении улья возникает "вспышка", которая может менять направление планера.
====Pentadecathlon====
[[Файл:Pentadecathlon.png|500px]]
Циклическая конструкция, генерирующая небольшую конструкцию, которая может отражать планеры.
}}
== См.также ==* [[Неразрешимость исчисления предикатов первого порядка]]* [[Примеры неразрешимых задач: задача о выводе в полусистеме Туэ|Задача о выводе в полусистеме Туэ]]* [[Примеры неразрешимых задач: задача о замощении|Задача о замощении]]* [[Примеры неразрешимых задач: однозначность грамматики|Однозначность грамматики]]* [[Неразрешимость задачи об эквивалентности КС-грамматик]]* [[Неразрешимость проблемы существования решения диофантова уравнения в целых числах]]== Примечания ==<br><br><br><br><br><br><br><brreferences/>== Построение Источники информации ==Подробное описание построения МТ можно найти здесь* [https:Rendell, P//ru.wikipedia. org/wiki/%D0%96%D0%B8%D0%B7%D0%BD%D1%8C_(2014%D0%B8%D0%B3%D1%80%D0%B0) Turing machine universality of the game of life. PhD, University of the West of England. Available from: Википедия {{---}} Жизнь (игра)]* [http://eprintsacademic.uweregis.acedu/dbahr/generalpages/CellularAutomata/CA_part14_files/frame.uk/22323htm Proving Life is Universal] [[Категория: Теория формальных языков]][[Категория: Теория вычислимости]][[Категория: Примеры неразрешимых задач]]