Рекурсивные функции. Самая первая алгоритмическая система

Самая первая алгоритмическая система.

Рекурсией называется способ задания функции, при котором значения функции для произвольных аргументов выражается через значения функции для меньших значений аргумента.

Численные функции, значение которых можно определить, используя некоторый алгоритм, называются вычислимыми.

Функция называется рекурсивной, если существует эффективная процедура ее вычисления.

Совокупность числовых функций, совпадающая с совокупностью всех вычислимых функций, называется множеством рекурсивных функций.

Гипотеза Черча: класс рекурсивных функций тождественен с классом всюду определенных вычислимых функций.

Частично определенные целочисленные и целозначные функции называют арифметическими функциями. Среди них выделяют наиболее простые, которые называются элементарные арифметические функции.

Простые функции:

Ø тождественно равные нулю

0ⁿ(x₁, x₂, …, x_n) = 0

n – количество аргументов

Ø повторяющая значение аргумента

I_iⁿ (x₁, x₂, …, x_n) = x_i

Ø функция непосредственного следования

S¹(x) = x+1

Используя элементарные функции и известные конструктивные методы можно получать все более и более сложные арифметические функции.

В теории алгоритмов наиболее важными являются 3 метода построения сложных функций:

Ø суперпозиция

Ø примитивная рекурсия

Ø наименьшего корня