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

Примити́вная реку́рсия, способ определения функций от натуральных аргументов с натуральными значениями. Говорят, что ${\displaystyle (n+1)}$-местная функция ${\displaystyle f(x_{1},\dots ,x_{n},y)}$ получена примитивной рекурсией из ${\displaystyle n}$-местной функции ${\displaystyle g(x_{1},\dots ,x_{n})}$ и ${\displaystyle (n+2)}$-местной функции ${\displaystyle h(x_{1},\dots ,x_{n},y,z)}$, если для всех натуральных значений ${\displaystyle x_{1},\dots ,x_{n}}$, ${\displaystyle y}$ имеет место

${\displaystyle f(x_{1},\dots ,x_{n},0)=g(x_{1},\dots ,x_{n})}$

и

${\displaystyle f(x_{1},\dots ,x_{n},y+1)=h(x_{1},\dots ,x_{n},y,f(x_{1},\dots ,x_{n},y))}$.

Для данных ${\displaystyle g}$ и ${\displaystyle h}$ такая функция ${\displaystyle f}$ всегда существует и единственна. При ${\displaystyle n=0}$ определяющие равенства для ${\displaystyle f}$ записываются в виде

${\displaystyle f(0)=a,\quad f(x+1)=h(x,f(x))}$.

Фундаментальным свойством примитивной рекурсии является то, что при любом разумном уточнении понятия вычислимости функция ${\displaystyle f}$, полученная из вычислимых функций ${\displaystyle g}$ и ${\displaystyle h}$ с помощью примитивной рекурсии, сама вычислимая. Примитивная рекурсия – одно из основных правил порождения всех примитивно рекурсивных и всех частично рекурсивных функций из исходного набора простейших функций.