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

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

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

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

Существуют и невычислимые функции.

Пример:

Известно, что математическая постоянная π — иррациональное число, его десятичная запись бесконечна и не периодична. Введем функцию h(n), которая для любого натурального числа n равна 1, если в десятичной записи числа π есть n стоящих подряд девяток, окруженных другими цифрами, и равна нулю, если такой цепочки девяток нет. Как вычислить значение этой функции при некотором заданном n?

Конечно, можно вычислять друг за другом десятичные знаки числа π (такие алгоритмы математикам известны!) и проверять, не нашлась ли в полученной последовательности цифр цепочка из n девяток. С помощью такого "наивного” алгоритма можно найти такие значения n, при которых h(n) = 1: обнаружив требуемую цепочку, алгоритм закончит работу. Например, анализ первых 800 знаков показывает, что h(n) = 1 при n = 0, 1, 2, 6. Но если для какого-то n функция h(n) равна нулю, то наивный алгоритм никогда не остановится. Более того, для этой функции вообще не существует алгоритма, который при любом n останавливается и выдает значение h(n) в качестве результата. Поэтому такая функция невычислима.

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

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

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

Таким образом, всякий алгоритм можно рассматривать как некоторое универсальное средство для решения целого класса задач.

Оказывается, что существуют такие классы задач, для решения которых, нет и не может быть единого универсального приема. Проблемы решения такого рода задач называют алгоритмически неразрешимыми проблемами. Однако алгоритмическая неразрешимость задачи того или иного класса вовсе не означает невозможность решения любой конкретной задачи из этого класса. Речь идет о невозможности решения всех задач данного класса одним и тем же приемом.

Одной из первых задач, для которой была доказана неразрешимость, является проблема остановки.

Проблема останова МТ:

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

Алан Тьюринг доказал в 1936 году, что не существует общего алгоритма для решения проблемы остановки. Другими словами, проблема остановки неразрешима на машине Тьюринга.

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

Доказательство неразрешимости проблемы остановки важно тем, что к ней можно свести другие задачи.

Доказательство неразрешимости проблемы остановки (из википедии)

Рассмотрим множество алгоритмов, которые принимают на вход натуральное число и на выходе тоже выдают натуральное число. Каждый алгоритм можно записать в виде конечной последовательности символов внешнего алфавита некоторой универсальной МТ. Упорядочим множество лексикографически (в словарном порядке), при этом каждый алгоритм получит свой порядковый номер. F алгоритм решающий проблему остановки, который получает на вход пару натуральных чисел , и:

останавливается и возвращает 1, если алгоритм с номером не останавливается, получив на вход

не останавливается в противном случае (если алгоритм с номером останавливается, получив на вход ).

Докажем, что F не существует.

Доказательство от противного. Допустим, F существует. Напишем алгоритм F₁, который принимает на вход число , передает пару аргументов F и возвращает результат его работы. Другими словами, F₁ останавливается в том и только том случае, если не останавливается алгоритм с номером , получив на вход число . Пусть - это порядковый номер F₁ в множестве . Запустим F₁, передав ему это число . F₁ остановится в том и только том случае, если алгоритм с номером (то есть, он сам) не останавливается, получив на вход число (какое мы ему и передали). Из этого противоречия следует, что наше предположение неверно: F не существует, что и требовалось доказать.