애커만 함수

에커만 함수(Ackermann函數)는 음이 아닌 정수 $m$ 과 $n$ 에 대해

${\rm Ack}(m, n) = \begin{cases} n + 1, & \mbox{ if }m = 0\\ {\rm Ack}(m - 1, 1), & \mbox{ if }n = 0\\ {\rm Ack}(m - 1, {\rm Ack}(m, n - 1)), & \mbox{ otherwise}\\ \end{cases}$

로 정의되는 함수이다.

$m$ 과 $n$ 이 커질수록 계산량이 폭발적으로 늘어나는 특징이 있어 기기의 성능측정 등에 사용되는 경우가 있다.

또한, ${\rm Ack}(m, n) = \begin{cases} 2n, & \mbox{ if }m = 0 \\ 0, & \mbox{ if }m>= 1, n=0 \\ 2, & \mbox{ if }m>= 1, n=1 \\ {\rm Ack}(m - 1, {\rm Ack}(m, n - 1)), & \mbox{ otherwise }m>=1, n>=2\\ \end{cases}$

로 표현하기도 한다.