아커만 함수 계산기

A(0, n) = n + 1, A(m, 0) = A(m−1, 1), A(m, n) = A(m−1, A(m, n−1)) 세 줄로 정의되는 함수입니다. 1928년 빌헬름 아커만이 내놓았고, 계산 가능하면서도 원시재귀가 아닌 첫 예로 알려져 있습니다.

반복 횟수를 미리 정해 놓는 루프만 아무리 겹쳐 써도 이만큼 빨리 자라는 함수를 만들 수 없다는 뜻이기 때문입니다. 그전까지는 「계산 가능하다」와 「원시재귀다」가 같은 말이라고 여겼는데, 아커만 함수가 그것을 깼습니다.

연산이 한 단계씩 올라갑니다. A(1, n) = n + 2로 더하기, A(2, n) = 2n + 3으로 곱하기, A(3, n) = 2^(n+3) − 3으로 거듭제곱, A(4, n) = 2↑↑(n+3) − 3으로 거듭제곱탑입니다. 더하기가 반복되면 곱하기가 되고, 곱하기가 반복되면 거듭제곱이 되는 그 사다리를 그대로 올라갑니다.

2^65536 − 3이고 십진수로 19,729자리입니다. A(4, 3)은 그 자체가 지수인 수라 우주의 모든 입자에 한 자리씩 적어도 자리가 모자랍니다. m을 5로 올리면 A(5, 0) = 65,533부터 시작해 더 빨리 폭발합니다.

정의를 그대로 재귀로 옮기면 A(3, 8) 정도에서 벌써 호출 깊이가 2,000을 넘어 브라우저가 죽기 때문입니다. 이 도구는 아직 처리하지 못한 m들을 배열에 쌓아 두는 방식으로 같은 계산을 합니다. 결과는 같고, 호출 횟수를 세기도 쉽습니다.

아커만 함수를 뒤집은 것으로, 믿기지 않을 만큼 천천히 자랍니다. 실제 우주에서 나올 법한 어떤 입력에서도 5를 넘지 않아 사실상 상수처럼 다룹니다. 유니온–파인드 자료구조의 시간복잡도에 이 함수가 등장합니다.

전송되지 않습니다. 계산은 모두 브라우저 안에서 이뤄지고, 입력값은 이 기기에만 남습니다.