원시 재귀 함수

계산 가능성 이론에서 원시 재귀 함수(영어: primitive recursive function)은 원시 재귀와 합성 연산으로 정의되는 함수이다. 원시 재귀 함수의 클래스는 μ-재귀 함수의 클래스의 부분집합이며, μ-재귀 함수와는 달리 전역적(total)이다. 원시 재귀 함수의 클래스는 PR로 표기되며, 이는 R의 일부이다.

원시 재귀 함수는 우선 자연수에서 자연수로의 함수, 즉 수론적 함수여야 한다. n개의 변수를 받는 이 함수를 n항 함수라 한다.

원시 재귀 함수는 기본적으로 다음 공리들로부터 주어진다:

1. 상수 함수: 0항 함수 ${\displaystyle 0}$은 원시 재귀 함수이다.

2. 따름수 함수: 1항 함수 ${\displaystyle S}$는 인수의 따름수를 반환하는 함수로, 원시 재귀 함수이다. (${\displaystyle S(k)=k+1}$)

3. 사영 함수: 각 n≥1 과 각 1≤i≤n에 대하여, n항 함수 ${\displaystyle P_{i}^{n}}$는 i번째 인수를 반환하는 함수로, 원시 재귀 함수이다.

다음 공리들로 주어지는 작용소(연산자)를 추가하여 더 복합적인 원시 재귀 함수를 얻을 수 있다:

4. 합성: k항 원시 재귀함수 ${\displaystyle f}$, k개의 m항 원시 재귀함수들 ${\displaystyle g_{1},...,g_{k}}$가 주어졌을 때, ${\displaystyle f}$와 ${\displaystyle g_{1},...,g_{k}}$의 합성, 즉 m항 함수 ${\displaystyle h(x_{1},\ldots ,x_{m})=f(g_{1}(x_{1},\ldots ,x_{m}),\ldots ,g_{k}(x_{1},\ldots ,x_{m}))\,}$는 원시 재귀 함수이다.

5. 원시 재귀: k항 원시 재귀함수 ${\displaystyle f}$, (k+2)항 원시 재귀 함수 ${\displaystyle g}$가 주어졌을 때, (k+1)항 함수 ${\displaystyle h}$는 ${\displaystyle f}$와 ${\displaystyle g}$의 원시 재귀로 정의된다. 즉, 다음이 성립하면 ${\displaystyle h}$는 원시 재귀 함수이다:

${\displaystyle h(0,x_{1},\ldots ,x_{k})=f(x_{1},\ldots ,x_{k})\,}$

${\displaystyle h(S(y),x_{1},\ldots ,x_{k})=g(y,h(y,x_{1},\ldots ,x_{k}),x_{1},\ldots ,x_{k})\,.}$

• μ-재귀 함수
• 재귀 (컴퓨터 과학)

이 글은 수학에 관한 토막글입니다. 여러분의 지식으로 알차게 문서를 완성해 갑시다.