Математическая логика и теория алгоритмов

2.9 Контрольные вопросы  

назад | оглавление |

   
  1. Что такое внешний и внутренний алфавиты МТ ?

  2. Что такое начальное и заключительное состояния МТ ?

  3. Как выглядит команда для МТ?

  4. Что такое конфигурация МТ ?

  5. Сформулируйте тезис Тьюринга.

  6. Какая функция называется примитивно рекурсивной? частично рекурсивной? общерекурсивной? Приведите примеры таких функций.

  7. Назовите базовые функции.

  8. Назовите основные операции получения ч.р.ф.

  9. В чем заключается тезис Чёрча-Клини?

  10. Назовите основные характеристики сложности алгоритмов.

  11. Назовите основные классы сложности алгоритмов.


назад | оглавление |