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

Квант 1985, №7 с. 9-15 Тег 01S7

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

Профессор
В. А. УСПЕНСКИЙ,
доктор физико-математических наук
А. Л. СЕМЕНОВ

Алгоритмы

Все мы умеем складывать многоозначные числа — этоу учат в детстве. Давайте задаемся, в чем состоит нашей учение? Когда в пьесе Э. Ионеско «Урок» ученица демонстрирует заменательные способности к переменной десятизначных чисел, потрясенный учитель узнал, что ее способ очень прост — она выучила (беско нечную!) таблицу умножения всех чисел. По-видимому, наш способ — иного рода. Мы знаем единый конечный способ, позволяющий решать бесконечное множество задач. В нашем случае бесконечное множество образуют задачи о нахождения суммы: для каждой пары чисел — свой задача. Способ единый, поскольку он один и тот же для всех задач. Способ конечный в том смысле, что он может быть изложен конечным числом слов (а если бы это было не так, то ведь этому способу нельзя было бы и научить!). Как известно, способ этот называется «сложение столбиком» и состоит в том, что одно число (например, 8257) подписывается сизу под другим (например, 64) с выражением правого края (то есть так: 64/8357, а не, скажем, так: 64/8357) и далее начинается последовательное применение таблицы сложения однозначных чисел (которую нужно заранее вычитать) с переносом, где надо, в следующий разряд. В результате этого постелено будет формуровано число 8421.

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

проблему сложения чисел. Эту и другие проблемы построения алгоритмов мы будем далее формулировать, указая, что от алгоритма требуется, примерно в таком виде:

Проблема. Дано: два произвольных натуральных числа. Требуется: найти их сумму.

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

В этой статье под алгоритм мы будем понимать всякую конечную систему правил, которая задает вычислительной процедусе. Этот процесс начинается с предъявления (подачи на вход алгоритма) произвольного (но выбранного из фиксированной для данного алгоритма совокупности) исходного данного. Процесс может завершиться получением полностоящего определенного этим исходным данным результата; тогда говорят, что результат обращается на выход алгоритма. Однако процесс может продолжаться и неограниченно, у алгоритма результат существует не всегда. Например, алгоритм, вычисывающий частное двух чисел в виде десятичной дроби, может никакого не кончит работать (так 1:3=0,33333…).

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

Замечательен сам термин «alгоритм». В самом деле, много ли терминов науки, в состав которых входит географическое название? Подобное навание не сразу разгладишь в слое «alгоритм», однako оно там есть — это навание города «Хорезм». Ведь в основе термин «alгоритм» лежит имя аль Хорезми (что значит «из Хорезма») — велико математика IX века. Крупнейшие математики и алгоритмы всего мира воздали дан основополагающей роли аль Хорезми, съехавшись в сентябре 1979 года в Хорезмскую область Узбекистана, в город Ургенч, где они обсулились вопросы теории алгоритмов и ее приложений на современном этапе. Подобное об этой встрече в Ургенч расссказал один из ее организаторов, академик А. П. Erшов (см. «Квант», 1984, № 8, c. 29).

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

Решение алгебраических уравнений

Выпишем уравнение

$x^2 + 2 = y^3$

(1)

и будем интересовать его решениями. Решение в данной случае — это пара чисел (a; b), подчиненная условию $a^2 + 2 = b^3$ , например, пара (5; 3).

Решая какое-либо уравнение, надо всегда точно знать, какие числа дозволяет быть в качестве его решения. Если, к примеру, решения уравнения должны служить прирост количества коз в таком-то стаде за такой-то срок, вред ли нас устроит ответ «две трети» (но ответ «минус десять» будет осмыслен: он означает, что количество коз в стаде, к сожалению, не возросло, а уменьшилось). Для уравнения (1) можно интересовать его действительными решениями, то есть парамети действительных чисел, расположенными решениями, то есть парамети расположенных чисел, целыми решениями, то есть парамети целых чисел. Уравнение (1) имеет бесконечно много действительных решения: достаточно взять любое a и положить b = $\sqrt[3]{a^2 + 2}$ , тогда пара (a; b) будет решения (вопрос к читателю: можно ли взять любое b и положить a = $\sqrt{b^3 - 2}$ ?). Нетрудно доказать, что (1) имеет бесконечно много расположенных решения; вот одно из них: (0,383; 0,129). Цельх же решения только два: (5; 3) и (−5; 3). Однако доказать это не легко.

Решение уравнения в целых числах представляется собой очень древнюю (его занимается еще сам Пифогор в VI. в до н. э.) и — в общем случае — очень трудную задачу. Основная трудность состоит в том, чтобы выяснить, имеет ли данное уравнение хотя бы одно целочисленное решение. Например, неизвестно (во всяком случае было неизвестно до срав-

нительно недавнего времени) имеют ли решения в целях числа уравнения $x^3+y^3+z^3=30$ и $x^4+y^4+z^4=u^4$ .

Задача для читателя. Для каждого из уравнений $x^4+y^4=5z^2$ , $3x^2-y^2=1$ , $x^2+y^3=z^4$ найдите какое-нибудь решение в целях числа или доказите, что такое решение не существует.

Указание. Об этих и других уравнений в целях числа можно прочесть в популяриных брошюрах: Гельфонд А. О. «Решение уравнений в целях числа», М., 1952. (серия «Популяриные лекции по математике», вып. 8); Серпиский В. «О решении уравнений в целях числа», М., 1961.

Задача «уметь по произвольному алгебраическому уравнению с цельми коэффициентами выяснять, имеет ли оно решение в целях числа» составляется одну из двадцати трех называемых «проблем Гильберта». Что это проблема?

Когда Давид Гильберт (1862—1943), один из величайших математikов XX века, готовил свой доклад на Всемирном математическом конгрессе в Париже в 1900 г., он выбрал 23 пробемы из различных области математики. Эти пробемы были его попыткой «проникнуть в предстоящие условия нашей науки и тайны ее развития в начинащем состоянии». Попытка эта оказалась необсячайно успешной и ценной. И по сея день решения (далее частное) какой-либо пробемы Гильберта расценвается во всем мире как высшее математическое достижение. Обязательным требованием, предъявляемым к действительному фундаментальной пробке, Гильберт считал «возможность изложить ее содержание первогому встречному». Задача о выясении наличия целочисленных решений составляется десятию пробему из списка Гильберта. Читатель может сам судить, в какой степени ее формулировка является общественно. Сейчас мы сформируем десятию пробему Гильберта в соответствии с принятыми здесь стандартами.

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

Искомый алгоритм: в 1970 г. советский математик Ю. В. Матиясевич доказал невозможность алгоритма, решающего эту пробему (см. «Квант», 1970, № 7, с. 39).

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

Приведем несколько естественных модификаций первой пробемы.

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

Искомый алгоритм: существует!

Решение пробемы 2 было получено известным пользователем Альфредом Тарским в 40-e года XX века. О применении этого результата будет говорить далее. В действительности, Тарский построил более общий алгоритм, позволяющий выяснить наличие решения у систем равенств и неравенств.

Чтобы оценить степень нетривиальности алгоритма Тарского, попытаться решить следующую задачу. По произвольному алгебраическому уравнению с цельми коэффициентами и одной неизвестной требуется выяснить, существует ли у него решение в действительных числах. (Ясно, что эта задача — простой частный случай пробемы 2). Если степень уравнения нечетна, сразу можно ответить, что корень уравнения существует. А что, если чета?

Проблема 3. Дано: произвольное алгебраическое уравнение с цельми коэффициентами. Требуется: выяснить, существует ли у данного уравнения решения в рациональных числах.

Искомый алгоритм: существует или нет — неизвестно.

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

Преобразование слов

В математике словами называются любые конечные последовательности символов. Например, 1985 — слово длины 4. Слова не только не обязаны обладать каким-либо смыслом, но даже быть произносимыми. Так, БРДРОБЬШ — слово из русских букв (и притом длины 8), хотя и не слово русского языка. Как правило, исходные данные для алгоритмов — это слова. Когда алгоритм задан, определяено и множество букв, то есть символов, из которых составляют слова, подаваемые ему на вход. Такое множество называется алфавитом. Алфавиты, в которых пишутся тексты на естественных языках и языках программирования, печатаются книги, содержат не более несколько сот букв. Многозначные числа, участвующие в «школьных» алгоритмах — это слова в десятибуквенном алфавите, состоящем из букв 0, 1, 2, …, 9; эти буквы, как известно, называются цифрами; а для записи десятичных дробей, помимо этих десяти цифр, используются еще одна буква — запятая.

Современные вычислительные машины работают с двойными словами, состоящими из букв 0 и 1. Чтобы проиллюстрировать гибкость и эмкость понятия «слово», заметим, что пару слов можно закодировать одним словом, например, поставив между членами пары букву, не входящую в алфавит, в котором эти члены записаны. Таким образом, в качестве исходных данных для алгоритмов достаточно расматривать слова, а расматривать в этом качестве пары, тройки и т. д. слов нет нужны. Заметим еще, что часто бывают удобно расматривать слова длины полы; оно называется пустым словом, так как вовсе не содержит букв.

Многие из вас играли в следующую игру. Дается задание, например, «передать волка в козу». Решение:

В чем состоит один шаг переделки? — В замене любой буквы уже полученного слова на любую другую букву русского алфавита, причем так, чтобы получаемый объект (слово в математическом смысле этого слова) оказался слова осмысленным словом русского языка.

Тепер упростим игра — забудем о том, что среди всех последовательностей буквы выделены слова русского языка. Будем считать все (в математическом понимании, то есть как осмысленные, так и бессмысленные) слова в русском алфавите равноправными. Можно ли тогда переделать волка в козу? Ну, теперь это совсем легко:

ВОЛК→КОЛК→КОЗК→КОЗА

Может быть, теперь любое слово можно переделать в любое? Конечно нет — слова должны быть одинаковой длины. Но этого условия и достаточно!

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

Искомый алгоритм: сравнить длины слов, если они совпадают, то ответ ДА, если не совпадают, то ответ НЕТ.

Заметим, что первоначальная проблема — переделать одно заданное слово русского языка, также очень редко только имеет (конечный!) словарь всех слов русского языка, которые можно использовать в игре, и достаточно запас времени и бумаги. Несложный подчет показывает, что эта задача может быть практическими решения на сегодняших ЭВМ.

Тепер, опять забив о русском языке (но не о русском алфавите) и под словами понятия произвольные конечные последовательности русских букв, условия задачи полы; оно называется пустым словом, так как вовсе не содержит букв.

Преобразование слова за один шаг будет, как и раньше, состоять в том, что в любом месте слова мы заменаем участок, который разрешено заменять, на то, на что его разрешено заменять. При этом все разрешенные замены двусторонние: если участок X разрешено заменять на участок Y, то и участок Y разрешено заменять на участок X. Например, если спи-

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

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

АВ BB AY BY DBA DYB BВА
ВА BB YA YB BD YD BВА

Искомый алгоритм: не существует. Это доказал советский математик Г. С. Цейтин, придумавший указанную систему замен.

Подобную проблему в общем виде (то есть любой системы разрешенных замен) впервые поставил известный норвежский математик Аксель Туэв в 1914 году. Сам он доказал существование алгоритма в ряде частных случаев.

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

АВ
пустое слово
ВА
пустое слово

(Уже этот простейший пример важен для раздела алгебры, называемого «теория групп».)

Для любого набора разрешенных вставок-вышеркивания алгоритм, установливающий, можно ли передать одно слово в другое, существует. Показал это советский математик С. И. Адян в 1966 году.

Элементарная геометрия

Мы не имеем здесь возможность дать детальное определение, что такое элементарная геометрия в строом смысле, уточняемом с помощью математической логики. Постараемся, однako, дать приближательное описание. Исходными понятями элементарной геометрии служат точки, прямые, плоскости, отрезки, окружности, сферы, отношения «лежать на», «лежать между», «быть конгрузными» и т.п. Допускается образование новых понятений — но без использования многооточий и оборота «и так далее» (в этом пункте строое математiko-logичское представление об элементарной геометрии расходится с распливчатым традиционным). Например, понятие треугольника принадлежит элементарной геометрии: ведь треугольник можно определить как такие три отрезка $A_1A_2$ , $A_3A_4$ , $A_5A_6$ , что $A_2=A_3$ , $A_4=A_5$ , $A_6=A_1$ . А вот общее понятие ломаной не принадлежит элементарной геометрии, потому что в его определении участвует многооточие и слова «и так далее»: ломаная — это набор отрезков в $A_1A_2$ , $A_3A_4$ ,… (здесь многооточие!), $A_{n-1}$ , $A_n$ , таких, что $A_2=A_3$ , $A_4=A_5$ и т.д.

Проблема. Дано: утверждение элементарной геометрии. Требуется: проверить, истинно ли оно.

Искомый алгоритм: существует.

Существование алгоритма было, по существу, установлено Тарским в 40-e годы нашего века. Она достаточно просто вытекает из существования того алгоритма Тарского, о котором говорилось ранее. Связь проблем алгебры и геометрии была открыта уже давно (аналитическая геометрия), естественно, что она распространяется и на алгоритмические проблемы.

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

Полезно представить себе: насоклько «близко» начинаются те геометрические утверждения, для которых, несмотря на существование общого алго-

ритма, сейчас неизвестна их истинность или ложность.

Вот один наглядный пример. Возьмем движатель круглых банок одинакового диаметра (равного, скажем, 10 см). Мы хотим упаковать их, поставив стойям, в круглую коробку. Это можно сделать, например, так, как показано на рисунке 1). Однако можно расположить банки и более тесно — так, чтобы попадилась коробка меньше шиws размеров. Например так, как показано на рисунке 2. Наконец, упаковка, показанная на рисунке 3, позволяет использовать еще меньше коробку. Спрашивается, можно ли найти круглую коробку еще меньше диаметра, в котором бы впелезли все наши банки? Ответа на этот вопросник не знает, хотя этот ответ и может быть получен с помощью алгоритма Тарского: надо применить этот алгоритм к утверждению, что третья упаковка — наилучшая, и посмотреть, что получится в результате. ДА или НЕТ. Однако этот способ не реализен, поскольку для получения результат работы алгоритма требуется астрономически большее время.

Пример доказательства нерешимости

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

Программы можно переумеровать (например, в алфавитном порядке, ведь каждую программу можно считать словом в символах Языка Программирования), составив Библиотеку в сех программи:

$p_1, p_2, p_3, \dots, p_n, \dots$

Лучше всего имеет дело с таким программами $p$ , которые при любом входном данном $m$ дают результат $p(m)$ . Такова, например, стандартная программа для вычисления функции $y=m^2+5m-6$ . К сожалению, встречаются и такие программы, которые при некоторых значениях входного данного никакого не заканчивают работы, «зацикливаются», как говорят программы. Так, программа для вычисления десятичной записки функции $y=m/3$ не дает результатата, скажем, при $m=10$ .

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

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

Проблема. Дано: произвольная пара натуральных чисел $(n, m)$ . Требуется: построить алгоритм, выяснойший, заканчивает ли работу $n$ -ная программа $p_n$ при входном данном $m$ .

Искомый алгоритм: не существует, и мы сейчас это доказем.

Доказательство. (Диазональ Кантopa). Предположим, что искомый алгоритм А существует. Составим таблицу всех программы и исходных данных:

Рассмотрим программу $\bar{p}$ , результат которого «не такой, как на диагонали», то есть определяемся правлим

$\bar{p}(m) = \begin{cases} p_m(m) + 1, & \text{ если } p_m(m) \text{ определено, } 0 \\ 0, & \text{ если } p_m(m) \text{ не определено.} \end{cases}$

Это действительное программа, то есть $p$ вычисляется с помощью алгоритма. (А именно, такого: проверяем условие $p_m(m)$ определено по алгоритму $A$ , если оно выполнено, вычисляем $p_m(m)$ и прибавляем единицу, если нет, полагаем $\bar{p}(m) = 0$ ). Но тогда $\bar{p}$ входит в списк всех программы Виблотекки, под каким-то номером. Обозначим этот номер через $k$ и рассмотрим $p_k(k)$ (элемент по диагонали!).

Если $p_k(k)$ не определено, то $\bar{p}(k) = 0$ и поэтому $\bar{p}(k) \neq p_k(k)$ .

Если $p_k(k)$ определено, то $\bar{p}(k) = p_k(k) + 1 \neq p_k(k)$ .

В обих случаях $\bar{p}(k) \neq p_k(k)$ , что невозможно, либо $\bar{p}$ и $p_k$ — одна и та же программа. Это противоречие завершает доказательство.

Читатель, возможно, хотел бы узнать, почему приведенное выше доказательство называется «диагонально» Кантора». Дело в том, что изящный метод доказательства, использованный здесь, был придуман немецким математиком Георгом Кантором (1845—1918), основателем теории множества. Правда, Кантор устанавливавал совсем другое утверждение. Именно, что множество действительных чисел нельзя запутовать натуральными числами, то есть составить списк всех действительных чисел: $a_1, a_2, a_3, \dots$ (Читатель, которое этот результат показался очень давно — «ведь действительных чисел городадо большие, чем натуральных», мы советем доказать, что все рациональные числа можно запутовать — хотя их тоже «горадство большие, чем натуральных»).

Следуя Кантору, мы доказем (от противного), что даже множество действительных чисел на отрезке [0,1] нельзя запутать. Предположим, что нам удалось это сделать. Расположим наши числа, предположим, число 0,abc где $a$ — любая цифра, отличная от $a_1$ ; $b$ — любая цифра, отличная от $b_2$ ; $c$ — любая цифра, отличная от $c_3$ , и т. д. Противоречие!

Давайте подведем некоторые итоги. Мы познакомились с понятием алгоритма — важнейшим понятием современной математики и информастики. Разумеется, многие конкретные алгоритмы (например, алгоритм сложения столбком или алгоритм Евклида нахождения общей меры) были известны очень давно, однако общее представление об алгоритме формировалось только в первой половине XX века. Всякая попытка использовать вычислительные машины для решения каких-либо задач начинается с построения алгоритма, решающего эти задачи. Пока нет такого алгоритма, нельзя составлять программу для вычислительной машины. А если оказывается, что нужно алгоритма и не может быть, то бессмысленно и пытается составлять программу. Поэтому результат о невозможности тех или иных алгоритмов имеет очень практический смысл. Кроме того, расуждения, приводящие к установлению такой невозможности, позволяют глубже проникнуть в природу самого понятия «alгоритм».

У читателя может возникнуть вопрос: всякий ли алгоритм можно запустить в программу для вычислительной машины? Ответ: теоретически — да. Слово «теоретически» означает здесь, что ответ утвердительен, если допускать программы сколь годно длины (для написания которых зависит не хватит бумаги, чернил и карнашей на всей Земле) и сколько угодно долго работыЩОе (триллюоны лет). Отметим, что подобного рода допущения глобоко коренятся в математике. (Мы допускаем многоугольники с любым числом сторон. Мы верим, что алгоритм сложения столбком позволяет числа любых размеров, хотя и осознаем, что если в слабаемых большие знаков, чемAtomов в Земном шаре, то не вплоне ясно, как такие слагаемые записать, да и число шаров при их сложении окажется астрономически велико…) К тому же и возможности вычислительной техники непрерывно растут. Если первые вычислительные машины совершили сотни операций в секунду, и управлялись программими, составленные десятиков команда, то быстроенные современных машин доходят до сотни миллионов операций в секунду, а размер их программи — до сотен тысяч команда. Приятно считать, что возможности машины удесяертиется за каждое пятилетие. Разумеется, тем не менее, оценки и размеры алгоритма и числа шаров его работы имеют первостепенно важность. Но это — тема отдельных серверных обсуждений.