Экстраалгоритм и три неразрешимые проблемы
Вернемся на время к нормальным алгоритмам. Мы помним, что запись нормального алгоритма в алфавите А содержит, кроме букв в А, еще две буквы: «→» и «→•».Введем временно еще одну букву, не одинаковую ни с одной из указанных двух букв и не являющуюся буквой
в А.
Пусть это будет для определенности л. Запись нормального алгоритма можно превратить в слово, выписывая его формулы одну за другой и разделяя их буквами X. Такое слово очень легко снова превратить в запись нормального алгоритма (столбец формул). Теперь можно придумать некоторый прием кодирования, в результате которого полученное слово станет словом в А, конечно при условии, что алфавит А состоит не менее, чем из двух букв. Этот способ кодирования, например, может быть следующим. Перенумеруем все буквы алфавита. Пусть при этом будут использованы номера 1, 2..... k (k — число букв, входящих в А). Далее, букве «→» присвоен номер k+1, букве «→•»— номер k+2, а букве k — номер k+3. Возьмем теперь какие-либо две буквы в А. Пусть для определенности это будут а и b. Будем кодом j-й буквы (по нашей нумерации) считать слово в А, начинающееся буквой а, содержащее затем j букв b и кончающееся снова буквой а. Например, код четвертой буквы будет иметь вид
a b b b b а.
Заменяя в слове, которое мы получили из записи нормального алгоритма, все буквы их кодами, получим (новое) слово в А, являющееся кодом нормального алгоритма.
Условимся говорить, что алгоритм F: а) применим к алгоритму Ф, если он применим к его коду, и б) неприменим к алгоритму Ф, если он неприменим к его коду. Теперь можно говорить о самоприменимости нормального алгоритма или о его несамоприменимости.
Легко убедиться в том, что нормальный алгоритм в алфавите А, применимый ко всем несамоприменимым и только несамоприменимым алгоритмам, невозможен (не существует). Если бы он существовал, то не мог бы быть самоприменимым, так как он применим только к несамоприменимым алгоритмам. Одновременно он не мог бы быть и несамоприменимым, так как он применим ко всем несамоприменимым, а значит, и к себе.
Такой нормальный алгоритм, назовем его нормальным экстраалгоритмом в А[15], не существует. Можно доказать, что не существует и нормального экстраалгоритма над А.
He может существовать и какой-нибудь алгоритм из других классов алгоритмов, который был бы применим ко всем несамоприменимым нормальным алгоритмам в Л (его будем называть экстраалгоритмом). Это вытекает из принципа нормализации, который гласит, что в этом случае существовал бы эквивалентный ему нормальный алгоритм над алфавитом А, мы же знаем, что такого нормального алгоритма нет. Но из невозможности указанного экстраалгоритма вытекает ряд интересных следствий.
Оказывается, что невозможен алгоритм, который распознавал бы несамоприменимость нормальных алгоритмов. Такой алгоритм, если бы он существовал, должен бы быть применимым к любому нормальному алгоритму и перерабатывать его в некоторое определенное слово, если он несамоприменим. Это определенное слово, если оно получится, будет обозначать ответ «да».
В случае отрицательного ответа может получаться либо какое-нибудь определенное слово, либо любое слово, отличное от слова, имеющего смысл «да» (естественно считать, что если не «да», то «нет»). В дальнейшем для краткости условное слово, обозначающее «да», будем называть словом «да».
Докажем, что алгоритм распознавания несамоприменимости нормальных алгоритмов невозможен. Для этого предположим, что такой алгоритм существует. Назовем его В. Тогда можно построить следующий алгоритм (обозначим его С):
1. Выполнить алгоритм В. Перейти к следующему пункту.
2. Если получен ответ «да», то перейти к п. 3, иначе перейти к п. 4.
3. Окончить процесс.
4. Перейти к п. 4.
Алгоритм С применим к каждому несамоприменимому нормальному алгоритму (и дает для него результат «да»), а в случае, когда алгоритм несамоприменим (ответ «да» алгоритмом В не получен), его выполнение продолжается бесконечно (он «зацикливается» на п. 4). Но тогда С применим ко всем несамоприменимым и только несамоприменимым нормальным алгоритмам в А. Он, следовательно, является экстраалгоритмом. Значит, разрешимость проблемы распознавания несамоприменимости привела бы к абсурду. Поэтому указанная проблема неразрешима.
Но теперь ясно, что неразрешима и проблема распознавания самоприменимости. В самом деле, если бы существовал алгоритм D, распознающий самоприменимость, то существовал бы и алгоритм, гласящий:
1. Выполнить алгоритм D. Перейти к п. 2.
2. Если получено слово «да», перейти к п. 3, иначе перейти к п. 4.
3. Написать «нет». Конец.
4. Написать «да». Конец.
Но последний алгоритм распознавал бы несамоприменимость нормальных алгоритмов в А. Как мы знаем, это невозможно, значит, невозможен и алгоритм D.
Наконец, справедлива теорема:
Проблема распознавания применимости произвольного нормального алгоритма в А к произвольному слову в А неразрешима.
Допустим противное. Пусть существует алгоритм Е, который по заданному алгоритму в A и заданному слову в А распознает, применим ли указанный алгоритм к указанному слову.
Но отличить, является ли слово в A кодом заданного нормального алгоритма или не является, нетрудно. Будем считать, что для этого нами построен некоторый алгоритм G.
Тогда можно построить алгоритм Н:
1. Применить G к заданному слову в А. Перейти к п. 2.
2. Если G дал слово «да», перейти к п. 3, иначе перейти к п. 4.
3. Выполнить алгоритм Е. Конец.
4. Перейти к выполнению п. 4.
Алгоритм Н является алгоритмом, распознающим самоприменимость нормальных алгоритмов в А. Следовательно, он невозможен. Но тогда невозможен и алгоритм Е, так как предположение о его возможности привело к противоречию. Тем самым теорема доказана.
Читатель видит, что некоторые массовые проблемы, вовсе не имеющие абсурдного характера, неразрешимы потому, что из их разрешимости можно было бы вывести абсурд. Нужно заметать, что неразрешимость (массовой) проблемы распознавания применимости нормального алгоритма в А к слову в А совсем не означает, что мы вообще не можем распознавать применимость конкретного алгоритма к конкретному слову или к различным словам. Например, нормальный алгоритм «→•» применим к любому слову в Л, и это сразу видно. Любой алгоритм «→•α», где α — буква А, тоже применим к любому слову в Л. Наоборот, алгоритм «→α» неприменим ни к какому слову в А (он порождает бесконечный процесс приписывания букв а слева к преобразуемому слову).
Неразрешимость проблемы распознавания применимости нормального алгоритма к слову в А означает отсутствие общего метода, который для любого алгоритма и любого слова в А мог бы дать интересующий нас ответ. Ограничивая класс алгоритмов -или класс обследуемых слов, или и то и другое, можно в некоторых случаях получить разрешимые массовые проблемы.
Не значит ли это, что неразрешимость связана с тем, что исследуемая проблема является «слишком массовой»? Нет, не значит, потому что, вводя ограничения на алгоритмы или на слова, или и на то и другое, можно все множество одиночных проблем, входящих в состав массовой проблемы, оставить бесконечным (счетным), имеющим то же кардинальное число, что и исходное множество, но тем не менее получить разрешимую проблему. В некоторых случаях множество одиночных проблем неразрешимой проблемы оказывается подмножеством аналогичного множества одиночных проблем, образующих разрешимую проблему.
Заметим еще, что неразрешимость проблемы применимости нормальных алгоритмов легко переносится на любой другой достаточно четко описанный класс алгоритмов, если только для алгоритмов этого класса можно придумать такой способ кодирования, при котором коды алгоритмов оказывались бы допустимыми исходными данными для таких алгоритмов.
В частности, для машин Тьюринга неразрешимость проблемы распознавания их применимости к словам в А выражалось бы следующей теоремой:
Невозможна машина Тьюринга с внешним алфавитом А, распознающая применимость произвольной машины Тьюринга с внешним алфавитом А к произвольному слову в А (при условии, что А содержит не менее двух букв).
Некоторые замечания
В этой главе читатель ознакомился с рядом неразрешимых проблем. Примеры были связаны с несуществующими (парадоксальными) объектами. При этом идея доказательства неразрешимости заключалась в обосновании того, что из факта разрешимости должно вытекать существование невозможного объекта. Можно было бы и еще указать большое число неразрешимых проблем. Мы остановились на нескольких, исследование которых особенно просто.
Из широко известных неразрешимых проблем укажем 10-ю проблему Гильберта, выдвинутую им в числе других в 1901 г. на Международном математическом конгрессе в Париже. Она гласит: найти алгоритм, определяющий для любого диофантова уравнения, имеет ли оно целочисленное решение. Диофантово уравнение обычно пишут в виде
F(x, y, ...)=0,
где F(х, у, ...) — многочлен с целыми показателями степеней и целыми коэффициентами.
Для частного случая диофантова уравнения
anxn+an-1xn-1+…+a1x+a0=0
проблема решена. Известно, что всякий целый корень такого уравнения является делителем числа а0. Искомый алгоритм поэтому заключается в разложении а0 на простые множители, построении всех делителей числа а0 и последовательной проверке каждого делителя подстановкой его в левую часть. При этом все Целые решения будут найдены.
В общем случае 10-я проблема Гильберта долго оставалась нерешенной и только в 1970 г. ленинградский математик Ю. В. Матиясевич доказал неразрешимость ее.
Есть некоторые проблемы, которые уже много лет привлекают внимание математиков, но до сих пор остались нерешенными. Одна из них — проблема Гольдбаха, уже упомянутая в § 8 гл. 2, другая — известная великая теорема Ферма. Последняя формулируется так: нет таких целых положительных чисел а, b, с, п (п>2), для которых справедливо равенство
an+bn=cn.
Эта теорема доказана для многих значений п и проверена для ряда частных случаев. Все проверки ее подтверждают. Тем не менее общего доказательства до сих пор нет.
Хоть и очень коротко, но все же кое-что мы рассказали читателю об исследовании разрешимости проблем. Второе приложение традиционных теорий алгоритмов — обоснование математики — осталось непроиллюстрированным. Ни объем, ни характер книги не позволяют этого сделать.
Заметим только, что вполне правомерна точка зрения на дедуктивный метод (см. гл. 3, §1), согласно которой он является не более чем техническим приемом, позволяющим систематизировать и компактно описать большое число эмпирических фактов. Сущность этого приема можно видеть в том, чтопровозглашается некоторое число утверждений (их обычно называют аксиомами), от которых не требуется никакой истинности или интуитивной ясности и некоторое количество правил вывода, с помощью которых из аксиом можно выводить новые утверждения, называемые теоремами. Совокупность указанных правил вывода представляет собой логику данной дедуктивной теории.
Аксиомы и правила вывода должны быть подобраны так чтобы обеспечивать возможность получения всех утверждений, провозглашающих указанные выше эмпирические факты с допустимой степенью точности. Такие утверждения являются истинными. То обстоятельство, что в качестве некоторых аксиом были взяты утверждения, отражающие эмпирические факты, а в качестве правил вывода — законы формальной логики, обусловлено историческими причинами.
Очевидно кроме истинных утверждении с помощью описанного приема в принципе возможно получение и ложных и таких, о которых не известно, истинны они или ложны. Некоторые из последних могут быть проверены и приняты (научный прогноз) или отвергнуты. Другие могут быть принципиально непроверяемыми, хотя возможно что из них вытекают проверяемые и даже истинные.
При описанном кодходе к дедуктивному методу вопрос об основаниях математики приобретает совершенно новый смысл. Проблема «с головы ставится на ноги». Основанием дедуктивной теории оказывается не система аксиом и не логика теории а совокупность эмпирических фактов, которую эта теория описывает. Возможность противоречий теряет свой фатальный характер, но возникает вопрос об определении границ, в которых теория не содержит противоречий и не содержит ложных проверяемых утверждений Одна и та же совокупность эмпирических фактов может быть описана различными дедуктивными теориями. Расширение совокупности эмпирических фактов может приводить к необходимости изменения системы аксиом или системы правил вывода, или и того и другого.
Аргументом в пользу описанного понимания дедуктивного метода является присутствие пятой аксиомы в системе аксиом Евклида[16], которая, конечно, не могла казаться Евклиду очевидной истиной, но была удобна при доказательстве таких теорем, легко подтверждающихся на практике, как утверждение о равенстве суммы внутренних углов треугольника двум прямым (углам). Оценивая все ранее упомянутые попытки обоснования математики с последней точки зрения, можно прийти к выводу об их безнадежности.
Одновременно нужно признать, что все течения, возникшие в математике после обнаружения антиномий в теории множеств, что-то дали новое математике в целом, чем-то способствовали формированию ее идей.
Глава 6