40
правок
Изменения
Нет описания правки
|statement=Язык <tex>L</tex> допускается машиной Тьюринга тогда и только тогда, когда он допускается двухстековой машиной.
|proof=
Для упрощения доказательства без умаления общности предположим, что вход для двухстековой машины заканчивается специальным символом <tex>\$</tex>, которого нет в исходном алфавите (аналог пробела в МТ). <br>
[[Изображение:SM.png|400px|thumb|left|Рис. 2. Представление ленты МТ двумя стеками]]
<tex>\Rightarrow)</tex>
