Изменения
→Эквивалентность двухсчетчиковой машины машине Тьюринга
|statement=Язык <tex>L</tex> допускается машиной Тьюринга тогда и только тогда, когда он допускается трехсчетчиковой машиной.
|proof=
Так как [[Стековые машины, эквивалентность двухстековой машины МТ|двухстековая машина эквмвалентна эквивалентна машине Тьюринга]], то достаточно показать, что трехсчетчиковая машина эквивалентна по вычислительной мощности трехсчетчиковой машине.
}}
==Источники==
Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман. Введение в теорию автоматов, языков и вычислений.
