Алгоритмически неразрешимые задачи | Задачи (11 кл. 136 ч.)

Планирование уроков на учебный год (по учебнику К.Ю. Полякова, Е.А. Еремина, полный углублённый курс, по 4 часа в неделю)


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



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

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

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

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

Задачи


Задачи


1. В качестве доказательства того, что следующая функция вычислима, напишите программу для машины Поста.

2. Докажите, что следующая функция вычислима:

В качестве доказательства напишите программы для машин Тьюринга и Поста, а также НАМ.

*3. Первой задачей, неразрешимость которой была доказана, была проблема самоприменимости: по заданному тексту программы Р определить, останавливается ли программа Р, если ей на вход подать текст этой же программы. Докажите, что проблема останова сводится к проблеме самоприменимости (именно так и была доказана неразрешимость проблемы останова).

Следующая страница §35. Алгоритмически неразрешимые задачи



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







Наверх