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

- это задача, для которой невозможно построить алгоритм решения.
Алгоритмически неразрешимая задача

В 1900 г. на Международном математическом конгрессе в Париже немецкий математик Д.Гильберт сформулировал 23 математические проблемы.
Сегодня решение (даже частичное) какой-либо проблемы Гильберта расценивается как высшее математическое достижение.

Задано произвольное алгебраическое уравнение с целыми коэффициентами P(x1,x2,…,xn)=0
(Например, ax12+bx22+cx33=0).
10-ая проблема Гильберта
Требуется выяснить, существует ли у данного уравнения решение в целых числах.

В 1970 г. математик Ю.В.Матиясевич (СССР) доказал
невозможность
построения
алгоритма
решения этой задачи.

По описанию произвольного алгоритма и его исходных данных требуется определить остановится ли алгоритм на этих данных или будет работать бесконечно.
Проблема останова
Это классическая алгоритмически неразрешимая задача – доказано в теории алгоритмов.

любой теоремы из любой системы аксиом, которую пытался решить Лейбниц в XVII в., пытаясь построить алгоритм решения любых мат. задач.
Проблема
распознавания выводимости
В 1936 г. амер. математик А.Чёрч доказал теорему об алгоритмической неразрешимости проблемы.

основаны на методе сведения к этим задачам известных алгоритмически неразрешимых задач.
Методы доказательства алгоритмической неразрешимости
Задачи, для которых доказана алгоритмическая неразрешимость, не надо и пытаться решать на ЭВМ – практическая ценность понятия «алгоритмической неразрешимости».

– функция, вычисляемая некоторым алгоритмом.
Вычислимая функция
(алгоритмически вычислимая)
Теория вычислимости – раздел теории алгоритмов.

Пример
невычислимой функции
Анализ первых 800 знаков разложения π показывает, что f(n)=1 для n=0, 1, 2, 6.
Не существует общего метода (алгоритма), реализующего эту функцию.

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