close

Вход

Забыли?

вход по аккаунту

?

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

код для вставкиСкачать
урок по учебнику Гейна А.Г.
Алгоритмически неразрешимые задачи
§
14, стр. 76
-
78
Доказательство не существования алгоритма, пригодного для решения любой задачи
1 этап
(1724
-
1804, Кенигсберг
2 этап
Допустим, что существует алгоритм,
способный решить любую задачу
Существует исполнитель,
способный выполнить такой алгоритм...
Рассмотрим множество алгоритмов, предназначенных для обработки символьной переменной x
. Необходимо по тексту алгоритма и значению переменной x
узнать, закончится ли алгоритм за конечное число шагов.
Алгоритм
А (
арг
: В, х
; рез
:
z);
сим:
В, x
;
цел:
z;
{
запросить В;
запросить х
;
Если
(алгоритм В закончил работу на тексте х
за конечное число шагов то
{z:=1;} иначе
{z:=0;}
}
Алгоритм
C;
сим:
В, x
;
цел:
z;
{
запросить В;
запросить х
;
z:=1; Делать пока
z=1
{
вызвать
А(В, x, z);}
}
Задачи, для которых не существует алгоритма решения называются алгоритмически неразрешимыми.
Д. Гильберт (1842
-
1943)
Ю.В. Матиясевич
Автор
zukovaivik
Документ
Категория
Презентации
Просмотров
356
Размер файла
252 Кб
Теги
алгоритмического, неразрешимые, задачи
1/--страниц
Пожаловаться на содержимое документа