Пусть задано диофантово уравнение с произвольными неизвестными и целыми рациональными числовыми коэффициентами. Указать способ, при помощи которого возможно после конечного числа операций установить, разрешимо ли это уравнение в целых рациональных числах.
Диофантовы уравнения (названы в память греческого математика Диофанта, жившего в III в. н. э.) имеют вид
Р(х1,х2, …. хn) = Q(x1,x2, …. хn), где Р и Q — полиномы, например:
aх2 + bх + с = у2; ахn+ byn = czn; ax3 + bx2y + сху2 + dy3 = 1.
где коэффициенты а, b, с и степень п — целые числа; решения — значения х, у, z — также должны быть целыми числами.
Конечно, решения не всегда существуют: вспомним хотя бы известную теорему Ферма о том, что уравнение хn + уn = zn, п > 2, не имеет целочисленных решений. Теорема была сформулирована Пьером де Ферма в середине XVII в. без доказательства и доказана Э. Уайлсом в 1995 г.
Если вспомнить высказывания Гильберта в начале доклада, то можно предположить, что он считал «способ» существующим, который рано или поздно будет найден. Точного понятия алгоритма в то время еще не существовало, но в современной терминологии десятую проблему можно сформулировать так: «Построить алгоритм, который получает на входе строку символов — запись уравнения с конкретными целочисленными коэффициентами и показателями степени — и выдает ответ «ДА», если решение уравнения существует, или «НЕТ», если уравнение не имеет решения». При этом сам алгоритм — универсален, т. е. его текст не зависит от конкретных входных данных (обычное свойство массовости алгоритма).
Для машин Тьюринга был задан вопрос: Всякий ли неформально описанный алгоритм может быть реализован некоторой машиной Тьюринга? Ответом был тезис Тьюринга. Аналогичный вопрос может быть задан в отношении частично рекурсивной функции. Ответом был тезис Черча, который показал связь рекурсивных функций с машинами Тьюринга. Следует заметить, что исторически тезис Черча был сформулирован раньше тезиса Тьюринга.
Понятие частично-рекурсивной функции оказалось исчерпывающей формализацией понятия вычислимой функции. Это обстоятельство выражено в виде тезиса Черна, являющегося аналогом 1 тезиса Тьюринга для рекурсивных функций: всякая функция, вычислимая некоторым алгоритмом, частично-рекурсивна.
Из сопоставления двух тезисов вытекает утверждение: финкция вычислима машиной Тьюринга тогда и только тогда когда она частично-рекурсивна. Это утверждение об эквивалентности двух алгоритмических моделей является (в отличие от тезисов) вполне точным математическим утверждением и, следовательно, должно быть доказано. Дан доказательства разобьем его на две теоремы.
Теорема 1. Всякая частично-рекурсивная функция вычислима на машине Тьюринга.
План доказательства ясен: сначала доказывается, что простейшие функции вычислимы (это довольно очевидно), а затем это операторы суперпозиции, примитивной рекурсии и m-оператор сохраняют вычислимость.
Теорема 2 Всякая функция, вычислимая на машине Тьюринга, частично рекурсивна.
Итак, всякий алгоритм, описанный в терминах частично-рекурсивных функций, можно реализовать машиной Тьюринга, и наоборот. Отсюда следует, что любые утверждения о существовании или несуществовании алгоритмов, сделанные в одной из этих теорий, верны и в другой. В сочетании с тезисом Черча—Тьюринга это означает, что такие, утверждения можно формулировать для алгоритмов вообще, не фиксируя конкретную модель и используя результаты обеих теорий. Таким образом, возможно изложение теории алгоритмов, инвариантное по отношению к способу формализации понятия «алгоритм», — при любой формализации основные свойства алгоритмов остаются теми же самыми. Основные понятия такой инвариантной теории (будем называть ее общей теорией алгоритмов)—это алгоритм (рекурсивное описание функции, система команд машины Тьюринга или описание в какой-либо другой модели; считается, что выбрана какая-то модель, но какая именно — неважно) и вычислимая функция. Функция называется вычислимой, если существует вычисляющий ее алгоритм. При этом несущественно, числовая функция это или нет. Термин «общерекурсивная функция», употребленный в инвариантном смысле, является синонимом термина 0«всюду определенная вычислимая функция».
Эквивалентность утверждений «функция f вычислима» и «существует алгоритм, вычисляющий функцию f» иногда приводит к смешению понятий алгоритма и вычислимой функции; в частности, говоря о рекурсивной функции, часто имеют в виду ее конкретное рекурсивное описание. В действительности же различие между вычислимой функцией и алгоритмом — это различие между функцией и способом ее задания. Без соблюдения этих различий невозможна корректная интерпретация некоторых важных результатов теории алгоритмов. В то же время традиция изложения теории алгоритмов позволяет не различать понятия алгоритма и функции в тех случаях, когда-то не приводит к путанице.
Если нам не удается найти решение математической проблемы, то часто причина этого заключается в том, что мы не овладели еще достаточно общей точкой зрения, с которой рассматриваемая проблема представляется лишь отдельным звеном в цепи родственных проблем. Отыскав эту точку зрения, мы часто не только делаем более доступной для исследования данную проблему, но и овладеваем методом, применимым и к родственным проблемам<… >
Этот удивительный факт наряду с другими философскими основаниями создает у нас уверенность, которую разделяет, несомненно, каждый математик, но которую до сих пор никто не подтвердил доказательствами, — уверенность в том, что каждая определенная математическая проблема непременно должна быть доступна строгому решению или в том смысле, что удается получить ответ на поставленный вопрос, или же в том смысле, что будет установлена невозможность ее решения и вместе с тем доказана неизбежность неудачи всех попыток ее решить<…>
Является ли эта аксиома разрешимости каждой данной проблемы характерной особенностью только математического мышления или, быть может, имеет место общий, относящийся к внутренней сущности нашего разума закон, по которому все вопросы, которые он ставит, способны быть им разрешимы? Встречаются ведь в других областях знания старые проблемы, которые были самым удовлетворительным образом и к величайшей пользе науки разрешены путем доказательства невозможности их решения. Я вспоминаю проблему о perpetuum mobile (вечный двигатель). После напрасных попыток конструирования вечного двигателя стали, наоборот, исследовать соотношения, которые должны существовать между силами природы в предположении, что perpetuum mobile невозможно. И эта постановка обратной задачи привела к открытию закона сохранения энергии, из которой и вытекает невозможность perpetuum mobile в первоначальном понимании его смысла.
Люди придумали множество алгоритмов для решения разнообразных проблем. Существуют ли проблемы, для которых алгоритмов найти нельзя? Мы говорили раньше о существовании алгоритмически неразрушимых проблем, т.е. проблем, для которых нет алгоритмов их решения.
Утверждение это весьма сильное. Оно означает не только то, что мы не знаем сейчас соответствующего алгоритма, оно говорит о том, что такого алгоритма мы никогда найти не сможем. Долгое время математики считали, что для любой четко сформулированной проблемы алгоритм найти можно. Например, Д. Гильберт считал, что в математике не может быть неразрешимых проблем: «In mathematics there is nothing which cannot be known». Его целью в начале XX века было представить математику в виде такой формальной системы, что в ней все проблемы могли бы быть сформулированы в виде утверждений, которые либо истинны, либо ложны, а также найти алгоритм, который по заданному утверждению в этой системе мог бы определить его истинность. Гильберт рассматривал эту проблему как фундаментальную открытую проблему математики.
Впервые Курт Гедель в 1931 году представил строго сформулированную математическую проблему, для которой не существует решающего ее алгоритма. Сам по себе этот факт является удивительным, однако он имеет также большое практическое значение. Для проблем, алгоритмическая неразрешимость которых доказана, бессмысленно искать методы их решения точно так же, как бессмысленны поиски вечного двигателя. Оказалось, что таких алгоритмически неразрешимых проблем много, например, не существует алгоритма проверки общезначимости логической формулы в логике предикатов. Мы сейчас сформулируем одну из таких проблем и докажем ее алгоритмическую неразрешимость. Эта проблема известна как «проблема останова». Она состоит в том, что не существует алгоритма, позволяющего по описанию произвольного алгоритма и его исходных данных определить, останавливается ли этот алгоритм на этих данных или работает бесконечно.