271
правка
Изменения
→Эквивалентность двухсчётчиковой машины МТ
|statement=Для любого перечислимого языка <tex>L</tex> существует двухсчётчиковая машина, которая распознает этот язык.
|proof=
Утверждение теоремы очевидно следует из двух описанных выше лемм, и [[Стековые машины, эквивалентность двухстековой машины МТ|эквивалентности двухстековой машины машине Тьюринга]] и тезиса Тьюринга-Черча.
}}
==Источники==
* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' — '''Введение в теорию автоматов, языков и вычислений''', 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2002. — 528 с. : ISBN 5-8459-0261-4 (рус.)
