Математическая логика и теория алгоритмов. Для изучающих компьютерные науки

Таким образом, существуют как алгоритмически разрешимые проблемы, так и алгоритмически неразрешимые массовые проблемы. К алгоритмически разрешимым массовым проблемам относятся, например, следующие: -сложение двух и более заданных чисел; -решение в радикалах уравнений от одной переменной не выше четвертой степени; -решение систем линейных уравнений с п неизвестными; -и т.д. Обнаружение алгоритмически неразрешимых проблем создало в науке такую ситуацию, когда математик, стремящийся к построению желаемого алгоритма, должен считаться с тем, что такого алгоритма может и не существовать. Поэтому параллельно с поиском желаемого алгоритма приходится прилагать усилия для доказательства существования такого алгоритма. Алгоритмически неразрешимые массовые проблемы. 1. Рассмотрим полиномы, зависящие от произвольного числа переменных XI,X2,...,XN С целыми коэффициентами. Такие полиномы называют диофантовыми в память греческого математика Диофанта, рассмотревшего некоторые из таких полиномов. Будем интересоваться, есть ли у такого полинома целочисленные корни (диофантовы корни). Целочисленными решениями полиномов интересовались еще античные математики, например, в связи с теоремой 2 2 2 Пифагора они рассматривали уравнение х +у =z . Евклид приводит формулы, позволяющие найти все целочисленные решения этого уравнения. Сам Диофант (III. н.э.) среди многих других уравнений рассмотрел уравнение 2 2 ах +Ьх+с=у и решил его для некоторых частных случаев. В эпоху развития анализа диофантовы уравнения привлекали внимание таких выдающихся ученых, как Ферма, Эйлер, Лагранж, Гаусс. В частности. Ферма выдвинул знаменитую гипотезу о том, что уравнение при п>2 не имеет целочисленных решений (большая теорема Ферма). Па рубеже Х1Х-ХХ вв. Гильберт включил проблему диофантовых уравнений в число наиболее важных проблем, которые XIX век оставил XX веку. Эта проблема была сформулирована им так [33]: "Пусть задано произвольное диофантово уравнение с произвольными неизвестными и целыми рациональными числовыми коэффициентами. Указать способ, при помощи которого возможно после конечного числа операций установить, разрешимо ли это уравнение в целых рациональных числах". Эта проблема называется 10-й проблемой Гильберта. 166