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

Вернемся на время к нормальным алгоритмам. Мы пом­ним, что запись нормального алгоритма в алфавите А содержит, кроме букв в А, еще две буквы: «→» и «→•».Введем временно еще одну букву, не одинаковую ни с од­ной из указанных двух букв и не являющуюся буквой

в А.

Пусть это будет для определенности л. Запись нормаль­ного алгоритма можно превратить в слово, выписывая его формулы одну за другой и разделяя их буквами 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(х, у,...) — многочлен с целыми показателями сте­пеней и целыми коэффициентами.

Для частного случая диофантова уравнения

a_nxⁿ + a_n-1x^n-1 +…+ a₁x + a₀ =0

проблема решена. Известно, что всякий целый корень та­кого уравнения является делителем числа а₀. Искомый ал­горитм поэтому заключается в разложении а₀ на простые множители, построении всех делителей числа а₀ и последо­вательной проверке каждого делителя подстановкой его в левую часть. При этом все Целые решения будут найдены.

В общем случае 10-я проблема Гильберта долго остава­лась нерешенной и только в 1970 г. ленинградский матема­тик Ю. В. Матиясевич доказал неразрешимость ее.

Есть некоторые проблемы, которые уже много лет при­влекают внимание математиков, но до сих пор остались не­решенными. Одна из них — проблема Гольдбаха, уже упо­мянутая в § 8 гл. 2, другая — известная великая теорема Ферма. Последняя формулируется так: нет таких целых положительных чисел а, b, с, п (п >2), для которых спра­ведливо равенство

aⁿ + bⁿ = cⁿ.

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

Хоть и очень коротко, но все же кое-что мы рассказали читателю об исследовании разрешимости проблем. Второе приложение традиционных теорий алгоритмов — обосно­вание математики — осталось непроиллюстрированным. Ни объем, ни характер книги не позволяют этого сделать.

Заметим только, что вполне правомерна точка зрения на дедуктивный метод (см. гл. 3, §1), согласно которой он является не более чем техническим приемом, позволяю­щим систематизировать и компактно описать большое число эмпирических фактов. Сущность этого приема можно видеть в том, чтопровозглашается некоторое число ут­верждений (их обычно называют аксиомами), от которых не требуется никакой истинности или интуитивной яс­ности и некоторое количество правил вывода, с помощью которых из аксиом можно выводить новые утверждения, называемые теоремами. Совокупность указанных правил вывода представляет собой логику данной дедуктивной теории.

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

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

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

Аргументом в пользу описанного понимания дедуктив­ного метода является присутствие пятой аксиомы в системе аксиом Евклида[16], которая, конечно, не могла казаться Евклиду очевидной истиной, но была удобна при доказа­тельстве таких теорем, легко подтверждающихся на прак­тике, как утверждение о равенстве суммы внутренних углов треугольника двум прямым (углам). Оценивая все ранее упомянутые попытки обоснования математики с по­следней точки зрения, можно прийти к выводу об их без­надежности.

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

Глава 6