Теория алгоритмов, формальных языков, грамматик и автоматов. Бильгаева Н.Ц. - 9 стр.

    Данное определение записывается следующим образом:
                        f(x1, x2, ..., xn) = µ z < U(x) (P(x1, x2, ..., xn, z)).
    Ограничение z в ограниченном операторе минимизации дает гарантию окончания
вычислений, поскольку оно оценивает сверху число вычислений предиката P. Возможность
оценить сверху количество вычислений является существенной особенностью примитивно-
рекурсивных функций.

      2.3. Примитивно-рекурсивные и частично-рекурсивные функции
    Большинство вычислимых функций относится к классу примитивно-рекурсивных
функций.
    Функция называется примитивно-рекурсивной, если она может быть получена из
простейших функций с помощью конечного числа операторов суперпозиции и примитивной
рекурсии.
    Если некоторые функции являются примитивно-рекурсивными, то в результате
применения к ним операторов суперпозиции или примитивной рекурсии можно получить
новые примитивно-рекурсивные функции.
    Существует три возможности доказательства того, что функция является примитивно-
рекурсивной:
    а) показать, что заданная функция является простейшей;
    б) показать, что заданная функция построена с помощью оператора суперпозиции;
    в) показать, что заданная функция построена с помощью оператора примитивной
рекурсии.
    Тем не менее примитивно-рекурсивные функции не охватывают все вычислимые
функции, которые могут быть определены конструктивно. При построении этих функций
могут использоваться другие операции. Функция называется частично-рекурсивной, если
она может быть получена из простейших функций с помощью конечного числа операторов
суперпозиции, примитивной рекурсии и минимизации. Указанные операции могут быть
выполнены в любой последовательности и любое конечное число раз. Если такие функции
оказываются всюду определенными, то они называются общерекурсивными функциями.
Частично-рекурсивные функции вычислимы путем определенной процедуры механического
характера. Практически понятием частично-рекурсивных функций пользуются для
доказательства алгоритмической разрешимости или неразрешимости проблем. Приведем
тезис Черча, который связывает понятие алгоритма и строгое математическое понятие
частично-рекурсивной функции. Тезис Черча: всякий алгоритм может быть реализован
частично-рекурсивной функцией. Утверждение о несуществовании частично-рекурсивной
функции эквивалентно несуществованию алгоритма решения соответствующей задачи.

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