[Tech, etc.] Ackermann function(아커만 함수)

 계산 가능성 이론에 따르면 아커만 함수는 빌헬름 아커만(Wilhelm Ackermann)의 이름을 딴 함수로, 가장 간단하고 먼저 발견된 완전 계산 가능(total computable function) 함수이며 비원시 귀납 함수(not primitive recursive function)이다. 모든 원시 귀납 함수는 완전(total)하고 계산 가능하지만, 아커만 함수는 모든 완전 계산 가능 함수가 원시 재귀 함수는 아니라는 것을 설명한다. 아커만의 발표 이후, 3개의 음수가 아닌 정수를 인자로 갖는 아커만 함수에 대해 많은 사람들이 다양한 목적으로 변형했다. 흔한 예정 하나로는 두 개의 인자를 갖는 아커만 피터 함수(Ackermann-Peter function)이 있는데 음수가 아닌 두 정수 m과 n에 대해 아래와 같이 정의한다.

 아커만 함수의 극도로 깊은 재귀 성질 때문에 컴파일러의 재귀 최적화 성능 벤치마크를 측정하는 데 사용된다.

 

직접 숫자를 대입해보면 아래와 같다.

 

참조

- https://en.wikipedia.org/wiki/Ackermann_function