Неразрешимость проблемы существования решения диофантова уравнения в целых числах
|
Эта статья находится в разработке |
В 1900 году в Париже на втором Международном Конгрессе математиков выдающийся математик Давид Гильберт выступил с докладом, который назывался "Математические проблемы". Десятая из двадцати трех обозначенных в докладе проблем была сформулирована Гильбертом так:
| Задача: |
| Решение проблемы разрешимости для произвольного диофантова уравнения. Пусть дано произвольное диофантово уравнение с произвольным числом неизвестных и целыми рациональными коэффициентами; требуется указать общий метод, следуя которому можно было бы в конечное число шагов узнать, имеет ли данное уравнение решение в целых рациональных числах или нет. |
| Определение: |
| Диофантово уравнение имеет вид , где — многочлен с целыми коэффициентами. |
Диофант искал решение этих уравнений в рациональных числах, Гильберт спрашивал про решение диофантовых уравнений в целых числах.
В современной терминологии десятая проблема Гильберта является примером массовой проблемы. Массовая проблема состоит из счетного количества вопросов на каждый из которых нужно дать ответ — да или нет. В данном случае эти вопросы параметризуются диофантовыми уравнениями и нужно сказать: да, данное диофантово уравнение имеет решение или нет, данное уравнение не имеет решения. И суть массовой проблемы состоит в том, что нужно найти единый универсальный метод, который позволял бы ответить на любой из этих вопросов. Среди двадцати трех "Математических проблем" Гильберта десятая является единственной массовой проблемой и она может рассматриваться, как проблема информатики. Сегодня мы знаем, что десятая проблема Гильберта решения не имеет. Это означает, что она не разрешима, как массовая проблема.
| Теорема (Неразрешимость десятой проблемы Гильберта): |
Не существует алгоритма, который узнавал бы по произвольному диофантову уравнению, имеет ли оно решения. |
Таким образом, можно говорить об отрицательном решении десятой проблемы Гильберта.
Этапы доказательства неразрешимости десятой проблемы Гильберта
Во времена, когда Гильберт формулировал свои проблемы, не было общего определения понятия алгоритма, однако Гильберт был оптимистом в математике, верил в разрешимость этой проблемы, в этом смысле задача была сформулирована им вполне корректно. Понятие алгоритма было сформулировано в тридцатые годы двадцатого века в работах матлогиков Черча, Клини, Тьюринга, Геделя. Важную роль в решении десятой проблемы Гильберта сыграл Эмиль Пост. В одной из своих работ он написал, что десятая проблема Гильберта "молит о доказательстве неразрешимости".
