Вопрос 1. Из чего состоит машина Поста? Из каретки Из ленты Из ленты и каретки
Вопрос 2. Лента в машине Поста... конечна бесконечна
Вопрос 3. Как нумеруются секции на ленте машины Поста? относительно каретки не нумеруются жестко пронумерованы
Вопрос 4. Что записывается в секции на ленте в машине Поста? 1 или 0 ничего или V ничего, 1, 0,
Вопрос 5. В машине Поста. Информация о том, какие секции пусты, а какие отмечены, образует ... состояние ленты число
Вопрос 6. Как может двигаться каретка в машине Поста? влево вправо влево и вправо никак
Вопрос 7. Сколько секций обозревает каретка за один раз в машине Поста? текущую и следующую текущую следующую
Вопрос 8. Информация о том, какие секции пусты, а какие отмечены и где стоит каретка в машине Поста, ... образует состояние ленты образует состояние машины Поста позволяет считать число с ленты
Вопрос 9. Сколько команд у машины Поста? 5 6 7
Вопрос 10. Как называется число, стоящее в конце команды машины Поста? пересылкой отсылкой индексом постфиксом
Вопрос 11. Чему равна длина программы машины Поста? - Количеству ... отсылок команд различных команд
Вопрос 12. Из чего состоит машина Тьюринга? из автомата из ленты из ленты и автомата
Вопрос 13. Что вписывается в ячейки машины Тьюринга? 0 или V 0 или 1 символы из {0, ..., N-1}
Вопрос 14. Какие движения может осуществлять автомат машины Тьюринга? R или S R или L R, L, S
Вопрос 15. Как выглядит программа машины Тьюринга? Таблица Список
Вопрос 16. Что располагается в левом столбце программы? Символы внешнего алфавита Символы внутреннего алфавита
Вопрос 17. Множество состояний {q1, ... qr} машины Тьюринга образуют ... внешний алфавит внутренний алфавит
Вопрос 18. Выберите правильный вариант для машины Тьюринга? 0 R q3 R 1 => 2
Вопрос 19. Если означенная клетка в программе машины Тьюринга оказывается пустой, то машина... зацикливается выполняет предыдущую команду останавливается
Вопрос 20. Машина Тьюринга - ... всегда останавливается может остановиться, может не остановиться никогда не останавливается
Вопрос 21. Тезис Маркова - Всякий алгоритм ... нормализуем реализуем