Изменения

Перейти к: навигация, поиск
Нет описания правки
== Эквивалентность двухстековой машины машине Тьюринга ==
{{Теорема
|statement=Язык <tex>L </tex> допускается машиной Тьюринга тогда и только тогда, когда он допускается двухстековой машиной.
|proof=
sdfДля упрощения доказательства без умаления общности предположим, что вход для двухстековой машины заканчивается специальным символом <tex>\$</tex>, которого нет в исходном алфавите (аналог пробела в МТ).
}}
40
правок

Навигация