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

1

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

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

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

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

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

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

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

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

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

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

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