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

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

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

Задано произвольное алгебраическое уравнение с целыми коэффициентами P(x 1,x 2,…,x n )=0 (Например, ax 1 2 +bx 2 2 +cx 3 3 =0). 10-ая проблема Гильберта Требуется выяснить, существует ли у данного уравнения решение в целых числах.

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

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

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

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

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

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

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