197

Эту гипотезу называют основной гипотезой, или основным тезисом теории алгоритмов, или принципом нормализации, или тезисом Черча.

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

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

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

Никогда не бывает больших дел без больших трудностей.

Ф. Вольтер

§ 12. Проблема алгоритмической неразрешимости

Под массовой проблемой будем понимать бесконечное множество однотипных задач. Массовую проблему можно обозначать, например, через {aj}, где aj - некоторая единичная задача.

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

Массовая проблема {aj} называется алгоритмически разрешимой, если существует алгоритм (нормальный алгоритм или алгоритм Тьюринга) позволяющий решить каждую задачу этой массовой проблемы и алгоритмически неразрешимой, если такого алгоритма не существует.

Проблема алгоритмической (не)разрешимости формулируется следующим образом: «каждая ли массовая проблема является алгоритмически разрешимой?»

198

Эта проблема имеет свою историю. Еще великий математик и философ Лейбниц (1646-1716) мечтал о создании всеобщего метода, позволяющего решать любую задачу. Хотя всеобщего алгоритма ему не удалось найти, Лейбниц считал, что наступит время, когда такой алгоритм будет найден. Несмотря на долгие и упорные усилия многих крупных специалистов, трудности остались непреодолимыми. Более того, были обнаружены большие трудности даже при попытке создания алгоритмов для некоторых массовых проблем частного вида (не говоря уже о любой задаче). В результате многочисленных, но безрезультатных попыток создания таких алгоритмов стало ясно, что налицо имеются трудности принципиального характера, и возникло сомнение, для каждого ли класса задач возможно построение решающего алгоритма. Оказалось, что для целого ряда массовых проблем невозможно построить разрешающего алгоритма, т.е. алгоритма, который позволил бы решить все задачи данной массовой проблемы. Первые результаты такого рода были обнаружены в математической логике в работах Геделя, Черча, Тьюринга. Ими были указаны (найдены) примеры алгоритмически неразрешимых массовых проблем.

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

К алгоритмически разрешимым массовым проблемам относятся, например, следующие:

-сложение двух и более заданных чисел; -решение в радикалах уравнений от одной переменной не выше

четвертой степени;

-решение систем линейных уравнений с n неизвестными; -и т.д.

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

Рассмотрим, например, полиномы, зависящие от произвольного числа переменных х1,х2,...,хn с целыми коэффициентами. Такие полиномы называют диофантовыми в память греческого математика Диофанта, рассмотревшего некоторые из таких полиномов. Будем интересоваться, есть ли у такого полинома целочисленные корни (диофантовы корни). Целочисленными решениями полиномов интересовались еще античные математики, например, в связи с теоремой Пифагора они рассматривали уравнение х2+у2=z2. Евклид приводит формулы, позволяющие найти все целочисленные решения этого уравнения. Сам Диофант (Ш в. н.э.) среди многих других уравнений, рассмотрел уравнение ax2+bx+c=y2 и решил его для некоторых частных случаев.

199

Вэпоху развития анализа диофантовы уравнения привлекали внимание

выдающихся ученых, таких как Ферма, Эйлер, Лагранж, Гаусс. В частности, Ферма выдвинул знаменитую гипотезу о том, что уравнение xn+yn=zn при n>2 не имеет целочисленных решений (большая теорема Ферма).

На рубеже Х1Х-ХХ вв. Гильберт включил проблему диофантовых уравнений в число наиболее важных проблем, которые Х1Х век оставил ХХ. Эта проблема была сформулирована им так [27]: "Пусть задано произвольное диофантовое уравнение с произвольными неизвестными и целыми рациональными числовыми коэффициентами. Указать способ, при помощи которого возможно после конечного числа операций установить, разрешимо ли это уравнение в целых рациональных числах". Эта проблема называется

10-й проблемой Гильберта.

В1970 году советским математиком Ю.В. Матиясевичем, а несколько позже Г.В.Чудновским было доказано, что эта проблема алгоритмически неразрешима, т.е. алгоритм, который искали, не существует.

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

§13. Примеры алгоритмически неразрешимых массовых проблем

Впредыдущем параграфе уже рассмотрена одна из алгоритмически неразрешимых массовых проблем - 10-я проблема Гильберта. Рассмотрим еще несколько таких примеров.

1. Проблема распознавания применимости. Пусть задан нормальный алгоритм A и слово Р. Возможны два случая:

1) Алгоритм применим A к слову Р, т.е. процесс переработки слова Р конечен,

2) алгоритм A бесконечно перерабатывает слово Р, т.е. не применим к этому слову.

Следовательно, возникает задача аi: применим ли A к Р или нет. Учитывая, что нормальных алгоритмов A и слов Р может быть бесчисленное

множество, получаем массовую проблему {ai} - проблему распознавания применимости произвольного нормального алгоритма к произвольному слову.

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

200

Теорема 6.7. Не существует нормального алгоритма B, позволяющего решить все задачи массовой проблемы {ai}. Иначе: не существует нормального алгоритма B, который позволил бы выяснить, применим или нет произвольный нормальный алгоритм A к произвольному слову Р.

Теорему примем без доказательства.

2.Проблема эквивалентности слов. Пусть А - некоторый алфавит, Р и Q

слова в этом алфавите, Р→Q - ориентированная подстановка, т.е. когда вместо слова Р подставляется слово Q; P−Q - неориентированная подстановка, т.е. можно подставить либо вместо Р слово Q, либо наоборот, вместо Q слово Р. Из бесчисленного множества возможных подстановок в алфавите А задают некоторое конечное множество подстановок указанных видов и называют их допустимыми подстановками.

Два слова R и S в алфавите А называются эквивалентными, если

существует конечная последовательность слов R1,R2,...,Rn (R1=R, Rn=S) такая, что Ri+1 получается из Ri в результате одной допустимой подстановки.

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

3.Проблема представимости матриц. Пусть U1,U2,...,Uq - матрицы

порядка n×n. Будем говорить о матрице U того же порядка, что она представима через U1,U2,...,Uq, если для некоторого целого положительного t и целых чисел r1,r2,...rt из ряда 1,2,...,q имеет место равенство

U=Ur1*Ur2*...*Urt.

Общая проблема представимости матриц. Дано целое положительное число n, требуется выяснить, существует ли алгоритм, посредством которого можно было бы узнавать для любой системы матриц U,U1,U2,...,Uq порядка n×n, представима ли матрица U через матрицы U1,U2,...,Uq.

Частная проблема представимости матриц. Даны матрицы U1,U2,...,Uq

порядка n×n, Требуется выяснить, существует ли алгоритм, посредством которого можно было бы узнавать для любой матрицы U того же порядка, представима ли она через U1,U2,...,Uq.

А. А. Марков построил систему из 102 матриц 6-го порядка, для которой доказал алгоритмическую неразрешимость частной проблемы представимости, откуда сразу следует алгоритмическая неразрешимость и общей проблемы представимости матриц для n≥6 (позже было доказано для n≥4).

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

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