Обсуждение:Счетчиковые машины, эквивалентность двухсчетчиковой машины МТ

Материал из Викиконспекты
Перейти к: навигация, поиск

Todo[править]

«…то достаточно показать, что трехсчетчиковая машина эквивалентна по вычислительной мощности трехсчетчиковой машине.» Что-то здесь не так (подсказка: это утверждение очевидно=).
«Тогда операции со стеком можно реализовать на трехсчетчиковой машине:…» В списке каждая строчка с маленькой буквы, строчки заканчиваются точкой с запятой.
Код программы, реализующей добавление в стек — это замечательно, но мы строим автомат. Интуитивно поняяяятно, конечно, как он строится, но лучше сделать какие-нибудь комментарии (не слишком объёмные, желательно, но чтобы можно было понять, что вообще происходит).
В условии второй леммы стоит заменить нелепый знак [math]\forall[/math] на русский язык.
«…где [math]p_{k}[/math] - k-е простое число. Тогда любое состояние k-счетчиковой машины…» Здесь потерян тех. Под конец этого абзаца надо заменить нелепые [math]\forall[/math] и [math]\exists[/math] на русский язык.
В доказательстве теоремы стоит указать какую-нибудь ссылку на тезис Тьюринга-Черча.
Нормально оформить источники.
Во всём конспекте править «ё» и тире.Евгений Лукьянец