Математическая логика и теория алгоритмов. Стенюшкина В.А. - 54 стр.

ли целые корни у уравнения Р(х1,…,хm)=0, где Р (х1,…,хm)- произвольный мно-
гочлен с целыми коэффициентами от любого числа m переменных. Задача точ-
ного определения алгоритма стала одной из центральных математических про-
блем. Возникла теория алгоритмов, изучаются общие свойства алгоритмов.
      В 1936 году А. Черч опубликовал первое уточнение вычислимой функ-
ции, а А. Тьюринг и Э. Пост дали первые уточнения понятия алгоритма в тер-
минах идеализированных вычислительных машин. В дальнейшем А.А. Марков
предложил ввести понятие «нормального алгоритма». В рамках этих уточнений
упомянутая ранее алгоритмическая проблема, известная как 10-я проблема Ги-
льберта, оказалась неразрешимой.
      Теорию алгоритмов можно разделить на дескриптивную (качественную)
и метрическую (количественную). Первая исследует алгоритмы с точки зрения
устанавливаемого ими соответствия между исходными данными и результата-
ми. К ней относятся, в частности, проблемы построения алгоритма, обладаю-
щего теми или иными свойствами, - алгоритмические проблемы. Вторая иссле-
дует алгоритмы с точки зрения сложности как самих алгоритмов, так и задава-
емых ими вычислений, то есть процессов последовательного преобразования
конструктивных объектов.
      Приложения теории алгоритмов имеются во всех областях математики.
Теория алгоритмов тесно связана с математической логикой через понятие ис-
числения (например, теорема Геделя о неполноте может быть выведена из тео-
рем теории алгоритмов), с основаниями математики, в которых одно из центра-
льных мест занимает проблема соотношения конструктивного и неконструкти-
вного, с кибернетикой (алгоритмы управления), с теорией информации (в 1965
году А.Н. Колмогоров предложил использовать теорию алгоритмов для обос-
нования теории информации).

      1 Вычислимые функции

      1.1 Понятие вычислимой функции. График вычислимой функции

       Вычислимые функции (ВФ) – одно из основных понятий теории алгори-
тмов. Функция f называется вычислимой, если существует алгоритм, перераба-
тывающий всякий объект х, для которого определена функция f, в объект f(х) и
не приводящий к результату ни для какого х, для которого f не определена /3/.
Графиком ВФ называется множество пар вида (х, f(х)).
      Примеры
      1 х – любое натуральное число, f(х)=х2;
      2 х – пара рациональных чисел х1, х2, f(х)=х1:х2 (эта функция определена
лишь для тех х, у которых х2≠0);
      3 X – пара матриц X1, X2 с целочисленными элементами, f(X)=X1*X2
(эта функция определена лишь для тех X, у которых число столбцов в X1 равно
числу строк в X2)