원시 재귀 함수 문서 원본 보기

{{위키데이터 속성 추적}}
[[계산 가능성 이론]]에서 '''원시 재귀 함수'''({{llang|en|primitive recursive function}})은 원시 [[재귀]]와 [[함수의 합성|합성]] 연산으로 정의되는 [[함수]]이다. 원시 재귀 함수의 클래스는 [[μ-재귀 함수]]의 클래스의 부분집합이며, μ-재귀 함수와는 달리 전역적(total)이다. 원시 재귀 함수의 클래스는 [[PR (복잡도)|PR]]로 표기되며, 이는 [[R (복잡도)|R]]의 일부이다.

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

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

:1. '''상수 함수''': 0항 함수 <math>0</math>은 원시 재귀 함수이다.
:2. '''따름수 함수''': 1항 함수 <math>S</math>는 인수의 따름수를 반환하는 함수로, 원시 재귀 함수이다. (<math>S(k) = k + 1</math>)
:3. '''사영 함수''': 각 n≥1 과 각 1≤i≤n에 대하여, n항 함수 <math>P^n_i</math>는 i번째 인수를 반환하는 함수로, 원시 재귀 함수이다.

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

:4. '''합성''': k항 원시 재귀함수 <math>f</math>, k개의 m항 원시 재귀함수들 <math>g_1,...,g_k</math>가 주어졌을 때, <math>f</math>와 <math>g_1,...,g_k</math>의 합성, 즉 m항 함수 <math>h(x_1,\ldots,x_m) = f(g_1(x_1,\ldots,x_m),\ldots,g_k(x_1,\ldots,x_m)) \,</math>는 원시 재귀 함수이다.
:5. '''원시 재귀''': k항 원시 재귀함수 <math>f</math>, (k+2)항 원시 재귀 함수 <math>g</math>가 주어졌을 때, (k+1)항 함수 <math>h</math>는 <math>f</math>와 <math>g</math>의 원시 재귀로 정의된다. 즉, 다음이 성립하면 <math>h</math>는 원시 재귀 함수이다:
:<math>h (0, x_1, \ldots, x_k) = f (x_1, \ldots, x_k) \,</math>
:<math>h (S(y), x_1, \ldots, x_k) = g (y, h (y, x_1, \ldots, x_k), x_1, \ldots, x_k) \,.</math>

== 예시 ==
{{빈 문단}}

== μ-재귀 함수와의 연관 ==
{{빈 문단}}

== 같이 보기 ==
* [[μ-재귀 함수]]
* [[재귀 (컴퓨터 과학)]]

{{토막글|수학}}

[[분류:계산 가능성 이론]]
[[분류:계산 이론]]
[[분류:재귀]]