102
правки
Изменения
Нет описания правки
[[Файл:And.png|300px]]
}}
==Неразрешимость==
{{Теорема
|statement=
[[Файл:TM.png|300px|thumb|right| МТ в игре «Жизнь»]]
[[Файл:TM_diagram.png|300px|thumb|right| Схема МТ в игре «Жизнь»]]
[[Файл:Finite_state_control.png|300px|thumb|right| Схема конечного автомата в игре «Жизнь»]]Заметим, что если существует МТ, которая по начальной конфигурации игры «Жизнь» может определить, завершается ли она, то та же МТ может определить останавливается ли любая МТ, что противоречит неразрешимости проблемы останова для МТ. Следовательно, необходимо описать процесс построения МТ в игре «Жизнь».
<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>.=== Конечный автомат ===Конечный автомат представляет собой двумерный массив с двумя входами: предыдущее состояние, получаемое от детектора сигнала, и считанный символ от одного из стеков {{---}} для выбора ряда и колонки.=== Детектор сигнала ===Детектор сигнала распознает информацию, полученную от конечного автомата, и передает ее дальше: информацию о следующем состоянии {{---}} обратно в автомат(с задержкой), где она используется для выбора адреса ряда; информацию о символе для записи {{---}} на один из стеков.=== Стек ===Лента МТ представлена в виде двух стеков, чтобы можно было эмулировать передвижение головки чтения записи по ленте: в каждом цикле один стек делает push символа, другой {{---}} pop. МТ не дожидается сдвига всех ячеек стека.=== Контроллер стека ===Контроллер стека производит конструкцию из планеров, необходимую стека для произведения push или pop.==Некоторые конструкции==<b>Пчелиная королева</b><br>[[Файл:Queen_bee.png|350px]]<br>Небольшая конструкция передвигающаяся туда-обратно, при развороте оставляет стабильную конструкцию, называемую ульем. Умирает, если при возвращении улей не исчез. Используется для построения glider gun.<br><br><b>Buckaroo</b><br>Пчелиная королева с eater. Эта конструкция примечательная тем, что при исчезновении улья возникает "вспышка", которая может менять направление планера.<br><br><b>Pentadecathlon</b><br>[[Файл:Pentadecathlon.png|500px]]<br>Циклическая конструкция, генерирующая небольшую конструкцию, которая может отражать планеры.<br>
}}
== См.также ==
