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



Содержание


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

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

Одной из первых проблем, для которых была строго доказана алгоритмическая неразрешимость, была так называемая проблема останова. Сформулируем ее для программ, написанных на процедурных языках программирования (см. “Языки программирования”).

Зададимся следующим вопросом. Нельзя ли определить программным способом, с помощью самого компьютера, зациклится ли данная программа на определенных входных данных? Может быть, можно написать некоторую универсальную программу (обозначим ее через U), которая принимала бы на вход текст заданной программы и входные данные к ней, анализировала его и выдавала бы ответ, зациклится эта программа на этих входных данных или нет1. Возможность написания программы U кажется правдоподобной: ведь, например, программа-компилятор умеет анализировать текст заданной программы на наличие в нем возможных синтаксических ошибок и т.п. Программа U могла бы стать надстройкой над компилятором, которая вылавливала бы ошибку особого рода — ошибку “бесконечного цикла”.

Уточним формулировку задачи. Каждая программа П в каждом конкретном случае работает с входными данными. (Строго говоря, некоторые программы, например программа вычисления числа с точностью до 100 000 знаков, могут и ничего не получать на вход — в этом случае будем считать, что входные данные для такой программы образуют “пустой набор” — файл из нуля байт.) Можно считать, что эти входные данные берутся всегда из какого-то файла Д. Действительно, все входные данные — символы, вводимые с клавиатуры, файлы и даже движения мышки (здесь подразумевается, что нажатие определенных кнопок в интерфейсе программы — это тоже ввод данных в нее) — можно закодировать в одном общем файле данных. Может случиться, что некоторая программа, получая на вход одни данные, зацикливается, а получая другие — нет.

Работу программы U можно спроектировать следующим образом. Программа U должна получать на вход, во-первых, текст программы П (текстовый файл), а во-вторых, некоторый файл с данными Д (текстовый файл). Затем она должна проанализировать эти два файла и выдать точный ответ: зациклится ли программа П, если П получила на вход файл Д. Можно всегда считать, что программа U может воспринимать на вход любые файлы: например, если файл П не является синтаксически правильной программой на выбранном языке программирования (скажем, Паскале), то программа U это легко определяет, но все равно считает, что в этом случае П является “программой”: например, такой, которая “ничего не делает” и, следовательно, не зацикливается. Соответственно, если файл Д имеет “неправильный формат” (например, на вход программе П требуется число, а в файле Д имеется что-то другое), то программа П всегда останавливается на этих “неправильных данных”. Итак, вот более точное описание программы U:

а) программа U читает два произвольных файла: П и Д;

б) если файл П содержит синтаксически правильную программу (для определенности, на Паскале), а файл Д представляет собой корректные данные для программы П, то программа U проверяет, зациклится ли П на данных Д. Если она зациклится, то на экран компьютера будет выдано сообщение “зациклится”, иначе — “не зациклится”;

в) если файлы П и Д не удовлетворяют условиям б), то на экран выдается сообщение “не зациклится” (и в этой ситуации для простоты мы все равно называем П программой, а Д — данными, и П в этом случае не зацикливается на Д “по определению”).

Предположим, что нам удалось написать такую программу U. Можно считать, что она тоже написана на Паскале. Теперь мы собираемся написать новую программу, которую обозначим через U1. Но прежде мы введем специальное понятие — стандартный номер файла. Любой файл можно представить как слово, быть может, очень длинное. Каждая “буква” этого слова берется из некоторого алфавита. Например, можно считать, что алфавит для таких слов состоит из 256 символов, а каждая буква в слове — это один байт в файле; в качестве “букв” здесь выступают все ASCII-символы — “настоящие буквы”, знаки препинания, пробел, специальные символы и т.д. Таким образом, все файлы могут быть расположены в некоторую упорядоченную бесконечную последовательность:

Ф0, Ф1, Ф2, Ф3, ... (*)

(Сначала идет пустой файл Ф0, в котором нет ни одного байта. Затем перечисляются в алфавитном порядке все файлы, состоящие из одной “буквы”, затем — состоящие из двух “букв”, и т.д.) В этой последовательности каждый файл получает некоторый номер. Этот номер мы и назовем стандартным номером файла. Ясно, что можно написать программу, которая по заданному файлу вычислит стандартный номер этого файла. (Мы считаем, что у нас есть “идеальный” компьютер. Он не имеет ограничений памяти и поэтому может работать с числами, состоящими из сколь угодно большого количества цифр.) Можно также написать программу, которая по заданному числу восстанавливает файл, стандартный номер которого равен n.

Итак, любой файл попадает в последовательность (*) и имеет в ней свой уникальный номер, который мы называем стандартным номером этого файла. Значит, и у любого файла с программой (П), и у любого файла данных (Д) есть свои стандартные номера.

Теперь можно написать программу U1, которая будет делать следующее:

1) получать на вход натуральное число i;

2) восстанавливать файл Фi из последовательности (*), т.е. восстанавливать файл со стандартным номером i;

3) запускать программу U, подавая ей на вход в качестве файла П файл Фi, а в качестве файла Д — тот же самый файл Фi.

Коротко работу программы U1 можно описать так: по заданному числу i она определяет, зациклится ли программа, реализованная в файле со стандартным номером i при работе с данными, записанными в файле, который имеет стандартный номер i (эта программа решает проблему самоприменимости).

Ясно, что программу U1 всегда можно написать так, чтобы она в самом конце работы некоторой переменной z присваивала значение 0 или 1, и в соответствии с этим значением выводила одно из двух сообщений:

if z = 0 then writeln('нe зациклится')

else writein('зациклится')

Теперь подвергнем программу U1 маленькой переделке. Фрагмент, приведенный выше, заменим на такой (**):

if z = 0 then

repeat

until 1 = 2

else writeln('зациклится')

Эту программу (назовем ее U2) сохраним в другом файле. Что делает U2? Она тоже, как и U1, получает на вход число i, но отличается от U1 вот чем: если выяснилось, что исследуемая программа со стандартным номером i не зацикливается на файле данных со стандартным номером i, то сама U2 зацикливается, а в противном случае U2 выдает сообщение “зациклится” и после этого завершает работу.

Программа U2 сама тоже записана в файле. Этот файл обязательно находится в последовательности (*) и имеет некоторый стандартный номер. Пусть k — этот номер. Здесь начинается самое интересное. Что произойдет, если на вход программе U2 в качестве числа i мы подадим число k? В этом случае, конечно, выполнение программы U2 может либо зациклиться, либо остановиться. Предположим, что оно остановится. Тогда, как только компьютер дойдет до выполнения фрагмента (**), переменная z должна получить нулевое значение. После этого, в соответствии с (**), произойдет зацикливание. Предположив, что выполнение остановится, мы выяснили, что выполнение зациклится! Это невозможно. Теперь предположим, что выполнение зациклится. Но тогда программа U2, как говорилось выше, должна выдать сообщение “зациклится” и после этого остановиться. Это тоже невозможно.

Таким образом, программа должна зациклиться, если она остановится, и должна остановиться, если она зациклится. В чем тут дело? Конечно же в том, что мы предполагали возможность написания универсальной программы U, которая определяла бы любую программу на возможность зацикливания. Итак, такой программы U не существует в принципе, или, как говорят математики, проблема останова алгоритмически неразрешима.

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

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

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

Пусть у нас есть посылка R и следствие S, записанные в виде слов (формул) в некотором алфавите, состоящем из букв, цифр, скобок, знаков математических и логических операций. Процесс вывода следствия S из посылки R может быть описан путем указания последовательности допустимых формальных преобразований слов (дедуктивной цепочки).

Проблему распознавания выводимости можно сформулировать следующим образом: Существует ли для любых двух слов R и S дедуктивная цепочка, ведущая от R к S? Решение понимается в смысле существования алгоритма, дающего ответ на этот вопрос для любых слов R и S. В 1936 г. американский математик Черч доказал теорему о том, что проблема распознавания выводимости алгоритмически неразрешима. Тем самым выяснилась причина безуспешности всех прошлых попыток решения задачи, поставленной Лейбницем.

Неразрешимой оказалась и так называемая “10-я проблема Гильберта”. В упрощенной формулировке она звучит так: требуется выработать алгоритм, позволяющий для любого алгебраического уравнения P(x1, x2, …, xn) = 0, где P — многочлен с целыми коэффициентами, выяснить, имеет ли оно целочисленное решение. В 1970 г. советский математик Ю.В. Матиясевич доказал невозможность построения алгоритма для решения этой задачи. Интересно, что если для конкретного уравнения известно, что решение в целых числах есть, то алгоритм отыскания этого решения существует.

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

Методические рекомендации

Данная тема включена в стандарт профильного курса информатики в следующей формулировке: диагональное доказательство несуществования. Здесь имеется в виду канторовский диагональный процесс, который можно использовать для доказательства алгоритмической неразрешимости, в частности, проблемы останова. Именно поэтому в качестве основного материала статьи приведено такое доказательство этой проблемы, которое легко сводится к рассуждениям Кантора. Следует лишь описать канторовские массив-таблицу Т и массив-строку D.

В проблеме останова T[i,j] — крестик, если программа, реализованная в файле со стандартным номером i, зацикливается на данных, расположенных в файле со стандартным номером j, иначе — нолик. Значения T[i,j] для любых заданных i и j могла бы вычислять, после небольших модификаций, программа U (если бы, конечно, она существовала). Значение D[i] — нолик, если программа, реализованная в файле со стандартным номером i, зацикливается на данных, расположенных в файле со стандартным номером i, иначе — крестик. Значения D[i] можно было бы вычислять, используя программу U1. Тогда D[i] не равно Т[i,i] для всех индексов i и D не совпадает ни с одной строкой таблицы Т. А если бы программа U1 существовала, то она имела бы свой номер и ей соответствовала бы одна из строк таблицы T.

Подробнее о канторовском диагональном процессе и соответствующем доказательстве проблемы останова можно прочитать в уже упомянутой статье И.Долмачева “Алан Тьюринг”, которую также можно найти на сайте газеты “Информатика” (в архивных материалах № 5/2000). Два других доказательства алгоритмической неразрешимости данной проблемы можно прочитать в учебнике Е.В. Андреевой, Л.Л. Босовой, И.Н. Фалиной “Математические основы информатики” (М.: БИНОМ. Лаборатория Знаний, 2005) и в методическом пособии к этому учебнику (М.: БИНОМ. Лаборатория Знаний, 2006). Выбор доказательства остается на усмотрение учителя. Например, если в курс информатики включается рассмотрение машины Тьюринга, то и доказательство алгоритмической неразрешимости можно проводить с использованием этого формального аппарата.

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

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


1 При доказательстве алгоритмической неразрешимости этой проблемы использованы материалы статьи Ивана Долмачева “Алан Тьюринг”, “Информатика” № 5/2000.




Наверх