1. Зачем понадобилось уточнять понятие «алгоритм»? 2. Какие задачи рассматриваются в теории алгоритмов? 3. Почему можно ограничиться алгоритмами обработки символьных строк? Можно ли рассматривать только алгоритмы для преобразования двоичных кодов? 4. Как связаны понятия «алгоритм» и «исполнитель»? 5. В каком случае говорят, что два алгоритма эквивалентны? 6. Сравните интуитивное и строгое понятия алгоритма. 7. Что такое состояние машины Тьюринга? 8. Сопоставьте устройство машины Тьюринга с устройством компьютера. Какие устройства машины Тьюринга выполняют те же функции, что и аналогичные устройства компьютера? 9. В чём особенность состояний q0 и q1 машины Тьюринга? 10. Как можно построить программу для машины Тьюринга, которая последовательно выполняет операции А и Б, если уже есть две программы, которые выполняют две эти операции по отдельности? 11. Сравните машины Тьюринга и Поста. 12. Зачем нумеруются строки в программе для машины Поста? 13. Что такое нормальный алгорифм Маркова? 14. Зачем используют специальные символы в НАМ? 15. Что означает эквивалентность различных универсальных исполнителей?