Математическая логика и теория алгоритмов

Обнаружение алгоритмически неразрешимых проблем создало в науке такую ситуацию, когда математик, стремящийся к построению желаемого алгоритма, должен считаться с тем, что такого алгоритма может и не существовать. Поэтому параллельно с поиском желаемого алгоритма приходится прилагать усилия для доказательства сущест­ вования такого алгоритма. Рассмотрим, например, полиномы, зависящие от произвольного числа переменных хих2,...,х„ с целыми коэффициентами. Такие полиномы называют диофантовыми в память греческого математика Диофанта, рассмотревшего некоторые из таких полиномов. Будем интересоваться, есть ли у такого полинома целочисленные корни (диофантовы корни). Целочисленными решениями полиномов интересовались еще античные математики, например, в связи с теоремой Пифагора они рассматривали уравнение x^+y^-z^. Евклид приводит формулы, позволяющие найти все целочисленные решения этого уравнения. Сам Диофант (III в. н.э.) среди многих других уравнений рассмотрел уравнение ах'^+Ьх+с=у^ и решил его для неко­ торых частных случаев. В эпоху развития анализа диофантовы уравнения привлекали внимание таких выдающихся ученых как Ферма, Эйлер, Лагранж, Гаусс. В частности. Ферма выдвинул знаменитую гипотезу о том, что уравнение x"+y"=z" при п>2 не имеет целочисленных решений (большая теорема Ферма). На рубеже Х1Х-ХХ вв. Гильберт включил проблему диофан- товых уравнений в число наиболее важных проблем, которые XIX век оставил XX веку. Эта проблема бьша сформулирована им так [27]: "Пусть задано произвольное диофантовое уравнение с произвольными неизвестными и целыми рациональными числовыми коэффициентами. Указать способ, при помощи которого возможно после конечного числа операций установить, разрешимо ли это уравнение в целых рациональных числах". Эта проблема называется 10-й п р о б л е м о й Гильберта. 2 4 7