아커만 함수

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

아커만 함수(Ackermann函數, 영어: Ackermann function)는 음이 아닌 정수 mn 에 대해

{\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}

로 정의되는 함수이다.

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

또한, {\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}

로 표현하기도 한다.

역사[편집]

독일의 수학자 빌헬름 아커만(Wilhelm Ackermann)이 1928년 도입하였다.[1]

참고 문헌[편집]

  1. (독일어) Wilhelm Ackermann (1928년). Zum Hilbertschen Aufbau der reellen Zahlen. 《Mathematische Annalen》 99: 118–133. doi:10.1007/BF01459088. JFM 54.0056.06.