Двойная рекурсия

В теории рекурсивных функций, двойная рекурсия - это расширение примитивной рекурсии, которое позволяет определять непримитивные рекурсивные функции, такие как функция Аккермана.

Рафаэль М. Робинсон, называемые функциями две натуральные переменные G (n, x), дважды рекурсивные по отношению к заданным функциям, если

• G (0, x) является заданной функцией x.
• G (n + 1, 0) получается подстановкой из функции G (n, ·) и заданных функций.
• G (n + 1, x + 1) получается подстановкой из G (n + 1, x), функция G (n, ·) и заданные функции.

Робинсон предлагает конкретную двойную рекурсивную функцию (первоначально определенную Розса Петер )

• G (0, x) = x + 1
• G (n + 1, 0) = G (n, 1)
• G (n + 1, x + 1) = G (n, G (n + 1, x))

где заданная функция s примитивно рекурсивны, но G не является примитивно рекурсивным. Фактически, это именно та функция, которая теперь известна как функция Аккермана.

• Примитивная рекурсия
• функция Аккермана