아커만 함수
계산 가능성 이론에서, 빌헬름 아커만의 이름을 딴 아커만 함수(Ackermann函數, )는 가장 간단하고 가장 먼저 발견된 원시 재귀 함수가 아닌 완전히 정의된 계산 가능 함수의 예시이다. 모든 원시 재귀 함수는 완전히 정의되고 계산 가능하지만 아커만 함수는 모든 완전히 정의된 계산 가능 함수가 원시 재귀 함수일 필요가 없다는 것을 보였다.
아커만의 함수(음이 아닌 정수 세 개를 변수로 가지는)에 대한 아커만의 출간물 이후 많은 저자들은 다양한 목적에 따라서 이 함수를 수정하였다. 따라서 오늘날 "아커만 함수"라고 하며는 오리지날 함수의 수많은 변형 중 하나를 의미하는 것이다. 한 일반적인 변형은 변수가 두 개인 아커만-페테르 함수()는 음이 아닌 정수 "m"과 "n" 에 대해 다음과 같이 정의된다.
이 값은 입력이 작더라도 매우 빠르게 증가한다. 예를 들면, "A"(4,2)는 19,729자리의 정수이다.
1920년 말에 다비트 힐베르트(David Hilbert)의 제자인 수학자 가브리엘 수단(Gabriel Sudan)과 빌헬름 아커만(Wilhelm Ackermann)은 계산의 기초를 연구하고 있었다. 수단과 아커만은 둘 다 원시 재귀 함수가 아닌 완전히 정의된 계산 가능 함수 (어떤 문헌에서는 단순히 "재귀적"으로 표현한다)를 발견한 것으로 인정된다. 수단은 덜 알려진 수단 함수를 발표하였고, 그 직후 1928년에 아커만은 독립적으로 그의 함수 formula_2 (그리스 문자 "Φ")를 발표하였다. 아커만의 3변수 함수 formula_3는 "p" = 0, 1, 2일 때, 이 함수는 다음과 같은 기본적인 연산(덧셈, 곱셈, 거듭제곱)를 나타낸다.
그리고 "p" > 2이면 이 함수는 이 기본 연산을 하이퍼 연산과 비교할 수 있게 확장한다.
"On the Infinite"에서, 다비트 힐베르트는 아커만 함수는 원시 재귀 함수가 아니라는 가설을 세웠지만 그 가설을 증명한 사람은 힐베르트의 개인 비서이자 전 학생이였던 에크만으로 그의 논문 "On Hilbert’s Construction of the Real Numbers"에서 증명하였다.
로저 페테르(Rózsa Péter)와 라파엘 로빈슨(Raphael Robinson)은 이후에 많은 저자들이 선호하는 아커만 함수의 2변수 버전을 만들었다.
아커만의 오리지날 3변수 함수 formula_3는 다음 음이 아닌 정수 "m", "n", 그리고 "p"에 따라 재귀적으로 정의되었다.
다양한 2변수 버전 중에서, 페테르와 로빈슨이 만든 것(많은 사람들이 말하는 "그" 아커만 함수이다)은 음이 아닌 정수 "m"과 "n"으로 다음과 같이 정의되어 있다.
이것을 보자마자 formula_10이 항상 끝난다는 것을 명백하게 알 수 없다. 하지만, 각각의 재귀적인 적용에서 "m"이 줄어들거나 "m"은 그대로고 "n"이 감소하기 때문에 재귀는 끝이 있다. "n"이 0에 도달할 때 마다 "m"이 줄어들어 "m"은 결국에는 0에 도달한다. (더 기술적으로 표현하자면, 각각의 경우에 ("m", "n")의 쌍은 사전식 순서대로 줄어들어 음이 아닌 단일 정수를 정렬하는 것처럼 정렬 순서가 된다. 즉, 정렬을 무한히 많이 수행하며 내려갈 수 없다는 것을 의미한다.) 하지만, "m"이 감소할 때 "n"이 늘어나는 상한이 없기 때문에 매우 커질 수 있다.
페테르-아커만 함수는 다양한 다른 아커만 함수의 용어로 표현될 수 있다."m"이 1, 2, 또는 3처럼 작은 값일 때, 아커만 함수는 "n" 에 대해서 상대적으로 천천이 증가한다(기껏해야 지수적으로). 하지만 "m" ≥ 4일 때는 매우 빠르게 증가한다. 심지어 "A"(4, 2)만 해도 약 2이고, "A"(4, 3)를 풀어쓰면 어떤 전통적인 표기로 써도 매우 크다.
아커만 함수의 한 흥미로운 양상은 이것이 쓰는 유일한 산술적인 연산은 덧셈과 1을 빼는 것 뿐이다. 이 특성은 무한한 재귀의 지수에서만 온 것이다. 또한 수행 시간이 적어도 그 결과에 비례하다는 것을 암시하기 때문에, 마찬가지로 매우 거대하다. 실제로는 대부분의 경우에 수행 시간은 결과보다 크다.
"m" 과 "n"이 동시에 증가하는 단일 변수 버전 f(n) = A(n, n)는 모든 원시 재귀 함수를 뛰어넘는다. 그중에는 지수 함수, 팩토리얼 함수, 다중 팩토리얼 과 초팩토리얼 함수, 심지어는 커누스 윗화살표 표기법으로 정의된 함수(윗화살표에 지수를 사용하는 경우를 제외하고)와 같이 매우 빠르게 증가하는 함수를 포함한다. f(n)는 대략적으로 빠르게 증가하는 계급의 f(n)와 비교 가능하다고 볼 수 있다. 이 극한의 증가는 튜링 기계와 같이 무한한 메모리를 가지는 기계에서 명백히 계산 가능하고 따라서 계산 가능 함수인 "f"가 다른 어떤 원시 재귀 함수보다 빠르게 증가하기 때문에 원시 재귀함수가 아니라는 것을 보일 때 쓰인다.
거듭제곱들의 범주에서, 동형 사상 formula_17 (컴퓨터 과학에서는 커링이라고 부른다)을 사용하면, 아커만 함수는 다음의 높은 차수의 범함수에서 원시 재귀 함수를 통해 정의할 수 있다.
여기서 는 보통의 다음수 함수이고 Iter는 다음과 같이 원시 재귀로 정의된 함수의 거듭제곱 연산을 나타낸다.
이렇게 정의된 함수 formula_20는 위에서 정의한 아커만 함수 formula_21와 동일하다: formula_22.
아커만 함수가 어떻게 매우 빠르게 커지는지를 보기 위해서는 간단한 표현을 오리지날 정의의 규칙에 따라서 확장하는 것이 도움이 된다. 예를 들어, formula_23를 다음과 같이 완전히 계산할 수 있다:
아래는 formula_25의 계산이 어떻게 해서 많은 단계를 거치고 큰 수가 나오는지를 입증하기 위한 것이다.
아커만 함수를 계산한 것은 무한한 표에 쓸 수 있다. 가장 윗 행을 따라 자연수를 놓고. 표의 값을 결정하기 위해서는 수를 한 칸 왼쪽으로 가져가고, 이전 행에서 방금 그 수의 자리에 있는 수를 찾는다. 왼쪽에 수가 없을 때는 단순히 이전 행에서 "1"로 시작하는 열을 보라. 다음은 표의 왼쪽 상부의 일부이다.
! "m"\"n"
! 0
! 1
! 2
! 3
! 4
! "n"
! 0
! 1
! 2
! 3
! 4
이 역함수는 서로소 집합 자료 구조와 최소 신장 트리에 대한 채즐(Bernard Chazelle)의 알고리즘과 같은 알고리즘의 시간 복잡도에서 나타난다. 때때로 아커만의 원래 함수나 다른 변형은 이 설정에 쓰이나 모두 비슷하게 빠른 비율로 증가한다. 특히, 어떤 수정된 함수는 식에서 "−3"과 비슷한 항을 제거해서 단순하게 수정했다.
역 아커만 함수의 2변수 변형은 다음과 같이 정의할 수 있다. 여기서 formula_39는 바닥 함수이다:
이 함수는 위에서 언급한 알고리즘을 더 정확하게 분석 할 때 나타나고 더 제한된 시간 경계를 얻는다. 서로소 집합 자료 구조에서, "m"은 연산의 숫자를 나타내고 "n"은 원소의 갯수를 나타낸다. 최소 신장 트리에서, "m"은 변의 갯수를 나타내고 "n"은 꼭짓점의 갯수를 나타낸다.
몇몇 약간 다른 α("m", "n")의 정의가 있다. 예를 들어, log "n"은 종종 "n"으로 바뀌고 바닥 함수는 종종 천장 함수로 바뀐다.
다른 연구에서는 m이 상수로 정해져서 특정한 행의 역함수로 정의할 수도 있다.
그 정의 때문에 극한으로 깊은 재귀 때문에 아커만 함수는 컴파일러의 재귀를 최적화 하는 능력을 테스트 하는데 사용 할 수 있다. 아커만의 함수를 이렇게 사용하는 것은 1971년에 윙베 순드블라드(Yngve Sundblad)가 처음으로 출간하였다.
순드블라드의 세미나 논문은 1975년에서 1982년까지의 3부작 논문에서 브라이언 위치만(Brian Wichmann, 헤트스톤 벤치마크(Whetstone benchmark)의 공저자)에 의해 채택되었다.