Математическая логика и теория алгоритмов. Сергиевская И.М. - 40 стр.

• Детерминированность алгоритма. Величины, получаемые на каком-либо (не
  начальном) этапе решения задачи, должны однозначно определяться величинами,
  полученными на предшествующих этапах. Кроме того, после каждого шага
  алгоритма должно быть указано, какой шаг выполняется дальше, либо дается
  команда остановки.

• Результативность алгоритма. После конечного числа шагов работа должна
  быть остановлена с указанием того, что считать результатом.

      Можно выделить семь параметров, характеризующих алгоритм:
1) совокупность возможных исходных данных;
2) совокупность возможных результатов;
3) совокупность возможных промежуточных результатов;
4) правило начала;
5) правило непосредственной переработки;
6) правило окончания;
7) правило извлечения результата.
      Мы рассмотрим элементы теории алгоритмов – рекурсивные функции и
машины Тьюринга.

В Содержание.




Глава 8. Рекурсивные функции.

     Рекурсивные функции очень хорошо иллюстрируют понятие алгоритма. Если
рассуждать упрощенно, то для рекурсивной функции должен существовать
алгоритм, вычисляющей ее значения. Вообще говоря, большая часть известных
числовых функций являются рекурсивными.
     Полезно вспомнить, как определяются элементарные функции. Вначале
рассматривается несколько классов функций: алгебраические, тригонометрические,
показательные, логарифмические. Элементарная функция определяется как
суперпозиция (или сложная функция) этих функций.
     Рекурсивные функции строятся аналогичным образом.
     Обратите внимание, что все функции в данном параграфе определены на
множестве N ∪ {0} = N 0 . Если это необходимо, в обозначении функции верхний
индекс указывает число переменных. Так, функция f n ( x1 , x2 ,..., xn ) зависит от n
переменных. Таким образом, f n : N 0n → N 0 .
     Рассмотрим вначале примитивно-рекурсивные функции.



                                         45