원시재귀 함수

수치해석 소프트웨어 마지막 수정: 2026-09-14 04:31:07

○ 공개 검수 대기 표시 기준 보기

1. 개요

원시재귀 함수 Primitive Recursive Function
기본 함수	영함수 · 후속자 $S(x)=x+1$ · 사영 $P^n_i$
만드는 규칙	합성 · 원시재귀 (딱 둘)
프로그래밍 대응	횟수가 정해진 `for` 문만 쓰는 언어
보장되는 것	모든 입력에서 정지하는 전체함수
못 담는 것	아커만 함수 — 전체이고 계산 가능하지만 원시재귀 아님
확장	뮤 연산자(무계 최소화)를 더하면 일반재귀 = 계산 가능
위계	그제고르치크 $\bigcup_n \mathcal{E}^n$ · 빠른 성장 위계의 유한 층 $F_k$

안전한 언어를 만드는 방법은 간단하다. while 을 빼면 된다. 문제는 그러면 못 짜는 함수가 생긴다는 것이다.

원시재귀 함수(primitive recursive function)는 영함수·후속자·사영이라는 세 가지 기본 함수에서 출발해 합성과 원시재귀라는 두 가지 규칙만으로 만들어지는 자연수 함수들의 모임이다. 정의가 이렇게 인색한데도 덧셈·곱셈·거듭제곱·나눗셈·소수 판정·정렬·행렬 곱셈까지 우리가 실제로 짜는 알고리즘이 사실상 전부 여기에 들어간다.

이 모임이 수학사에 남은 이유는 담고 있는 것 때문이 아니라 담지 못하는 것 때문이다. 원시재귀 함수는 정의상 모든 입력에서 정지한다 — 무한 루프가 원천적으로 불가능하다. 그런데 “정지하면서 계산 가능한 함수”를 전부 담지는 못한다. 1928년 아커만 함수가 그 반례로 등장하면서, 계산 가능성 ⊋ 원시재귀라는 구분이 확정됐다. 프로그래밍 언어의 말로 옮기면 for 문만으로는 못 짜고 while 문이 있어야 짤 수 있는 함수가 존재한다는 것이고, 이 트레이드오프는 오늘날 정지성을 보장하는 언어와 컴퓨터 보조 증명 도구 설계에서 그대로 되풀이된다.

2. 정의 — 기본 셋과 규칙 둘

기본 함수는 셋이다.

영함수 $Z() = 0$ (혹은 상수 0을 내는 $n$ 변수 함수)
후속자 $S(x) = x + 1$
사영 $P^n_i(x_1,\dots,x_n) = x_i$

규칙도 둘뿐이다.

합성. $m$ 변수 $h$ 와 $n$ 변수 함수 $g_1,\dots,g_m$ 에서

f(\vec{x}) = h\big(g_1(\vec{x}),\,\dots,\,g_m(\vec{x})\big)

원시재귀. $g$ 와 $h$ 에서 마지막 인자를 1씩 줄여 가는 재귀로

f(\vec{x},\,0) = g(\vec{x}), \qquad f(\vec{x},\,y+1) = h\big(\vec{x},\,y,\,f(\vec{x},\,y)\big)

두 번째 규칙이 이 체계의 심장이다. 새 값은 바로 직전 값 하나와 현재 카운터로부터만 만들어지고, 카운터는 반드시 1씩 내려간다. 재귀 호출의 깊이가 인자 $y$ 에 의해 미리 결정되므로 정지성은 $y$ 에 대한 귀납법 한 줄로 끝난다. 이 모임이 전부 전체함수(total function)인 것은 증명할 무언가가 아니라 정의에서 그냥 따라 나오는 성질이다.

3. 무엇이 만들어지는가

기본 셋에서 시작하면 금방 익숙한 것들이 나온다.

\mathrm{add}(x,0)=x,\quad \mathrm{add}(x,y+1)=S(\mathrm{add}(x,y))

\mathrm{mul}(x,0)=0,\quad \mathrm{mul}(x,y+1)=\mathrm{add}(x,\mathrm{mul}(x,y))

곱셈에서 거듭제곱, 거듭제곱에서 계승이 같은 방식으로 나온다. 한 층 위의 연산은 아래 층 연산의 반복이라는 구조가 여기서 이미 보이는데, 이 사다리를 함수 하나에 통째로 집어넣으면 아커만 함수가 된다는 점이 나중에 중요해진다.

조건 분기도 만들 수 있다. 열쇠는 잘린 뺄셈(monus) $x \dot{-} y = \max(x-y,\,0)$ 이고, 이것 역시 전임자 함수의 원시재귀로 정의된다. 여기서 부호 함수 $\mathrm{sg}(x)$ , 비교 술어, if-then-else 가 전부 따라 나온다. 술어는 0/1 값을 내는 함수로 다루면 되므로 논리곱·논리합·부정도 산술로 표현된다.

더 놀라운 것은 유계 연산이 전부 원시재귀라는 사실이다.

유계 합 $\sum_{i \le n} f(i)$ , 유계 곱 $\prod_{i \le n} f(i)$
유계 최소화 $\mu y \le n.\,[\,P(y)\,]$ — ” $n$ 이하에서 $P$ 를 만족하는 최소의 $y$ , 없으면 $n+1$ ”

유계 최소화가 있다는 것은 탐색 범위에 상한을 미리 댈 수만 있으면 탐색도 원시재귀라는 뜻이다. 나눗셈·나머지·약수 판정·소수 판정· $n$ 번째 소수 모두 여기서 나온다. 괴델의 β 함수나 소인수분해를 이용한 수열 부호화를 쓰면 유한 수열 전체를 자연수 하나에 넣고 꺼내는 일도 원시재귀가 되므로, 리스트·스택·배열을 쓰는 알고리즘도 결국 이 안이다.

정리하면 이렇다. 실무 알고리즘 중 “얼마나 오래 걸릴지 입력만 보고 상한을 댈 수 있는” 것은 전부 원시재귀다. 정렬, 행렬 연산, 동적 계획법, 그래프 탐색, 수치적분 루틴, 고정 반복 횟수의 선형계 풀이 — 다 들어간다.

4. `for` 문과 `while` 문

이 대응이 이 문서에서 가장 실용적인 부분이다. 마이어와 리치(1967)의 LOOP 언어는 변수 대입, 증감, 그리고 딱 한 종류의 반복문만 갖는다.

LOOP x DO  ...  END

의미는 “몸통을 $x$ 번 실행한다”이고, 결정적인 제약은 몸통 안에서 $x$ 를 바꿔도 반복 횟수가 안 바뀐다는 것이다. 횟수가 진입 시점에 확정된다. 이 언어로 계산 가능한 함수의 모임이 정확히 원시재귀 함수다.¹

여기에 WHILE x ≠ 0 DO ... END 를 추가하면 언어의 표현력이 튜링 기계와 같아진다. 함수 쪽에서 이에 대응하는 것이 뮤 연산자(무계 최소화)다.

f(\vec{x}) = \mu y.\,[\,g(\vec{x},y) = 0\,]

” $g$ 를 0으로 만드는 최소의 $y$ ”. 유계 버전과 딱 하나가 다른데, 상한이 없다. 그런 $y$ 가 없으면 이 함수는 값을 갖지 않고, 계산은 영원히 돈다. 전체함수가 부분함수(partial function)로 바뀌는 순간이 바로 이 지점이고, 정지 여부를 미리 알 수 없게 되는 것도 정확히 이 지점이다. 원시재귀 함수에 뮤 연산자를 더한 것이 부분재귀 함수(= 튜링 계산 가능)이고, 처치-튜링 논제가 말하는 “계산 가능”이 이것이다.

뮤 연산자가 얼마나 필요한지에 대한 정확한 답도 있다. 클레이니 정규형 정리에 따르면 임의의 계산 가능한 부분함수는

\varphi_e(x) = U\big(\mu y.\,T(e,x,y)\big)

꼴로 쓸 수 있고, 여기서 술어 $T$ 와 함수 $U$ 는 원시재귀다. 즉 무계 탐색은 딱 한 번이면 충분하다. “프로그램 $e$ 가 입력 $x$ 에서 $y$ 라는 계산 기록으로 정지한다”를 검사하는 일 자체는 유한하고 원시재귀적이며, 계산 불가능성은 전부 “그런 $y$ 를 찾을 때까지 세는” 바깥쪽 루프 하나에 응축된다. 정지 문제의 난이도가 어디서 오는지를 이보다 깔끔하게 보여 주는 진술은 없다.

5. 담지 못하는 것

원시재귀가 계산 가능성 전체보다 진짜로 작다는 증명은 두 가지 맛이 있다.

대각화(추상적). 원시재귀 함수는 유한한 구성 기술(記述)을 가지므로 그 기술들을 기계적으로 나열할 수 있고, $n$ 번째 원시재귀 1변수 함수를 $f_n$ 이라 쓸 수 있다. 이제

d(n) = f_n(n) + 1

을 정의하면 $d$ 는 명백히 계산 가능하고 모든 입력에서 정지하지만, 어떤 $m$ 에 대해서도 $d \ne f_m$ 이다( $n=m$ 에서 값이 다르다). 따라서 $d$ 는 원시재귀가 아니다.²

아커만(구체적). 대각화는 존재만 보여 줄 뿐 “그래서 그게 뭔데”에 답하지 않는다. 아커만이 준 것은 세 줄로 적히는 실제 함수다. 임의의 원시재귀 함수 $f$ 에 대해 어떤 $m$ 이 존재해 $f(n) < A(m,n)$ 이 모든 $n$ 에서 성립한다는 정리가 핵심이고, 여기에 $g(n)=A(n,n)$ 을 대각선으로 넣으면 모순이 나온다. 증명의 뼈대와 그 함수가 실무에서 역함수로 되돌아오는 이야기는 아커만 함수 문서에 있다.

여기서 오해를 하나 못 박아 두자. “원시재귀가 아니다”는 “계산할 수 없다”가 아니다. 아커만 함수는 계산 가능하고 언제나 정지한다. 못 하는 것은 반복 횟수를 미리 아는 루프만으로 짜는 것뿐이다. 정지 문제의 판정 함수가 계산 불가능한 것과는 층이 완전히 다르다.

6. 증가 속도로 본 지형

원시재귀 안쪽도 평평하지 않다. 그제고르치크 위계 $\mathcal{E}^0 \subseteq \mathcal{E}^1 \subseteq \mathcal{E}^2 \subseteq \cdots$ 는 허용되는 증가 속도의 상한을 층마다 한 칸씩 올려 쌓은 것으로, 합집합이 정확히 원시재귀 함수 전체다. LOOP 언어로 말하면 반복문의 중첩 깊이가 위계의 층에 대응한다. 삼중 루프로 짤 수 있는 것과 사중 루프가 필요한 것이 진짜로 다르다는 뜻이다.

$\mathcal{E}^3$ 은 칼마르 초등함수(elementary function)로 따로 이름이 있다. 덧셈·곱셈·거듭제곱과 유계 연산으로 닫힌 모임이며, $2^{2^{2^n}}$ 처럼 높이가 고정된 거듭제곱 탑까지는 담지만 높이가 $n$ 에 따라 자라는 탑은 못 담는다. 실무 알고리즘은 거의 전부 이 아래 두세 층 안에서 끝난다.

빠른 성장 위계(fast-growing hierarchy)는 같은 지형을 순서수로 매긴다.

F_0(n) = n+1, \qquad F_{\alpha+1}(n) = F_{\alpha}^{\,(n)}(n)

( $F_\alpha$ 를 $n$ 번 합성한다는 뜻이다.) $F_1(n) \approx 2n$ , $F_2$ 는 지수, $F_3$ 은 거듭제곱 탑이고, 원시재귀 함수는 정확히 어떤 유한한 $k$ 의 $F_k$ 에 눌리는 함수들이다. 그리고 극한 자리의

F_{\omega}(n) = F_n(n)

이 본질적으로 아커만 함수다. 아커만이 원시재귀 밖에 있는 이유가 위계 그림에서는 한눈에 보인다 — 그것은 모든 유한 층 위에 걸터앉은 대각선이다.

이 사다리는 원시재귀 위로도 계속 올라간다. $F_{\varepsilon_0}$ 근처에 굿스타인 정리의 수열 길이 함수와 파리스-해링턴 함수가 있는데, 이들은 전체함수이고 계산 가능하지만 페아노 산술로는 정지성을 증명할 수 없다. 계산 가능성과 증명 가능성이 갈라지는 또 다른 층이 여기 있다.

7. 왜 이게 실무에 걸리나

정지성 검사기의 정체. Coq/Rocq, Agda, Lean 같은 증명 보조기는 재귀 정의를 받을 때 인자가 구조적으로 줄어드는지를 기계적으로 확인한다. 이 검사가 통과시키는 것이 대체로 원시재귀(를 고차 타입으로 일반화한 것)의 모양이고, 더 복잡한 재귀는 잘 정초된 관계를 사람이 직접 제시해야 한다. “정지가 보장되는 언어는 표현력을 잃는다”는 1928년의 교훈이 매일의 컴파일 에러로 되돌아오는 셈이다.³
연료(fuel) 패턴. 전종료 언어에서 while 루프를 흉내 낼 때 쓰는 국룰은 반복 횟수 상한을 인자로 하나 더 받는 것이다. fuel 이 0이 되면 기본값을 반환한다. 원시재귀로 내려앉히는 가장 정직한 방법이고, “상한만 댈 수 있으면 원시재귀”라는 위 원칙을 코드로 옮긴 것이다.
원시재귀는 효율성의 보증이 전혀 아니다. 초등함수 층에 이미 거듭제곱 탑이 들어 있다. “이 함수는 원시재귀다”는 끝나기는 한다는 말이지 실용적이라는 말이 아니며, 실제 성능을 말하려면 계산 복잡도 쪽 어휘가 필요하다. 이론적 안전성과 공학적 실행 가능성을 헷갈리면 딱 여기서 사고가 난다.
형식주의의 유산. 힐베르트 학파가 “이의 없이 받아들일 수 있는 유한적 추론”의 후보로 잡은 것이 원시재귀 산술(PRA)이었다. 겐첸이 1936년 페아노 산술의 무모순성을 PRA + $\varepsilon_0$ 까지의 초한귀납으로 증명한 것이 그 프로그램의 마지막 형태다. 오늘날 증명 보조기의 신뢰 기반 논의가 “커널을 얼마나 작게 만들 것인가”로 굴러가는 것은 그 문제의식의 후손이다.

8. 여담

아커만 함수가 반례로서 특별한 이유는 자연스럽기 때문이다. 대각화로 만든 $d(n)=f_n(n)+1$ 은 “원시재귀가 아니도록 일부러 설계된” 물건이라 누구도 감동하지 않는다. 반면 아커만은 덧셈→곱셈→거듭제곱이라는 누구나 아는 사다리를 한 칸씩 올라가는 함수이고, 그게 밖으로 튀어나간다.
이 개념의 이름이 오해를 부른다. “원시(primitive)“는 원초적·단순하다는 뜻이지 열등하다는 뜻이 아니고, “재귀(recursive)“는 1930년대 어휘라 오늘날의 “계산 가능”에 가깝다. 그래서 옛 문헌의 “일반재귀 함수(general recursive function)“는 재귀를 일반적으로 쓴다는 뜻이 아니라 계산 가능한 전체함수를 가리킨다.
원시재귀 함수를 전부 열거할 수 있다는 사실 자체가 꽤 킹받는 성질이다. 프로그램을 나열할 수 있으면서 그 프로그램들이 전부 정지한다면, 대각선은 언제나 밖에 있다. “모든 프로그램이 정지하는 언어”는 필연적으로 불완전하다는 것이 이 논증의 일반형이고, 전종료 언어를 설계할 때마다 재발견된다.

9. 관련 문서

이 제약이 얼마나 빡센지는 C의 for 와 비교하면 드러난다. for (i=0; i<n; i++) 는 몸통에서 n 이나 i 를 건드리면 언제 끝날지 모르게 되므로 LOOP 문이 아니라 사실상 while 이다. 진짜 LOOP 는 파이썬의 for i in range(n) 처럼 반복자를 진입할 때 확정하고 몸통이 못 건드리는 형태다. 그러니까 “나는 while 을 안 쓰니까 안전하다”는 주장은 그 for 문이 어느 쪽인지에 달려 있다. ↩
이 논증이 성립하려면 ” $f_n$ 을 나열하는 일”과 ” $f_n(n)$ 을 계산하는 일”이 둘 다 기계적으로 가능해야 한다. 원시재귀 함수의 기술은 유한한 구문 트리라 나열이 되고, 그 트리를 해석하는 범용 계산기는 원시재귀가 아니지만(당연하다) 계산 가능하기는 하다. 이 미묘함이 증명의 전부이고, 학부 강의에서 학생이 가장 자주 미끄러지는 지점이기도 하다. ↩
여기에 재미있는 반전이 있다. 괴델의 체계 T는 고차 타입에서의 원시재귀를 허용하는데, 이렇게 하면 아커만 함수가 정의된다. 자연수 위에서는 원시재귀가 아커만을 못 담지만, 함수를 반환하는 함수 층위로 올라가면 담긴다는 뜻. “원시재귀”라는 울타리가 타입 층위에 따라 위치를 바꾼다는 점에서, 증명 보조기의 정지성 검사기가 생각보다 넉넉한 것도 같은 이유다. ↩

이 문서가 문제를 푸는 데 도움이 됐나요? 한 번의 클릭이 다음 검수 순서를 정합니다.

의견을 반영할게요. 감사합니다.

다음으로 읽기 NP-완전 약 5분 더 탐색 →