Изменения

В 1900 году в Париже на втором Международном Конгрессе математиков выдающийся математик Давид Гильберт выступил с докладом, который назывался "Математические проблемы"«Математические проблемы». Десятая из двадцати трех обозначенных в докладе проблем была сформулирована Гильбертом так:

В современной терминологии десятая проблема Гильберта является примером массовой проблемы. Массовая проблема состоит из счетного количества вопросов на каждый из которых нужно дать ответ {{---}} да или нет. В данном случае эти вопросы параметризуются диофантовыми уравнениями и нужно сказать: да, данное диофантово уравнение имеет решение или нет, данное уравнение не имеет решения. И суть массовой проблемы состоит в том, что нужно найти единый универсальный метод, который позволял бы ответить на любой из этих вопросов. Среди двадцати трех "Математических проблем" «Математических проблем» Гильберта десятая является единственной массовой проблемой и она может рассматриваться, как проблема информатики. Сегодня мы знаем, что десятая проблема Гильберта решения не имеет. Это означает, что она не разрешима, как массовая проблема.

Во времена, когда Гильберт формулировал свои проблемы, не было общего определения понятия алгоритма, однако Гильберт был оптимистом в математике, верил в разрешимость этой проблемы, в этом смысле задача была сформулирована им вполне корректно. Задача о целых решениях произвольного уравнения сводится к задаче о целых неотрицательных решениях. Далее достаточно ограничиться диофантовыми уравнениями степени не выше четвертой. Для диофантовых уравнений степени не выше второй искомый общий метод был найден, однако уже для уравнений третьей степени эта задача казалась неразрешимой, возникло предположение,что тот общий метод, об отыскании которого говорится в формулировке Гильберта, попросту не существует. Чтобы доказать не существование некого общего метода для решения серии задач, требовалось дать точное определение тому, что такое этот общий метод и какими средствами он может быть реализован. Понятие алгоритма было сформулировано в тридцатые годы двадцатого века в работах матлогиков Черча, Клини, Тьюринга, Геделя. Важную роль в решении десятой проблемы Гильберта сыграл Эмиль Пост. Постом было впервые предложено общее понятие вычислимости, которое имеет фундаментальное значение для доказательства неразрешимости ряда проблем математики. В одной из своих работ он написал, что десятая проблема Гильберта "молит «молит о доказательстве неразрешимости"неразрешимости». Эти слова Поста вдохновили его молодого ученика Мартина Дэвиса, который смог сформулировать гипотезу, из которой следовала неразрешимость десятой проблемы Гильберта.

Исследования Мартина Дэвиса, направленные на доказательство неразрешимости десятой проблемы Гильберта, привели его к постановке задачи, когда описано некоторое множество и требуется узнать, является ли оно диофантовым. В простейших случаях диофантовость множества очевидна {{---}} ясно, например, что диофантовым является множество всех положительных нечетных чисел. Однако совсем нелегко ответить на такие естественные вопросы, как "диофантово «диофантово ли множество всех степеней числа <tex>2</tex>?», "диофантово «диофантово ли множество всех простых чисел?"», "диофантово «диофантово ли множество всех совершенных чисел?" » С первого взгляда кажется, что на эти вопросы следует дать отрицательный ответ. Тем не менее все эти множества являются диофантовыми. Приведем примеры диофантовых множеств: