16.2. Примечательные алгоритмически неразрешимые проблемы

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

1. Проблема распознавания истинности формул элементарной арифметики. Формулы строятся с помощью арифметических действий (сложения и умножения), логических операций (логических связок и кванторов) и знака равенства. Проблема состоит в том, чтобы найти алгоритм, который по любой такой формуле определяет, истинна она или нет на натуральном ряду. Неразрешимость этой проблемы установил Гедель К. (1931).

2. Проблема разрешения для логики предикатов первого порядка. Нужно найти алгоритм, который бы проверил общезначимость формулы алгебры предикатов. Неразрешимость этой проблемы установил Черч А. (1936).

3. Проблема сочетаемости Поста. Конечное множество V пар слов в некотором алфавите называется сочетаемым, если для некоторых пар (A₁, B₁), …, (A_s, B_s) из V выполнено равенство A₁…A_s = B₁…B_s. Нужно найти алгоритм, который по всякому множеству V пар слов узнает сочетаемо оно или нет. Неразрешимость данной проблемы установил Пост Э. (1946).

4. Проблема представимости матриц. Рассматриваются (nxn)-матрицы над кольцом целых чисел Z. Пусть даны произвольные матрицы U₁…U_q и U. Нужно иметь алгоритм, который бы решал, верно ли U =  для некоторых i₁, …, i_p. Неразрешимость данной проблемы, начиная с n = 4, установлена Марковым А.А. (1958).

5. Проблема тождества элементарных функций вещественного переменного. Определим класс термов Т индуктивно: x — переменная,  (число) — термы. Если u, v — термы, то (u + v), (uv), (u/v), sin u, |u| — термы. Нужно иметь алгоритм, который по любым двум термам из Т узнает, задают ли одну и ту же функцию одного вещественного переменного x. Неразрешимость данной проблемы установил Матиясевич Ю.В. (1973).

6. Проблема полноты автоматных базисов. Дан набор конечных автоматов (базис) с одним множеством входов и выходами, входящими в множество входов. Строятся схемы с помощью присоединения базисного автомата и введения обратной связи. Каждая схема реализует автомат. Если схемами в данном базисе может быть реализован любой автомат в данном алфавите, то базис называется полным, в противном случае — неполным. Проблема полноты заключается в том, чтобы узнавать по заданному базису — является он полным или нет. Неразрешимость данной проблемы установил Кратко М.И. (1966).

7. Десятая проблема Гильберта из 23 поставленным им в 1900 году формулируется так: «Пусть задано диофантово уравнение (т.е. уравнение вида p(x₁, …, x_n) = 0, р — многочлен) с произвольными неизвестными и целыми рациональными коэффициентами. Указать способ, при помощи которого возможно после конечного числа операций установить, разрешимо ли уравнение в целых рациональных числах.» Неразрешимость 10-й проблемы Гильберта установлена Матиясевичем Ю.В. (1970). Учитывая важность данного результата, приведем его точнее.

Пусть p(x₁, …, x_n, y₁, …, y_m) — многочлен над кольцом целых чисел Z. Тогда предикат М(x₁, …, x_n), задаваемый формулой М(x₁, …, x_n) = y₁…y_m(p(x₁, …, x_n, y₁, …, y_m) = 0), называется диофантовым предикатом (область определения кванторов — множество N₀). Легко убедиться, что диофантовы предикаты являются полувычислимыми. Матиясевич Ю.В. в 1970 году установил справедливость теоремы, гласящей, что каждый полувычислимый предикат диофантов.

Покажем теперь, как из этой теоремы следует неразрешимость десятой проблемы Гильберта. Заметим, что если 10-я проблема Гильберта разрешима, то разрешима и такая проблема: «установить, имеет ли произвольное полиномиальное уравнение p(x₁, …, x_n) = 0 с целыми коэффициентами решение в множестве натуральных чисел”. Действительно, любое натуральное число может быть представлено как сумма четырех квадратов (по теореме Лагранжа), поэтому, чтобы решать эту проблему достаточно найти целые решения уравнения

.

Возьмем теперь многочлен p(x, y₁, …, y_m) такой, что x  W_x  y₁…y_m(p(x, y₁, …, y_m) = 0), что можно сделать по теореме Матиясевича. Тогда, если бы существовала разрешающая процедура для 10-й проблемы Гильберта, то существовала бы и разрешающая процедура для проблемы «x  W_x»: чтобы проверить, верно ли а  W_а, нужно проверить, имеет ли решение в N₀ уравнение q(y₁, …, y_m) = p(a, y₁, …, y_m). Значит, неразрешимая проблема «x  W_x» сводится к проблеме Гильберта, что означает ее неразрешимость.

Укажем еще одно следствие теоремы Матиясевича.

Теорема 16.17. Всякое рекурсивно перечислимое множество является множеством неотрицательных значений, принимаемых некоторым многочленом p(x₁, …, x_n) над кольцом целых чисел Z (причем x₁, …, x_n  N₀).

Доказательство. Пусть А — рекурсивно перечислимое множество. По теореме Матиясевича существует многочлен q(x, y₁, …, y_m) такой, что x  A  y₁…y_m(q(x, y₁, …, y_m) = 0). Рассмотрим теперь многочлен p(x, y₁, …, y_m), определяемый формулой p(x, y₁, …, y_m) = x – (x + 1)(q(x, y₁, …, y_m))².

Ясно, что p(x, y₁, …, y_m)  0  q(x, y₁, …, y_m) = 0, причем в этом случае p(x, y₁, …, y_m) = x. Таким образом, А есть множество неотрицательных значений, принимаемых p(x, y₁, …, y_m), когда x, y₁, …, y_m пробегает множество N₀, что и требовалось доказать.

Одно из приложений этого результата — множество простых чисел. Ясно, что множество простых чисел — рекурсивно перечислимо. На основании доказанного множество простых чисел есть множество положительных значений, принимаемых некоторым многочленом с целыми коэффициентами. Данный факт считался ранее маловероятным и даже невозможным.

Л е к ц и я 17