Математическая логика и теория алгоритмов
|
2.9 Контрольные вопросы |
назад | оглавление | |
Что такое внешний и внутренний алфавиты МТ ?
Что такое начальное и заключительное состояния МТ ?
Как выглядит команда для МТ?
Что такое конфигурация МТ ?
Сформулируйте тезис Тьюринга.
Какая функция называется примитивно рекурсивной? частично рекурсивной? общерекурсивной? Приведите примеры таких функций.
Назовите базовые функции.
Назовите основные операции получения ч.р.ф.
В чем заключается тезис Чёрча-Клини?
Назовите основные характеристики сложности алгоритмов.
Назовите основные классы сложности алгоритмов.