О десятой проблеме Гильберта

На последнем заседании Президиума РАН с докладом об успехах решения диофантовых уравнений в 20 веке выступил академик Юрий Матиясевич.

Юрий Матиясевич (Санкт-Петербургское отделение Математического института им. В. А. Стеклова РАН) известен тем, что завершил доказательство алгоритмической неразрешимости задачи – десятой проблемы Гильберта. Выступая на заседании президиума РАН, он рассказал историю вопроса.

В 1900 году на Втором международном конгрессе математиков немецкий математик Давид Гильберт огласил список из 23 самых важных, по его мнению, нерешенных математических проблем, которые оказали значительное влияние на дальнейшее развитие математики. Проблема под номером десять касалась так называемых диофантовых уравнений, трудность решения которых состоит в ограничении на допустимые значения неизвестных, которые должны быть целыми положительными числами. Такое условие возникает как в чисто теоретических математических задачах, так и в прикладных. (Примером может служить расчет зубчатой передачи). Уравнения названы в честь греческого математика Диофанта, который жил в третьем веке нашей эры. К концу 19-го века, были найдены решения большого количества диофантовых уравнений, и было доказано, что многие из них решений не имеют. Однако дальнейшее их рассмотрение имело большое значение, поскольку для их решения математикам приходилось изобретать все новые и новые методы. В 10-ой проблеме Гильберт просил решить не конкретные диофантовы уравнения, а найти общий, универсальный метод (алгоритм), который будучи применен к конкретному диофантову уравнению, давал ответ на вопрос, имеет ли это уравнение решения или нет. Сегодня, благодаря усилиям математиков, известно, что 10-ая проблема Гильберта неразрешима – требуемого в ней алгоритма не существует. Однако общее понятие алгоритма было выработано только в 30-ые годы 20-го века в результате исследований Курта Гёделя, Алана Тьюринга, Алонзо Чёрча и других математических логиков. В наши дни алгоритм можно отождествить с программой на любом языке программирования. Таким образом, полученное "отрицательное решение" 10-ой проблемы Гильберта состояло в доказательстве невозможности написать программу, которая говорила бы нам, имеет ли то или иное уравнение решения или нет.

Какая же может быть польза от этого доказательства невозможности? Академик Матиясевич сравнил ситуацию с законом сохранения энергии, который делает невозможным построение "вечного двигателя", избавляя тем самым изобретателей от заведомо бесполезной траты времени на его построения, а патентные бюро – от рассмотрения заявок горе-изобретателей. Аналогично доказанная неразрешимость 10-ой проблемы Гильберта дает математикам "моральное право" больше не тратить время на попытки найти универсальный метод решения диофантовых уравнений, а финансирующим органам – отказывать в поддержке проектов, обещающих разработать такой метод.

Однако у доказательства неразрешимости проблемы есть и другая польза, более важная, чем само ее решение. – это новые идеи и методы, разработанные для получения ее решения. В начале 50-ых годов американский математик Мартин Дейвис выдвинул гипотезу, которая утверждала, что одно из основополагающих понятий информатики – понятие перечислимого множества – совпадает с теоретико-числовым понятием диофантова множества, возникающим при изучении параметрических диофантовых уравнений. Гипотеза Дейвиса была доказана через два десятилетия после ее выдвижения, последний шаг в 1970 году сделал советский математик Юрий Матиясевич.

Гипотеза Дейвиса, став теоремой, позволила установить неразрешимость многих других проблем и получить другие интересные следствия. Например, на основе диофантовых уравнений была предложена новая криптографическая система.

Академик Юрий Матиясевич подчеркнул, что не следует думать, что с установлением неразрешимости 10-ой проблемы Гильберта закрыты все алгоритмические проблемы, связанные с диофантовыми уравнениями. Напротив, здесь имеется много открытых проблем, которые 21-ый век унаследовал от 20-го. Это направление продолжает развиваться.

В ходе обсуждения доклада президент РАН академик Юрий Осипов отметил, что именно Юрий Владимирович Матиясевич внес самый большой вклад в решение проблем Гильберта. На этой базе может быть построено решение многих проблем криптографии и теории чисел.