102
правки
Изменения
Нет описания правки
* управляющее устройство, способное находиться в одном из множества состояний.
<br>
Доказательство строится на том, что простая логика, необходимая для построения МТ, может быть построена в игре "Жизнь":* [[Детерминированные_конечные_автоматы|детерминированный конечный автомат]],* ленту(с ячейками памяти),* головку записи-чтения.
<br>
===Базовые конструкции===
См. рисунок. Пусть <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]]
}}
== Следствие ==
{{Теорема
|about=
Следствие
|statement=
Проблема останова игры «Жизнь» неразрешима.
}}
== См.также ==
