Урок 61
Алгоритмически неразрешимые задачи
(§35. Алгоритмически неразрешимые задачи)

Содержание урока

Вычислимые и невычислимые функции

Когда задача алгоритмически неразрешима?

Вопросы и задания

Задачи

Вопросы и задания

1. Что такое вычислимая функция?

2. Приведите пример невычислимой функции.

3. Что такое алгоритмически неразрешимые задачи? Приведите известные вам примеры.

4. Что такое проблема останова? Каковы её следствия?

5. Что такое проблема эквивалентности?

6. Как можно доказать алгоритмическую неразрешимость новой задачи?

Следующая страница Задачи

Cкачать материалы урока