아커만 함수

수치해석 소프트웨어 마지막 수정: 2026-09-06 04:51:30

1. 개요[편집]

아커만 함수 Ackermann Function
정의	$A(0,n)=n+1$ · $A(m,0)=A(m-1,1)$ · $A(m,n)=A(m-1,A(m,n-1))$
역사적 의의	전역 계산가능하지만 원시재귀가 아닌 최초의 함수
발표	Ackermann (1928) · 2변수 형태는 Péter·Robinson
증가 속도	$A(4,2)=2^{65536}-3$ — 19,729 자리
실무 등장	역함수 $\alpha(n)$ 이 유니온-파인드 상각 복잡도에
실용 감각	현실의 모든 $n$ 에 대해 $\alpha(n)\le 4$

함수 하나가 수학사에 남으려면 보통 유용해야 한다. 이 함수는 아무 쓸모가 없다는 방식으로 남았다.

아커만 함수(Ackermann function)는 전역적으로 정의된 계산 가능한 함수이면서 원시재귀적(primitive recursive)이 아닌 최초의 예시로, 1928년 빌헬름 아커만이 제시했다. 오늘날 표준으로 쓰이는 2변수 형태(아커만–페테르 함수)는 이렇게 정의된다.

A(m,n) = \begin{cases} n+1 & m=0 \\ A(m-1,\,1) & m>0,\ n=0 \\ A(m-1,\,A(m,\,n-1)) & m>0,\ n>0 \end{cases}

세 줄이 전부고, 어떤 $(m,n)$ 에서든 유한 번에 끝난다는 것도 어렵지 않게 보일 수 있다. 그런데 이 세 줄이 “계산 가능하다”와 “for 문으로 계산 가능하다”가 다른 개념임을 증명하는 데 쓰였고, 그 역함수는 유니온-파인드의 복잡도 표에 붙박이로 앉아 있다. 이론 컴퓨터과학의 어휘가 실무 자료구조에 침투한 몇 안 되는 사례다.

2. 왜 만들어졌나 — 힐베르트의 추측을 깨기 위해[편집]

1920년대 사람들이 갖고 있던 “계산 가능한 함수”의 후보는 **원시재귀 함수**였다. 기본 함수(0, 후속자, 사영)에서 시작해 합성과 원시재귀(하나의 매개변수를 1씩 줄여 가는 재귀)만으로 만들 수 있는 함수들이며, 덧셈·곱셈·거듭제곱·소수 판정 등 실제로 쓰는 것 거의 전부가 여기 들어간다.

프로그래밍 언어로 번역하면 정체가 선명해진다. 원시재귀 = 반복 횟수가 미리 정해진 for 문만으로 짜는 프로그램이다. while 문은 언제 끝날지 모르므로 여기 없다. 원시재귀 함수는 정의상 전부 정지하고, 그래서 안전하다.

힐베르트를 비롯한 여러 사람이 “계산 가능한 함수는 전부 원시재귀적일 것”이라 추측했는데, 아커만이 이를 깼다. 그가 만든 것은 덧셈 → 곱셈 → 거듭제곱 → 그 위 로 이어지는 연산 계층을 하나의 함수 안에 넣은 것이었고, 원래 논문의 함수는 3변수 $\varphi(m,n,p)$ 형태였다. 지금 쓰는 2변수 축약형은 로자 페테르와 라파엘 로빈슨이 다듬은 것이다.¹

3. 값이 얼마나 커지는가[편집]

$m$ 을 고정하면 닫힌 형태가 나온다. 귀납법으로 어렵지 않게 확인된다.

$m$	$A(m,n)$	정체
0	$n+1$	후속자
1	$n+2$	덧셈
2	$2n+3$	곱셈
3	$2^{\,n+3}-3$	거듭제곱
4	$2\uparrow\uparrow(n+3)-3$	거듭제곱 탑

$m$ 이 1 늘어날 때마다 연산의 층위 자체가 한 칸 올라간다. 크누스 위 화살표로 쓰면 $A(m,n)$ 은 대략 $2\uparrow^{m-2}(n+3)-3$ 이고, 하이퍼연산 계층을 그대로 걸어 올라가는 함수다.

$m=4$ 부터 손을 놓게 된다.

$A(4,0) = 2^{2^2}-3 = 13$
$A(4,1) = 2^{16}-3 = 65533$
$A(4,2) = 2^{65536}-3$ — 십진수로 19,729자리
$A(4,3) = 2^{2^{65536}}-3$ — 자릿수 자체가 19,729자리 수

$A(5,\cdot)$ 은 표기법을 바꾸지 않으면 쓸 수조차 없다. 그리고 이것이 이 함수의 요점이다 — 폭발이 취향이 아니라 정리의 내용이다.

4. 원시재귀가 아님 — 증명의 뼈대[편집]

핵심 명제는 하나다.

임의의 원시재귀 함수 $f$ 에 대해, 어떤 상수 $m$ 이 존재해 모든 $n$ 에 대해 $f(n) < A(m,n)$ 이다.

증명은 원시재귀 함수의 구성 방식을 따라가는 구조적 귀납이다. 기본 함수는 $A(0,\cdot)$ 이나 $A(1,\cdot)$ 로 쉽게 눌리고, 합성과 원시재귀 각각에 대해 ” $A(m,\cdot)$ 로 눌리는 함수들로 만든 새 함수는 $A(m+1,\cdot)$ 로 눌린다” 를 보인다. 여기에 필요한 것이 $A$ 의 단조성과 $A(m,A(m,n)) \le A(m+1,n+c)$ 류의 부등식들이고, 이 준비가 증명 분량의 대부분을 차지한다.

명제가 서면 결론은 대각선 논법 한 줄이다. $g(n) = A(n,n)$ 이 원시재귀라고 가정하면 어떤 $m$ 에 대해 $A(n,n) < A(m,n)$ 이 모든 $n$ 에서 성립해야 하는데, $n=m$ 을 넣으면 $A(m,m) < A(m,m)$ 이라는 모순이다. 그런데 $g$ 는 명백히 계산 가능하고 모든 입력에서 정지한다. 따라서 계산 가능 ⊋ 원시재귀.

프로그래밍 언어의 언어로 다시 말하면 이렇다. for 문만으로는 못 짜지만 while 문으로는 짤 수 있는 함수가 존재한다. 반복 횟수를 미리 알 수 있는 프로그램만 허용하는 언어는 정지성이 보장되는 대신 표현력을 잃는다는 뜻이고, 이는 오늘날 전종료(total) 언어 설계에서 그대로 되풀이되는 트레이드오프다. 계산 가능성의 전체 지형은 튜링 기계·NP-완전 쪽 문서를 참고.

한 가지 오해를 짚어 두자. 아커만 함수는 정지 문제와 다르다. 이것은 모든 입력에서 정지하고 계산 가능하다. “원시재귀가 아니다”는 못 계산한다는 뜻이 아니라 정해진 횟수의 루프로는 못 계산한다는 뜻이다.

5. 벤치마크로서의 인생[편집]

전역적이면서 원시재귀가 아니라는 성질은, 프로그래밍 관점에서는 재귀를 for 문으로 못 바꾼다로 번역된다. 그래서 이 함수는 1970년대부터 컴파일러와 런타임의 재귀 처리 능력을 재는 표준 시험지로 쓰였다. 순드블라드(1971)의 연구가 이 용법을 정착시켰고, 이후 언어 비교 벤치마크에 단골로 등장했다.

무엇을 재는가가 재미있다. 아커만 함수의 재귀는 꼬리재귀가 아니다. $A(m-1, A(m,n-1))$ 에서 안쪽 호출의 결과가 바깥 호출의 인자로 들어가므로 반복문으로 기계적 변환이 안 되고, 호출 스택이 실제로 깊게 쌓인다. 따라서 이 벤치마크가 측정하는 것은 산술 성능이 아니라 함수 호출 오버헤드와 스택 처리 비용이다. 값이 작아도 호출은 폭발한다 — $A(3,6)$ 은 결과가 509에 불과한데 재귀 호출이 172,233번이고, $A(3,7)$ 은 결과 1021에 호출 693,964번이다. 값이 두 배가 될 때 호출이 네 배가 되는 구조라, 언어·컴파일러 간 차이가 선명하게 드러난다.

실제로 돌릴 때의 요령도 몇 가지 있다.

깊이가 값보다 먼저 죽인다. $A(3,n)$ 은 값 자체가 $2^{n+3}-3$ 으로 얌전한데 재귀 깊이가 그 값에 비례해 자란다. $A(3,13)$ 이면 중첩 호출이 6만 5천 겹이고, 인터프리터의 재귀 한계나 기본 스택 크기가 대개 이 근처에서 먼저 항복한다.
메모이제이션이 극적으로 듣는다. 같은 $(m,n)$ 이 엄청나게 많이 재방문되므로 캐시 한 줄이 몇 자릿수를 줄인다. 다만 $m\ge4$ 에서는 인자 자체가 거대해져 캐시 키가 감당이 안 된다.
$m\le3$ 은 닫힌 형태로 잘라낸다. 위 표의 공식을 그대로 넣으면 재귀가 $m=4$ 층에서만 돌아 실용적으로 계산 가능한 범위가 훨씬 넓어진다. 이 최적화를 넣는 순간 벤치마크로서의 의미는 사라지지만.
임의정밀도 산술이 필요하다. $A(4,2)$ 를 정직하게 얻으려면 19,729자리 정수를 다뤄야 한다. 64비트 정수로 짠 구현은 조용히 오버플로한다.²

6. 역아커만 함수 — 실무에 나타나는 쪽[편집]

정작 이 바닥 사람들이 아커만을 만나는 자리는 함수 자체가 아니라 역함수다. 대각선 $A(n,n)$ 이 상상을 초월하게 빨리 커지므로, 그 역함수

\alpha(n) = \min\{\,m : A(m,m) \ge n\,\}

는 상상을 초월하게 천천히 커진다. 얼마나 천천히인지는 값을 보면 안다.

$n$ 의 범위	$\alpha(n)$
$2 \le n \le 3$	1
$4 \le n \le 7$	2
$8 \le n \le 61$	3
$62 \le n < A(4,4)$	4

마지막 줄이 결론이다. $A(4,4) = 2\uparrow\uparrow 7 - 3$ 은 2의 거듭제곱 탑이 일곱 층이라, 관측 가능한 우주의 원자 수 $10^{80}$ 은 그 앞에서 반올림 오차도 못 된다. 어떤 실제 입력에 대해서도 $\alpha(n)\le4$ 이고, 그래서 복잡도 표의 $\alpha$ 는 실무적으로 상수다. 다만 수학적으로는 상수가 아니라 발산하는 함수이며, 이 구별이 하한 증명에서 결정적으로 작동한다.

타잔의 분석에서는 두 변수 버전 $\alpha(m,n)$ 이 쓰인다. 원소 $n$ 개에 연산 $m$ 개일 때 연산당 밀도가 높으면 더 빨리 상수에 가까워지는 것을 반영한 것으로, 세부 정의는 문헌마다 조금씩 다르지만 어떤 정의를 써도 실용 범위에서 4 이하라는 결론은 같다.

7. $\alpha$ 가 나오는 자리들[편집]

유니온-파인드. 경로 압축 + 랭크 합치기의 상각 비용이 $\Theta(m\,\alpha(m,n))$ 이다(타잔 1975). 여기서 중요한 것은 이것이 상한일 뿐 아니라 하한이기도 하다는 점 — 즉 더 좋은 자료구조를 찾는 것이 불가능하다. 프레드먼과 삭스(1989)가 셀 프로브 모형에서 하한을 확립하면서 ” $\alpha$ 는 알고리즘의 한계가 아니라 문제의 난이도”임이 확정됐다.
최소 신장 트리 검증과 계산. 주어진 신장 트리가 최소인지 선형 시간에 검증할 수 있다는 결과가 유니온-파인드 계열 기법 위에 서 있고, 샤젤(2000)의 결정적 MST 알고리즘은 $O(m\,\alpha(m,n))$ 으로 돈다. 결정적 알고리즘으로 알려진 최선이며, MST가 선형 시간에 풀리는지는 여전히 미해결이다.
다벤포트–신첼 수열. 서로 다른 함수 $n$ 개의 하한 포락선(lower envelope)의 조각 수가 $\Theta(n\,\alpha(n))$ 이다. 선형이 아니라 아주 조금 초선형이라는 이 결과가 계산기하의 여러 자료구조 크기를 지배한다. 여기서는 $\alpha$ 가 상한뿐 아니라 하한에도 나오므로 “사실상 상수”라는 위안조차 반쯤만 유효하다.
오프라인 질의 처리. 타잔의 오프라인 최소 공통 조상 알고리즘, 구간 병합형 질의, 그리고 순차적 병합만 일어나는 여러 오프라인 문제가 유니온-파인드를 통해 $\alpha$ 를 물려받는다.

시뮬레이션 실무자 입장에서 요약하면 이렇다. 퍼콜레이션 클러스터를 세든, 메시 생성 후 연결 성분을 찾든, 적응 격자 세분화에서 블록을 묶든, 뒤에서 굴러가는 상각 비용이 $\alpha$ 다. 그리고 그 $\alpha$ 는 절대 5가 되지 않는다.

8. 여담[편집]

아커만이 이 함수로 무엇을 부순 것인지 다시 보면 감상이 좀 달라진다. 그는 “계산 가능성”이라는 개념이 아직 정의되기도 전에 그 개념의 후보 하나를 반례로 무너뜨렸다. 튜링 기계는 8년 뒤, 처치의 람다 계산은 5년 뒤에 나온다. 개념이 없을 때 그 개념의 경계를 먼저 찾은 것이다.
이 함수는 컴퓨터과학 교육에서 특이한 역할을 한다. “재귀를 배웠으니 짜 봐라”에서 시작해 학생의 노트북을 얼려 놓고, 스택 오버플로와 메모이제이션과 임의정밀도 산술을 한꺼번에 가르친다. $A(4,2)$ 를 출력해 보라는 과제가 컴퓨터과학 통과의례로 돌아다니는 데는 이유가 있다.
반대 방향의 농담도 있다. 알고리즘 논문에서 $\alpha(n)$ 을 상수로 안 놓고 끝까지 끌고 가는 저자를 보면 두 부류다 — 하한이 진짜로 $\alpha$ 인 것을 아는 사람이거나, 정직한 사람이거나. 대개는 둘 다다.
그리고 이 함수가 남긴 가장 실용적인 유산은 아마 이것일 것이다. “거의 상수 시간”이라는 표현이 이 바닥에서 허용되는 근거. 진짜 상수는 아니지만 우주가 끝날 때까지 4를 안 넘으면, 공학적으로는 상수라고 불러도 아무도 안 다친다.³

9. 관련 문서[편집]

거의 잊힌 각주가 하나 있다. 루마니아 수학자 가브리엘 수단이 1927년에 비슷한 목적의 원시재귀 아닌 함수를 먼저 발표했다. 두 사람은 힐베르트 밑에서 같이 공부했고 문제의식도 공유했지만, 오늘날 교과서에 이름이 남은 쪽은 아커만이다. 수단 함수도 여전히 그 이름으로 불리기는 한다 — 아커만 함수를 다루는 논문의 각주 안에서. ↩
이 실패가 특히 짓궂은 이유는 작은 입력에서는 잘 돌기 때문이다. $A(3,10)$ 까지 멀쩡히 맞다가 $A(4,2)$ 에서 조용히 음수나 0이 나온다. 오버플로 검사를 안 켠 C 구현이 “계산이 빨리 끝났네요”라며 틀린 답을 내놓는 장면이 매 학기 재현된다. ↩
물론 이 논리를 남용하면 곤란해진다. ” $\log^* n \le 5$ 니까 상수”, ” $\log n \le 64$ 니까 상수”까지는 그럭저럭 봐줄 만한데, 여기서 한 발 더 가면 ” $n \le 10^9$ 니까 $O(n^2)$ 도 상수”가 나온다. 어디서 멈출지를 아는 것이 공학이고, 멈추지 않는 것이 벤치마크 사기다. ↩