102
правки
Изменения
м
== Следствие =={{Теорема|about=СледствиеУтверждение
[http:<references//eprints.uwe.ac.uk/22323 Rendell, P. (2014) Turing machine universality of the game of life. PhD, University of the West of England.]>
Нет описания правки
|statement = Игра «Жизнь» вычисляет то же множество функций, что и МТ.
|proof =
[[Файл:Types.png|250px|thumb|right|Базовые конструкции]]
[[Файл:Glidergun.png|200px|thumb|right| Glider gun]]
[[Файл:Eater.png|150px|thumb|right| Glider eater]]
* управляющее устройство, способное находиться в одном из множества состояний.
<br>
Доказательство строится на том, что простая логика, необходимая для построения МТ, может быть построена в игре "Жизнь"«Жизнь»<ref>[http://eprints.uwe.ac.uk/22323 Rendell, P. (2014) Turing machine universality of the game of life. PhD, University of the West of England]</ref>.
<br>
===Базовые конструкции===
Рассмотрим базовые конструкции необходимые для построения этих элементов МТ.
<br><br>
В игры "Жизнь" «Жизнь» можно построить различные конструкции (см. рис.):* стабильные {{---}} не меняются с течением времени(первые два ряда),
* циклические {{---}} принимают исходное положение каждые <tex>n</tex> итераций (третий ряд),
* планер (glider) {{---}} фигура, которая смещается на одну клетку вниз и в право каждые <tex>4</tex> итерации (<tex>4</tex> четвертый ряд),
* космический корабль {{---}} фигура, которая смещается ортогонально на <tex>1</tex> клетку каждые <tex>4</tex> итерации,
* glider gun {{---}} фигура, бесконечно производящая планер каждые <tex>30</tex> итераций,
Каждая МТ вычисляет определенную вычислимую функцию. Так как мы можем записать управляющий автомат в виде строки, можно подать МТ и входные данные на вход другой МТ. Следовательно, достаточно построить универсальную МТ.
<br>
Если показать, что мы можем построить в игре "Жизнь" «Жизнь» любую булеву функцию, то мы сможем построить булеву функцию УМТ.
Так как <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>.
[[Файл:And.png|300px]]
}}
|statement=
Проблема останова игры «Жизнь» неразрешима.
* [[Неразрешимость проблемы существования решения диофантова уравнения в целых числах]]
== Примечания ==
== Источники информации ==
* [https://ru.wikipedia.org/wiki/%D0%96%D0%B8%D0%B7%D0%BD%D1%8C_(%D0%B8%D0%B3%D1%80%D0%B0) Википедия {{---}} Жизнь (игра)]
