275
правок
Изменения
м
→Эквивалентность двухстековой машины машине Тьюринга
== Эквивалентность двухстековой машины машине Тьюринга ==
{{Теорема
|statement=Язык <tex>L</tex> допускается [[Машина Тьюринга | машиной Тьюринга ]] тогда и только тогда, когда он допускается двухстековой машиной.
|proof=
Для упрощения доказательства без умаления общности предположим, что вход для двухстековой машины заканчивается специальным символом <tex>\$</tex>, которого нет в исходном алфавите. <br>
