아커만 함수

계산 가능성 이론에서, 빌헬름 아커만의 이름을 딴 아커만 함수(Ackermann函數, 영어: Ackermann function)는 원시 재귀 함수가 아닌 전역적인 재귀 함수(계산가능 함수)의 가장 간단한 예시로, 가장 먼저 발견된 것이기도 하다. 모든 원시 재귀 함수는 완전히 정의되고 계산 가능하지만 아커만 함수는 모든 전역적 재귀 함수가 원시 재귀 함수일 필요는 없다는 것을 보였다.

음이 아닌 정수 세 개를 변수로 가지는 아커만 함수에 대한 아커만의 출간물 이후 많은 저자들은 다양한 목적에 따라서 이 함수를 수정하였다. 따라서 오늘날 "아커만 함수"라고 하면 오리지날 함수의 수많은 변형 중 하나를 의미하는 것이다. 일반적인 변형의 일종으로서, 변수가 두 개인 아커만-페테르 함수(영어: Ackermann–Péter function)는 음이 아닌 정수 m과 n에 대해 다음과 같이 정의된다.

$A(m,n)={\begin{cases}n+1&{\mbox{if }}m=0\\A(m-1,1)&{\mbox{if }}m>0{\mbox{ and }}n=0\\A(m-1,A(m,n-1))&{\mbox{if }}m>0{\mbox{ and }}n>0.\end{cases}}$

이 값은 입력이 작더라도 매우 빠르게 증가한다. 예를 들면, A(4,2)는 2⁶⁵⁵³⁶-3으로서, 19,729자리의 정수이다.

역사

1920년 말에 다비트 힐베르트(David Hilbert)의 제자인 수학자 가브리엘 수단(Gabriel Sudan)과 빌헬름 아커만(Wilhelm Ackermann)은 계산의 기초를 연구하고 있었다. 수단과 아커만은 둘 다 원시 재귀 함수가 아닌 완전히 정의된 계산 가능 함수 (어떤 문헌에서는 단순히 "재귀적"으로 표현한다)를 발견한 것으로 인정된다. 수단은 덜 알려진 수단 함수를 발표하였고, 그 직후 1928년에 아커만은 독립적으로 그의 함수 $\varphi$ (그리스 문자 Φ)를 발표하였다. 아커만의 3변수 함수 $\varphi (m,n,p)$는 p = 0, 1, 2일 때, 이 함수는 다음과 같은 기본적인 연산(덧셈, 곱셈, 거듭제곱)를 나타낸다.

$\varphi (m,n,0)=m+n,$

$\varphi (m,n,1)=m\cdot n,$

$\varphi (m,n,2)=m^{n},$

그리고 p > 2이면 이 함수는 이 기본 연산을 하이퍼 연산과 비교할 수 있게 확장한다. (이 함수의 원시 재귀 함수가 아닌 완전히 정의된 계산 가능 함수로서의 역사적 역할을 제외하고, 아커만의 오리지날 함수는 그런 목적으로 특별히 고안된 아커만의 함수(예:굿스타인의 하이퍼 연산 수열)처럼 완벽하지는 않지만 기본 산술 연산에서 거듭 제곱을 넘어서 확장한 것으로 볼 수 있다.)

On the Infinite에서, 다비트 힐베르트는 아커만 함수는 원시 재귀 함수가 아니라는 가설을 세웠지만 그 가설을 증명한 사람은 힐베르트의 개인 비서이자 전 학생이였던 에크만으로 그의 논문 On Hilbert’s Construction of the Real Numbers에서 증명하였다.

로저 페테르(Rózsa Péter)와 라파엘 로빈슨(Raphael Robinson)은 이후에 많은 저자들이 선호하는 아커만 함수의 2변수 버전을 만들었다.

정의와 특성

아커만의 오리지날 3변수 함수 $\varphi (m,n,p)$는 다음 음이 아닌 정수 m, n, 그리고 p에 따라 재귀적으로 정의되었다.

${\begin{array}{lr}\varphi (m,n,0)=m+n\\\varphi (m,0,1)=0\\\varphi (m,0,2)=1\\\varphi (m,0,p)=m{\text{ for }}p>2\\\varphi (m,n,p)=\varphi (m,\varphi (m,n-1,p),p-1){\text{ for }}n>0,p>0.\end{array}}$

다양한 2변수 버전 중에서, 페테르와 로빈슨이 만든 것(많은 사람들이 말하는 "그" 아커만 함수이다)은 음이 아닌 정수 m과 n으로 다음과 같이 정의되어 있다.

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

이것을 보자마자 $A(m,n)$이 항상 끝난다는 것을 명백하게 알 수 없다. 하지만, 각각의 재귀적인 적용에서 m이 줄어들거나 m은 그대로고 n이 감소하기 때문에 재귀는 끝이 있다. n이 0에 도달할 때마다 m이 줄어들어 m은 결국에는 0에 도달한다. (더 기술적으로 표현하자면, 각각의 경우에 (m, n)의 쌍은 사전식 순서대로 줄어들어 음이 아닌 단일 정수를 정렬하는 것처럼 정렬 순서가 된다. 즉, 정렬을 무한히 많이 수행하며 내려갈 수 없다는 것을 의미한다.) 하지만, m이 감소할 때 n이 늘어나는 상한이 없기 때문에 매우 커질 수 있다.

페테르-아커만 함수는 다양한 다른 아커만 함수의 용어로 표현될 수 있다.

• 색인된 버전의 커누스 윗화살표 표기법 (정수가 표현하는 범위 ≥ -2로 확장 되었다):

$A(m,n)=2\uparrow ^{m-2}(n+3)-3.$

정의 중 A(m, 0) = A(m-1, 1)이라는 부분은 $2\uparrow ^{m+1}3=2\uparrow ^{m}4$에 대응된다

• 콘웨이 연쇄 화살표 표기법:

$A(m,n)=(2\rightarrow (n+3)\rightarrow (m-2))-3$ for $m\geq 3$

따라서

$2\rightarrow n\rightarrow m=A(m+2,n-3)+3$ for $n>2$.

(n=1과 n=2 일 때는 논리적으로 A(m,−2) = −1과 A(m,−1) = 1에 대응되도록 추가할 수 있다.)

m이 1, 2, 또는 3처럼 작은 값일 때, 아커만 함수는 n에 대해서 상대적으로 천천히 증가한다(기껏해야 지수적으로). 하지만 m ≥ 4일 때는 매우 빠르게 증가한다. 심지어 A(4, 2)만 해도 약 2×10^¹⁹⁷²⁸이고, A(4, 3)를 풀어쓰면 어떤 전통적인 표기로 써도 매우 크다.

아커만 함수의 한 흥미로운 양상은 이것이 쓰는 유일한 산술적인 연산은 덧셈과 1을 빼는 것 뿐이다. 이 특성은 무한한 재귀의 지수에서만 온 것이다. 또한 수행 시간이 적어도 그 결과에 비례하다는 것을 암시하기 때문에, 마찬가지로 매우 거대하다. 실제로는 대부분의 경우에 수행 시간은 결과보다 크다.

m 과 n이 동시에 증가하는 단일 변수 버전 f(n) = A(n, n)는 모든 원시 재귀 함수를 뛰어넘는다. 그중에는 지수 함수, 팩토리얼 함수, 다중 팩토리얼 과 초팩토리얼 함수, 심지어는 커누스 윗화살표 표기법으로 정의된 함수(윗화살표에 지수를 사용하는 경우를 제외하고)와 같이 매우 빠르게 증가하는 함수를 포함한다. f(n)는 대략적으로 빠르게 증가하는 계급의 f_ω(n)와 비교 가능하다고 볼 수 있다. 이 극한의 증가는 튜링 기계와 같이 무한한 메모리를 가지는 기계에서 명백히 계산 가능하고 따라서 계산 가능 함수인 f가 다른 어떤 원시 재귀 함수보다 빠르게 증가하기 때문에 원시 재귀함수가 아니라는 것을 보일 때 쓰인다.

거듭제곱들의 범주에서, 동형 사상 $((X\times Y)\rightarrow Z)\cong (X\rightarrow (Y\rightarrow Z))$ (컴퓨터 과학에서는 커링이라고 부른다)을 사용하면, 아커만 함수는 다음의 높은 차수의 범함수에서 원시 재귀 함수를 통해 정의할 수 있다.

${\begin{array}{lcl}\operatorname {Ack} (0)&=&\operatorname {Succ} \\\operatorname {Ack} (m+1)&=&\operatorname {Iter} (\operatorname {Ack} (m))\end{array}}$

여기서 Succ(n) = n + 1는 보통의 다음수 함수이고 Iter는 다음과 같이 원시 재귀로 정의된 함수의 거듭제곱 연산을 나타낸다.

${\begin{array}{lcl}\operatorname {Iter} (f)(0)&=&f(1)\\\operatorname {Iter} (f)(n+1)&=&f(\operatorname {Iter} (f)(n)).\end{array}}$

이렇게 정의된 함수 $\mathrm {Ack}$는 위에서 정의한 아커만 함수 $A$와 동일하다: $\mathrm {Ack} (m)(n)=A(m,n)$.

예시

아커만 함수가 어떻게 매우 빠르게 커지는지를 보기 위해서는 간단한 표현을 오리지날 정의의 규칙에 따라서 확장하는 것이 도움이 된다. 예를 들어, $A(1,2)$를 다음과 같이 완전히 계산할 수 있다:

${\begin{aligned}A(1,2)&=A(0,A(1,1))\\&=A(0,A(0,A(1,0)))\\&=A(0,A(0,A(0,1)))\\&=A(0,A(0,2))\\&=A(0,3)\\&=4.\end{aligned}}$

아래는 $A(4,3)$의 계산이 어떻게 해서 많은 단계를 거치고 큰 수가 나오는지를 입증하기 위한 것이다.

${\begin{aligned}A(4,3)&=A(3,A(4,2))\\&=A(3,A(3,A(4,1)))\\&=A(3,A(3,A(3,A(4,0))))\\&=A(3,A(3,A(3,A(3,1))))\\&=A(3,A(3,A(3,A(2,A(3,0)))))\\&=A(3,A(3,A(3,A(2,A(2,1)))))\\&=A(3,A(3,A(3,A(2,A(1,A(2,0))))))\\&=A(3,A(3,A(3,A(2,A(1,A(1,1))))))\\&=A(3,A(3,A(3,A(2,A(1,A(0,A(1,0)))))))\\&=A(3,A(3,A(3,A(2,A(1,A(0,A(0,1)))))))\\&=A(3,A(3,A(3,A(2,A(1,A(0,2))))))\\&=A(3,A(3,A(3,A(2,A(1,3)))))\\&=A(3,A(3,A(3,A(2,A(0,A(1,2))))))\\&=A(3,A(3,A(3,A(2,A(0,A(0,A(1,1)))))))\\&=A(3,A(3,A(3,A(2,A(0,A(0,A(0,A(1,0))))))))\\&=A(3,A(3,A(3,A(2,A(0,A(0,A(0,A(0,1))))))))\\&=A(3,A(3,A(3,A(2,A(0,A(0,A(0,2)))))))\\&=A(3,A(3,A(3,A(2,A(0,A(0,3))))))\\&=A(3,A(3,A(3,A(2,A(0,4)))))\\&=A(3,A(3,A(3,A(2,5))))\\&=\ldots \\&=A(3,A(3,A(3,13)))\\&=\ldots \\&=A(3,A(3,65533))\\&=\ldots \\&=A(3,2^{65536}-3)\\&=\ldots \\&=2^{2^{\overset {65536}{}}}-3.\\\end{aligned}}$

값들의 표

아커만 함수를 계산한 것은 무한한 표에 쓸 수 있다. 가장 윗 행을 따라 자연수를 놓고. 표의 값을 결정하기 위해서는 수를 한 칸 왼쪽으로 가져가고, 이전 행에서 방금 그 수의 자리에 있는 수를 찾는다. 왼쪽에 수가 없을 때는 단순히 이전 행에서 "1"로 시작하는 열을 보라. 다음은 표의 왼쪽 상부의 일부이다.

A(m, n)의 값

m＼n	0	1	2	3	4	n
0	1	2	3	4	5	$n+1$
1	2	3	4	5	6	$n+2=2+(n+3)-3$
2	3	5	7	9	11	$2n+3=2\cdot (n+3)-3$
3	5	13	29	61	125	$2^{(n+3)}-3$
4	13 =${2^{2^{2}}}-3$	65533 =${2^{2^{2^{2}}}}-3$	265536 − 3 =${2^{2^{2^{2^{2}}}}}-3$	${2^{2^{65536}}}-3$ =${2^{2^{2^{2^{2^{2}}}}}}-3$	${2^{2^{2^{65536}}}}-3$ =${2^{2^{2^{2^{2^{2^{2}}}}}}}-3$	${\begin{matrix}\underbrace {{2^{2}}^{{\cdot }^{{\cdot }^{{\cdot }^{2}}}}} _{n+3}-3\end{matrix}}$
5	65533 =$2\uparrow \uparrow \uparrow 3-3$	$2\uparrow \uparrow \uparrow 4-3$	$2\uparrow \uparrow \uparrow 5-3$	$2\uparrow \uparrow \uparrow 6-3$	$2\uparrow \uparrow \uparrow 7-3$	$2\uparrow \uparrow \uparrow (n+3)-3$
6	$2\uparrow \uparrow \uparrow \uparrow 3-3$	$2\uparrow \uparrow \uparrow \uparrow 4-3$	$2\uparrow \uparrow \uparrow \uparrow 5-3$	$2\uparrow \uparrow \uparrow \uparrow 6-3$	$2\uparrow \uparrow \uparrow \uparrow 7-3$	$2\uparrow \uparrow \uparrow \uparrow (n+3)-3$

여기에서 재귀적 지수나 커누스 윗화살표 표기법으로 나타낸 수는 너무 크기 때문에 일반적인 십진법으로 쓰기에는 공간을 너무 차지한다.

이 표의 앞부분의 큰 수나 나타남에도 불구하고, 그레이엄 수 같이 작은 개수의 커누스 윗화살표로도 표현할 수 없는 큰 수가 더 많이 정의되어 있다. 이 수는 아커만 함수를 재귀적으로 적용하는 것과 비슷하게 만들어진다.

아래는 위의 표를 반복한 것이지만, 패턴을 명확하게 보이기 위해서 값들을 함수의 정의와 관련된 표현으로 바꿔 적었다.

A(m, n)의 값

m＼n	0	1	2	3	4	n
0	0+1	1+1	2+1	3+1	4+1	$n+1$
1	A(0, 1)	A(0, A(1, 0)) = A(0, 2)	A(0, A(1, 1)) = A(0, 3)	A(0, A(1, 2)) = A(0, 4)	A(0, A(1, 3)) = A(0, 5)	A(0, A(1, n-1))
2	A(1, 1)	A(1, A(2, 0)) = A(1, 3)	A(1, A(2, 1)) = A(1, 5)	A(1, A(2, 2)) = A(1, 7)	A(1, A(2, 3)) = A(1, 9)	A(1, A(2, n-1))
3	A(2, 1)	A(2, A(3, 0)) = A(2, 5)	A(2, A(3, 1)) = A(2, 13)	A(2, A(3, 2)) = A(2, 29)	A(2, A(3, 3)) = A(2, 61)	A(2, A(3, n-1))
4	A(3, 1)	A(3, A(4, 0)) = A(3, 13)	A(3, A(4, 1)) = A(3, 65533)	A(3, A(4, 2))	A(3, A(4, 3))	A(3, A(4, n-1))
5	A(4, 1)	A(4, A(5, 0))	A(4, A(5, 1))	A(4, A(5, 2))	A(4, A(5, 3))	A(4, A(5, n-1))
6	A(5, 1)	A(5, A(6, 0))	A(5, A(6, 1))	A(5, A(6, 2))	A(5, A(6, 3))	A(5, A(6, n-1))

아커만 함수가 원시 재귀 함수가 아니라는 것에 대한 증명

어떤 면에서, 아커만 함수는 다른 어떤 원시 재귀 함수보다 빠르게 증가하고 따라서 원시 재귀함수가 아니다.

특히, 모든 원시 재귀 함수 $f(x_{1},\ldots ,x_{n})$에 대해서 모든 음이 아닌 정수 $x_{1},\ldots ,x_{n}$에 대해 다음이 성립하는 음이 아닌 정수 $t$가 존재한다는 것을 보여준다.

$$f(x_{1},\ldots ,x_{n})<A(t,\mathrm {max} _{i}x_{i})$$

이것이 확립되면, $A$ 자신은 원시 재귀함수가 아니라는 것은 자명하다. 왜냐하면 만약 그렇지 않다면 $x_{1}=x_{2}=t$일 때 $A(t,t)<A(t,t)$가 되어서 모순이 발생하기 때문이다.

이 증명은 다음과 같은 과정을 거친다: 아커만 함수보다 더 느리게 증가하는 모든 함수들의 분류${\mathcal {A}}$를 정의한다.

$${\mathcal {A}}=\left\{f\mid \exists t\ \forall x_{1}\cdots \forall x_{n}:\ f(x_{1},\ldots ,x_{n})<A(t,\mathrm {max} _{i}x_{i})\right\}$$

그리고 ${\mathcal {A}}$가 모든 원시 재귀 함수를 포함하고 있다는 것을 보인다. 후자는 ${\mathcal {A}}$가 상수 함수, 다음수 함수, 투영 함수를 포함하고 함수 합성과 원시 재귀의 연산에서 닫혀 있다는 것을 증명하면 성립한다.

역함수

함수  f (n) = A(n, n)는 위에서 매우 급하게 증가하는 것으로 고려하기 때문에, 그 역함수 f⁻¹는 매우 느리게 증가한다. 이 역 아커만 함수 f⁻¹는 일반적으로 α로 표기한다. 사실, A(4, 4)는 $2^{2^{2^{2^{16}}}}$차이기 때문에 α(n)은 모든 실제 입력 크기 n에 대해서 5보다 작다.

이 역함수는 서로소 집합 자료 구조와 최소 신장 트리에 대한 채즐(Bernard Chazelle)의 알고리즘과 같은 알고리즘의 시간 복잡도에서 나타난다. 때때로 아커만의 원래 함수나 다른 변형은 이 설정에 쓰이나 모두 비슷하게 빠른 비율로 증가한다. 특히, 어떤 수정된 함수는 식에서 −3과 비슷한 항을 제거해서 단순하게 수정했다.

역 아커만 함수의 2변수 변형은 다음과 같이 정의할 수 있다. 여기서 $\lfloor x\rfloor$는 바닥 함수이다:

$\alpha (m,n)=\min\{i\geq 1:A(i,\lfloor m/n\rfloor )\geq \log _{2}n\}.$

이 함수는 위에서 언급한 알고리즘을 더 정확하게 분석 할 때 나타나고 더 제한된 시간 경계를 얻는다. 서로소 집합 자료 구조에서, m은 연산의 숫자를 나타내고 n은 원소의 개수를 나타낸다. 최소 신장 트리에서, m은 변의 개수를 나타내고 n은 꼭짓점의 개수를 나타낸다. 몇몇 약간 다른 α(m, n)의 정의가 있다. 예를 들어, log₂ n은 종종 n으로 바뀌고 바닥 함수는 종종 천장 함수로 바뀐다.

다른 연구에서는 m이 상수로 정해져서 특정한 행의 역함수로 정의할 수도 있다.

벤치마크로 사용

그 정의 때문에 극한으로 깊은 재귀 때문에 아커만 함수는 컴파일러의 재귀를 최적화하는 능력을 테스트 하는데 사용할 수 있다. 아커만의 함수를 이렇게 사용하는 것은 1971년에 윙베 순드블라드(Yngve Sundblad)가 처음으로 출간하였다.

순드블라드의 세미나 논문은 1975년에서 1982년까지의 3부작 논문에서 브라이언 위치만(Brian Wichmann, 헤트스톤 벤치마크(Whetstone benchmark)의 공저자)에 의해 채택되었다.

같이 보기

• 계산 가능성 이론
• 재귀함수
• 원시 재귀 함수
• 그제고르치크 위계
• 굿스타인 함수

외부 링크

• “Ackermann function”. 《Encyclopedia of Mathematics》 (영어). Springer-Verlag. 2001. ISBN 978-1-55608-010-4. 
• Weisstein, Eric Wolfgang. “Ackermann function”. 《Wolfram MathWorld》 (영어). Wolfram Research. 
•  이 문서는 다음을 포함합니다: 퍼블릭 도메인 자료 출처: NIST 문서: Black, Paul E. “Ackermann's function”. 《Dictionary of Algorithms and Data Structures》. 
• An animated Ackermann function calculator
• Scott Aaronson, Who can name the biggest number? (1999)
• Ackermann functions. Includes a table of some values.
• Hyper-operations: Ackermann's Function and New Arithmetical Operation
• Robert Munafo's Large Numbers describes several variations on the definition of A.
• Gabriel Nivasch, Inverse Ackermann without pain on the inverse Ackermann function.
• Raimund Seidel, Understanding the inverse Ackermann function (PDF presentation).
• The Ackermann function written in different programming languages, (on Rosetta Code)
• Ackermann's Function( 2009-10-24)—Some study and programming by Harry J. Smith.