μ-재귀 함수

수리논리학 및 컴퓨터 과학에서 μ-재귀 함수(영어: μ-recursive function) 또는 간단히 재귀 함수란, 자연수에서 자연수로의 '계산가능한' 부분 함수이다. 재귀 이론에서는, μ-재귀 함수와 튜링 기계로 계산가능한 함수가 일치하는 것임이 알려져 있다. 유명한 예로 피보나치 수 등이 있다.

μ-재귀 함수는 원시 재귀 함수와 밀접한 관련이 있으며, 그 재귀적(귀납적) 정의가 원시 재귀 함수에 기초하고 있다. 다만, μ재귀함수가 모두 원시 재귀 함수인 것은 아닌데, 그러한 예로 아커만 함수 등이 있다.

또 재귀함수와 일치하는 개념으로는, 람다 계산에서 쓰이는 재귀함수나 마르코프 알고리즘(Markov algorithms)으로 계산가능한 함수 등이 있다.

전역 μ-재귀 함수를 모은 클래스는 복잡도 클래스 R과 같다. 이는 PR을 포함한다.

정의

μ-재귀 함수란, 유한 개의 자연수의 튜플을 취하여 1개의 자연수를 내어놓는 부분 함수를 가리키는 말로, 이들의 클래스는 초등함수를 포함하면서 합성, 원시재귀, μ작용소(μ연산자)에 대하여 닫혀 있는 부분 함수의 클래스 중 최소의 것이다.

원시 재귀 함수와 똑같은 방식으로 정의되지만, 전역 함수이며 μ 연산자가 추가되어 있다는 점에서 다르다. 때문에 아커만 함수와 같이 원시 재귀 함수는 아니면서 전역 재귀 함수인 것을 정의에 포함할 수 있다. μ-재귀함수에서 μ 연산자는 비유계(unbounded)의 '탐색' 작용소로서 작용하며, 마지막으로 수를 내어놓고 연산을 종료시키는 역할을 한다.

그러나, 만약 비유계 μ 작용소 그 자신이 부분적이라면(즉 수를 내어놓지 못하는 경우가 존재한다면) 그것이 쓰인 함수 역시 부분함수가 되어 일부 수에 대하여 정의되지 않게 된다. 이러한 경우, μ작용소는 비유계이기 때문에 탐색을 끝없이 계속할 것이고, 결국 영원히 수를 내어놓고 계산을 종료하지 못하게 된다. (간혹 비결정임을 나타내는 기호 u를 내어놓을 수 있고 연산을 끝내도록 정의해두기도 한다.) 다르게 말하면, 부분 μ작용소를 쓰는 부분 μ재귀 함수는 전역적이지 않을 수도 있다.

초등함수

우선 다음을 초등함수로 정의한다(Kleene (1952) p. 219 에 근거):

1. 상수 함수(constant function): 각 자연수 $n$과 $k$에 대하여:

   $f(x_{1},\ldots ,x_{k})=n$.

   정수 $n$은, 0만을 내어놓는 영함수에 따름수 함수의 합성을 반복시키는 것으로서 정의하기도 한다.

2. 따름수 함수(successor function) S:

   $S(x){\stackrel {\mathrm {def} }{=}}f(x)=x'=x+1\,$

3. 사영 함수(projection function) $P_{i}^{k}$: $1$ ≤ $i$ ≤ $k$를 만족하는 모든 자연수 $i,k\,$에 대하여:

   $P_{i}^{k}(x_{1},\ldots ,x_{k}){\stackrel {\mathrm {def} }{=}}f(x_{1},\ldots ,x_{k})=x_{i}$

작용소

다음은 작용소(연산자)이다:

1. 합성 작용소(composition operator): m항 함수 $h(x_{1},\ldots ,x_{m})\,$와 m개의 k항 함수 $g_{1}(x_{1},\ldots ,x_{k}),\ldots ,g_{m}(x_{1},\ldots ,x_{k})$를 취하여, $x_{1},\ldots ,x_{k}$를 다음과 같이 매핑하는 함수를 반복하는 조작이다:

   $f(x_{1},\ldots ,x_{k})=h(g_{1}(x_{1},\ldots ,x_{k}),\ldots ,g_{m}(x_{1},\ldots ,x_{k}))$

2. 원시 재귀 작용소(primitive recursion operator): 함수 $g(x_{1},\ldots ,x_{k})$와 $h(y,z,x_{1},\ldots ,x_{k})$를 취하여 다음과 같은 함수 $f$를 반복하는 조작이다:

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

   $f(y+1,x_{1},\ldots ,x_{k})=h(y,f(y,x_{1},\ldots ,x_{k}),x_{1},\ldots ,x_{k})$.

3. μ 작용소: 함수 $f(y,x_{1},\ldots ,x_{k})$를 취하여, $x_{1},\ldots ,x_{k}$를 변수로 하는 함수 $\mu yf(y,x_{1},\ldots ,x_{k})$를 반복하는 조작이다. 여기서 함수 $f$는 자연수 $\{0,1,...n\}$로부터 자연수 $\{0,1,...n\}$로의 수론적 함수이거나 치역이 $\{0,1\}$인 진리값을 나타내는 지시함수이다. 또 함수 $\mu yf$는 $f(0,x_{1},\ldots ,x_{k}),f(1,x_{1},\ldots ,x_{k}),...,f(y,x_{1},\ldots ,x_{k})$가 모두 결과값을 내어놓을 때 $f(y,x_{1},\ldots ,x_{k})=0$를 만족시키는 자연수 $y$가 존재하면 그 중 최소의 값을 내어놓고, 만약 그러한 $y$가 없으면 $\mu yf$는 변수 $x_{1},\ldots ,x_{k}$에 대하여서는 정의되지 않는다.

계산가능성 이론에서

(halt하지 않을 가능성을 가지는) 튜링 기계의 계산능력과 일치하며, 처치-튜링 명제는 "μ-재귀에 해당한다는 것이 '계산가능'이라는 무정의 용어에 대한 최적의 정의"이라는 주장이다.

원시재귀와의 관계

μ 연산자는 일부 입력값에 대하여 정의되지 않을 수 있으며, 컴퓨터적으로 표현하면 계산이 끝나지 않고 영원히 계속될 수 있다. 이로 인해 원시 재귀와의 결정적 차이가 발생하지만, 클레이니의 정규형 정리에 의하면 모든 재귀함수는 원시재귀함수와 μ 연산자를 결합한 형태로 적절히 분해할 수 있다.

같이 보기

• 계산 가능성 이론
• 원시 재귀 함수
• 계산 가능 함수