아커만 함수

계산가능성 이론에서 빌헬름 아커만 함수의 이름을 딴 아커만 함수는 원시적 재귀성이 아닌 총 계산가능함수의 가장 단순하고^[1] 가장 먼저 발견된 예 중 하나이다.모든 원시 재귀 함수는 총체적이고 계산 가능하지만, Ackermann 함수는 모든 총 계산 가능한 함수가 원시 재귀 함수는 아니라는 것을 보여준다.아커만이 자신의 기능을 출판한^[2] 후(비음수 정수 인수가 세 개 있었던) 많은 저자들이 다양한 목적에 맞게 수정하여 오늘날 "아커만 함수"는 수많은 변형 중 어느 것도 본래의 함수를 지칭할 수 있도록 하였다.하나의 일반적인 버전인 두 개의 주장 Ackermann-Péter 함수는 음이 아닌 정수 m과 n에 대해 다음과 같이 정의된다.

${\displaystyle {\begin{array}{lcl}\operatorname {A} (0,n)&=&n+1\\\operatorname {A} (m+1,0)&=&\operatorname {A} (m,1)\\\operatorname {A} (m+1,n+1)&=&\operatorname {A} (m,\operatorname {A} (m+1,n))\end{array}}}$

그것의 가치는 작은 입력에도 불구하고 빠르게 증가한다.예를 들어 A(4, 2)는 소수점 19^[3],729자리(2-3⁶⁵⁵³⁶ 또는 2-3과²²²² 동일)의 정수다.

역사

1920년대 후반, 수학자 가브리엘 수단과 데이비드 힐버트의 학생 빌헬름 애커먼이 연산의 기초를 연구하고 있었다.수단과 아커만 모두 원시적 재귀가 아닌 총 계산 가능한 함수(일부 참조에서 단순히 "재귀적"이라고 칭함)를 발견한 것으로 인정받고^[4] 있다.수단은 덜 알려진 수단 함수를 발표했고, 그 직후 그리고 독립적으로 1928년에 아커만은 그의 함수 $\phi {\displaystyle }$ ${\displaystyle \$varphi $}$을 발표하였다.$$Ackermann의 3개 인수 함수인 $\phi {\displaystyle (m}$, ${\displaystyle n}$, p${\displaystyle }$) ${\displaystyle \varphi(m,n,p)}$는$$$p{\displaystyle }$= ${\displaystyle 0,}$ ${\displaystyle 1}$, ${\displaystyle 2}$ ${\displaystyle p=0,1,2$에 대해 덧셈, 곱셈, 지수의 기본 연산을 다음과 같이 재현한다.

${\displaystyle {\n}\varphi(m,n,0)&=m+n\\\\varphi(m,n,1)&=m\n\\barphi(m,n,2)&=m^{n}\end{igned}}}}}}}}$

그리고 p > 2의 경우, 이러한 기본적 연산을 초작용으로 비교할 수 있는 방식으로 확장한다.

${\displaystyle {\n,3}\varphi(m,n,3)&=m[4](n+1)\\\varphi(m,n,p)&\gtrapprox m[p+1](n+1)&{}{}p>3\end{igned}}}}}}$

(총컴퓨팅은 가능하나 일차적인 리커시브 함수로서의 역사적 역할과는 달리, 아커만의 본래의 함수는 그 목적을 위해 특별히 설계된 아커만 함수의 변종(예: 굿스타인의 초동작렬)처럼 매끄럽게는 아니지만, 기본 산술 연산을 지수 이상으로 확장하는 것으로 보인다..)

온 더 인피니트(^[5]On the Infinite)에서 데이비드 힐버트는 아커만 함수가 원시적인 재귀적 기능이 아니라 힐버트의 개인 비서이자 전 학생인 애커만(Ackermann)이라고 가설을 세웠는데, 그는 실제로 그의 논문 '힐버트의 실제 숫자 구성'에서 그 가설을 증명했다.^[2][6]

로자 페터와^[7] 라파엘 로빈슨은^[8] 후에 거의 모든 작가들이 선호하는 아커만 함수의 2변형 버전을 개발했다.

일반화된 초작동 시퀀스$($예: $G{\displaystyle }$(${\displaystyle m}$ ,${\displaystyle a}$, ${\displaystyle b}$)${\displaystyle }$=${\displaystyle }$[ ${\displaystyle m}$ ${\displaystyle ]}$ ${\displaystyle b}$ ${\displaystyle G(m,a,b)=a[m]b}$도 Ackermann 함수의 한 버전이다.^[9]

1963년 R.C. Buck은 과작동 시퀀스에$$ 직관적인 $2변수{\displaystyle \mathrm{}}$ F ${\displaystyle \operatorname {F} }$을(를) 기반으로 했다.^[10][11]

${\displaystyle \operatorname {F}(m,n)=2[m]n.}$

대부분의 다른 버전에 비해 Buck의 함수는 본질적이지 않은 오프셋을 가지고 있지 않다.

${\displaystyle {\begin{aligned}\operatorname {F} (0,n)&=2[0]n=n+1\\\operatorname {F} (1,n)&=2[1]n=2+n\\\operatorname {F} (2,n)&=2[2]n=2\times n\\\operatorname {F} (3,n)&=2[3]n=2^{n}\\\operatorname {F} (4,n)&=2[4]n=2^{2^{2^{{}^{.^{.^{{}_{.}}}}}}\\\&\cHB \vdots \end{aigned}}}$

Ackermann 함수의 다른 많은 버전이 조사되었다.^[12]

정의

정의: m-ari 함수로써

Ackermann의 원래 3개 인수 함수 $\phi {\displaystyle (m}$, ${\displaystyle n}$, p${\displaystyle }$) ${\displaystyle \varphi(m,n,p)}$은(는) $음$이 아닌 정수 m${\displaystyle ,}$ {\$displaystym m,n,}$ 및 $p$ ${\displaystyp}$에 대해 다음과 같이 반복적으로 정의된다$.$

${\displaystyle {\begin{aligned}\varphi (m,n,0)&=m+n\\\varphi (m,0,1)&=0\\\varphi (m,0,2)&=1\\\varphi (m,0,p)&=m&&{\text{for }}p>2\\\varphi (m,n,p)&=\varphi (m,\varphi (m,n-1,p),p-1)&&{\text{for }}n,p>0\end{aligned}}}$

다양한 두 가지 주장 버전 중, Péter와 Robinson(대부분 저자에 의해 "The" Ackermann 함수라고 불리는 것)이 개발한 것은 다음과 같이$$ 비부정 $정수{\displaystyle }$ m ${\displaystyle m}$과 n ${\displaystyle n}$에 대해 정의된다.

${\displaystyle {\begin{array}{lcl}\operatorname {A} (0,n)&=&n+1\\\operatorname {A} (m+1,0)&=&\operatorname {A} (m,1)\\\operatorname {A} (m+1,n+1)&=&\operatorname {A} (m,A(m+1,n))\end{array}}}$

Ackermann 함수는 또한 과작동 순서와 관련하여 다음과 같이 표현되었다.^[13][14]

${\displaystyle A(m,n)={\begin}n+1&m=0\\\2[m](n+3)-3&m_0\\end{case}}}}$

또는 Knuth의 위쪽 화살표 표기법(정수 지수 $\ge {\displaystyle }$- ${\displaystyle 2}$ ${\displaystyle \geq$ -2$}$에 확장):$$

${\displaystyle ={\case}n+1&m=0\\2\uparrow ^{m-2}(n+3)-3&m_0\\end{case}}}}$

또는 Buck의 함수 F:^[10]

${\displaystyle ={\begin}n+1&m=0\\F(m,n+3)-3&m_0\\\case}}$

정의: 반복된 1ari 함수

$f{\displaystyle }$ ${\$를 f ${\displaystyle f}$의 n번째 반복으로$$ 정의하십시오$.$

${\displaystyle {\reason{array}{rll}f^{0}(x)&=&x\f^{n+1}(x)&f(f^{n})(x)\end{array}}}}}}}}$

반복은 스스로 일정한 횟수로 함수를 구성하는 과정이다.함수 구성은 연관 연산이기 때문에 $f{\displaystyle (f^{}}$ n${\displaystyle {}^{}}$( ${\displaystyle x}$)${\displaystyle }$= ${\displaystyle f^{}}$( ${\displaystyle x}$ )$$= ${\displaystyle {}^{}}$ ( x ) $displaystyle f(f^{n}(x)=f^{n$}($f(x)})}}$.

Ackermann 함수를 단항 함수의 시퀀스로 간주하여 A ${\displaystyle m_{}}$ ${\displaystyle {}_{}}$( ${\displaystyle n}$)${\displaystyle }$= A ${\displaystyle }$( ${\displaystyle m}$, n${\displaystyle }$) ${\displaystyle \operatorname {A} _{m}(n)=\operatorname {A}(m,n)$를 설정할 수 있다$.$

그런 다음 함수는 $시퀀스{\displaystyle {\mathrm{}}_{}}$ A${\displaystyle {}_{}{0\mathrm{}}_{}{}_{}}$ ${\displaystyle {\mathrm{}}_{}}$ 1, ${\displaystyle {A\mathrm{}}_{}}$2,${\displaystyle }$. . . ${\displaystyle \operatorname {A} _{0},\operatorname {A} _{1},\operatorname {A} _{2},$ .반복에서 정의된 $}$개의$$ 단일^{[n 2]} 함수:

${\displaystyle {\begin{array}{lcl}\operatorname {A} _{0}(n)&n+1\\\operatorname {A} _{m}^{n+1}(1)\\end{array}}}}}$

연산

Ackermann 함수의 재귀적 정의는 자연스럽게 용어 재작성 시스템(TRS)으로 전환할 수 있다.

TRS, 2ari 함수에 기반

2-ari Ackermann 함수의 정의는 명확한 감소 규칙으로 이어진다.

${\displaystyle {\begin{array}{lll}{\text{(r1)}}&A(0,n)&\rightarrow &S(n)\\{\text{(r2)}}&A(S(m),0)&\rightarrow &A(m,S(0))\\{\text{(r3)}}&A(S(m),S(n))&\rightarrow &A(m,A(S(m),n))\end{array}}}$

예

계산 $A{\displaystyle }$( 1,${\displaystyle 2}$)${\displaystyle {}_{}}$→ ${\displaystyle {\ast }_{}}$ ${\displaystyle {}_{}\mathrm{}}$ ${\displaystyle$ A$(1,2)\오른쪽 화살표 _{*}}$

감소 순서는

가장 왼쪽(한 단계) 전략:	가장 왼쪽 내측(한 단계) 전략:
${\displaystyle {\underline {A(0), S(0)}}}$	${\displaystyle {\underline {A(0), S(0)}}}$
${\displaystyle \rightarrow _{r3}{\underline {A(0,A(S(0),S(0))}$	${\displaystyle \rightarrow _{r3}A(0,{\underline {A(0), S(0)}}}$
${\displaystyle \rightarrow _{r1}S({\underline {A(0), S(0)}}}}$	${\displaystyle \rightarrow _{r3}A(0,{\underline {A(S(0),0)})}$
${\displaystyle \rightarrow _{r3}S({\underline {A(0,A(S0,0)))}})}$	${\displaystyle \rightarrow_{r2}A(0,{\underline {A(0,S(0)})}$
${\displaystyle \rightarrow _{r1}S({\underline {A(0),0})}$	${\displaystyle \rightarrow _{r1}A(0,{\underline {A(0,S(0)))}}$
${\displaystyle \rightarrow _{r2}S({\underline {A(0,S(0)}))}$	${\displaystyle \rightarrow _{r1}{\underline {A(0,S(S))))}}}$
${\displaystyle \rightarrow _{r1}S(S(S(0)))}$	${\displaystyle \rightarrow _{r1}S(S(S(0)))}$

$A{\displaystyle \mathrm{}}$ ${\displaystyle }$( ${\displaystyle m}$, n${\displaystyle }$) ${\displaystyle \operatorname {A}(m,n)}$을(를) 계산하려면 스택을 사용할 수 있으며, 이 스택에는 처음에는 $⟨{\displaystyle }$ ${\displaystyle m,}$ ${\displaystyle n}$ ${\displaystyle ⟩}${\$displaystyle \langle$ m$,n\angle$} 요소가 포함되어 있다$.$

그런 다음 반복적으로 두 개의 상위 요소를 규칙에^{[n 4]} 따라 교체한다.

${\displaystyle {\begin{array}{lllllllll}{\text{(r1)}}&0&,&n&\rightarrow &(n+1)\\{\text{(r2)}}&(m+1)&,&0&\rightarrow &m&,&1\\{\text{(r3)}}&(m+1)&,&(n+1)&\rightarrow &m&,&(m+1)&,&n\end{array}}}$

${\displaystyle \mathrm{개략적}}$으로${\displaystyle ,}{\displaystyle n}$m ,$$n $display$ {\$displaystyle \langle m$,n$\$angle $\}:$

WHY stackLength <> 1 { POP 2 요소, PUSH 1 또는 2 또는 3 요소, r1, r2, r3 규칙 적용 }

이 필적은 그로스만&자이트만(1988)에 발표된다.

예를 들어, 입력 $⟨{\displaystyle 2}$에서 ${\displaystyle 1}$ ${\displaystyle ⟩}$ ${\displaystyle \langle$ 2,$1\angle$ $\},$

스택 구성	감액을[n 5] 반영하다
${\displaystyle {\underline {2,1}$	${\displaystyle {\underline {A(2,1)}$
${\displaystyle \rightarrow 1,{\underline {2,0}}$	${\displaystyle \rightarrow _{r1}A(1,{\underline {A(0,2)}}$
${\displaystyle \rightarrow 1,{\underline {1,1}}$	${\displaystyle \rightarrow_{r2}A(1,{\underline {A(1,1})}$
${\displaystyle \rightarrow 1,0,{\underline {1,0}}$	${\displaystyle \rightarrow_{r3}A(1,A(0,{\underline {A(1,0)})}$
${\displaystyle \rightarrow 1,0,{\underline {0,1}$	${\displaystyle \rightarrow_{r2}A(1,A(0,{\underline {A(0,1)})}$
${\displaystyle \rightarrow 1,{\underline {0,2}}$	${\displaystyle \rightarrow _{r1}A(1,{\underline {A(0,2)}}$
${\displaystyle \rightarrow {\underline{1,3}}$	${\displaystyle \rightarrow _{r1}{\underline {A(1,3)}}$
${\displaystyle \rightarrow 0,{\underline {1,2}}$	${\displaystyle \rightarrow _{r3}A(0,{\underline {A(1,2})}}$
${\displaystyle \rightarrow 0,0,{\underline {1,1}}$	${\displaystyle \rightarrow _{r3}A(0,{\underline {A(1,1})})}$
${\displaystyle \rightarrow 0,0,{\underline {1,0}}$	${\displaystyle \rightarrow_{r3}A(0,A(0,{\underline {A(1,0}))}$
${\displaystyle \rightarrow 0,0,0,{\underline {0,1}$	${\displaystyle \rightarrow_{r2}A(0,A(0,{\underline {A(0,1))}$
${\displaystyle \rightarrow 0,0,{\underline {0,2}}$	${\displaystyle \rightarrow_{r1}A(0,{\underline {A(0,2)}}$
${\displaystyle \rightarrow 0,{\underline {0,3}}$	${\displaystyle \rightarrow _{r1}A(0,{\underline {A(0,3)}}$
${\displaystyle \rightarrow {\underline {0,4}}$	${\displaystyle \rightarrow _{r1}{\underline {A(0,4)}}$
${\displaystyle \오른쪽 화살표 5}$	${\displaystyle \rightarrow _{r1}5}$

언급

• 로제타 코드의 225개 컴퓨터 언어로 가장 왼쪽 내부를 찌르는 전략이 실행된다.
• 모든 $m{\displaystyle }$, ${\displaystyle n}$ ${\displaystyle m,n}$에 대해 $A{\displaystyle }$( ${\displaystyle m}$, n${\displaystyle }$) ${\displaystyle A(m,n)}$의 계산은${\displaystyle }$(${\displaystyle A(,n}$)${\displaystyle }$+ 1${\displaystyle {}^{}}$) ${\displaystyle m^{}}$ ${\$ 단계$$ 이하가 걸린다$$.^[17]
• 그로스만&${\displaystyle \mathrm{제이트먼}}$(1988)은 $A{\displaystyle \mathrm{}}$ ${\displaystyle (}$m ${\displaystyle ,n}$) ${\displaystyle \operatorname$ {$A$$}($$m,n)}$의 계산에서 스택의$$ 최대 $길이$는 M${\displaystyle }$> ${\displaystyle }${\$displaysty \operatorname {A}(m,n)$이고$,$ 최대 길이는 > 0 ${\displaystym m >0$이라고 지적했다.

Their own algorithm, inherently iterative, computes ${\displaystyle \operatorname {A} (m,n)}$ within ${\displaystyle {\mathcal {O}}(m\operatorname {A} (m,n))}$ time and within ${\displaystyle {\mathcal {O}}(m)}$ space.

반복된 1ari 함수에 기반한 TRS

반복된 1ari Ackermann 함수의 정의는 다른 감소 규칙으로 이어진다.

${\displaystyle {\begin{array}{lll}{\text{(r4)}}&A(S(0),0,n)&\rightarrow &S(n)\\{\text{(r5)}}&A(S(0),S(m),n)&\rightarrow &A(S(n),m,S(0))\\{\text{(r6)}}&A(S(S(x)),m,n)&\rightarrow &A(S(0),m,A(S(x),m,n))\end{array}}}$

함수 구성이 연관성이 있기 때문에 규칙 r6 대신 정의할 수 있다.

${\displaystyle {\begin{array}{lll}{\text{(r7)}}&A(S(S(x)), m,n)&\rightarrow &A(S(S),m,n)\end{array}}}}}$

이전 섹션과 마찬가지로 A $m{\displaystyle {\mathrm{}}_{}^{}}$ ${\displaystyle {}_{}^{}}$⁡${\displaystyle }$(${\displaystyle n}$ ${\displaystyle )}$ ${\displaystyle \operatorname {A} _{m}^{1}(n)}$의 연산을 스택으로 구현할 수 있다$$.

처음에 스택에는 세 가지 요소인 $⟨{\displaystyle }$ ${\displaystyle 1}$,${\displaystyle m,}$ ${\displaystyle n}$ ${\displaystyle ⟩}$ ${\displaystyle \langle$1$,m,n\angle }$이(가) 포함되어 있다$.$

그런 다음 반복적으로 세 가지 상위 요소를 규칙에^{[n 4]} 따라 교체한다.

${\displaystyle {\begin{array}{lllllllll}{\text{(r4)}}&1&,0&,n&\rightarrow &(n+1)\\{\text{(r5)}}&1&,(m+1)&,n&\rightarrow &(n+1)&,m&,1\\{\text{(r6)}}&(x+2)&,m&,n&\rightarrow &1&,m&,(x+1)&,m&,n\\\end{array}}}$

$⟨{\displaystyle }$ ${\displaystyle 1}$,${\displaystyle }$m${\displaystyle }$, ${\displaystyle n}$ ${\displaystyle ⟩}$ ${\displaystyle \langle$ 1,$m,n\angle }$부터 개략적으로 시작$:$

WHY stackLength <> 1 { POP 3 요소, PUSH 1 또는 3 또는 5 요소, r4, r5, r6; } 규칙 적용

예

입력 $⟨{\displaystyle }$ ${\displaystyle 1}$,${\displaystyle 2}$,${\displaystyle 1}$ ${\displaystyle ⟩}$ ${\displaystyle \langle$1$,2,1\angle }$에서 연속$$ 스택 구성은

${\displaystyle{\begin{정렬}&,{\underline{1,2,1}}\rightarrow _{r5}{\underline{2,1,1}}\rightarrow _{r6}1,1,{\underline{1,1,1}}\rightarrow _{r5}1,1,{\underline{2,0,1}}\rightarrow _{r6}1,1,1,0,{\underline{1,0,1}}\\&, \rightarrow _{r4}1,1,{\underline{1,0,2}}\rightarrow _{r4}{\underline{1,1,3}}\rightarrow _{r5}{\underline{4,0,1}}\rightar.연속 즉{r6}1,0,{\underline {3,0,1}}\rightarrow _{r6}1,0,1,0,{\underline {2,0,1}}\\&\rightarrow _{r6}1,0,1,0,1,0,{\underline {1,0,1}}\rightarrow _{r4}1,0,1,0,{\underline {1,0,2}}\rightarrow _{r4}1,0,{\underline {1,0,3}}\rightarrow _{r4}{\underline {1,0,4}}\rightarrow _{r4}5\end{aligned}}}$

그에 상응하는 동일성은 다음과 같다.

$디스플레이 스타일 {\displaystyle}&A_{2}(1)=A_{1}^{2}(1)=A_{1}(A_{1}(1)=A_{1}(A_{0}^{2}(1)=A_{1}(A_{0}(A_{0}(1))\\&=A_{1}(A_{0}(2)=A_{1}(3)=A_{0}^{4}(1)=A_{0}(A_{0}^{3}(1)=A_{0}(A_{0}^{2}(1))\\&=A_{0}(A_{0}(A_{0}(A_{0}(1)))=A_{0}(A_{0}(A_{0}(2))=A_{0}(A_{0}(3)=A_{0}(4)=5\end{aigned}}$

규칙 r6 대신 r7을 사용하면 스택의 교체가 뒤따를 것이다.

${\displaystyle {\cHB{array}{lllllll}{\text{(r7)}&(x+2)&,m&,n&\오른쪽 화살표 &(x+1)&,m&,1&,m&,n\end{array}}}}}$

그런 다음 연속적인 스택 구성은

${\displaystyle{\begin{정렬}&,{\underline{1,2,1}}\rightarrow _{r5}{\underline{2,1,1}}\rightarrow _{r7}1,1,{\underline{1,1,1}}\rightarrow _{r5}1,1,{\underline{2,0,1}}\rightarrow _{r7}1,1,1,0,{\underline{1,0,1}}\\&, \rightarrow _{r4}1,1,{\underline{1,0,2}}\rightarrow _{r4}{\underline{1,1,3}}\rightarrow _{r5}{\underline{4,0,1}}\rightar.연속 즉{r7}3,0,{\underline {1,0,1}}\rightarrow _{r4}{\underline {3,0,2}}\\&\rightarrow _{r7}2,0,{\underline {1,0,2}}\rightarrow _{r4}{\underline {2,0,3}}\rightarrow _{r7}1,0,{\underline {1,0,3}}\rightarrow _{r4}{\underline {1,0,4}}\rightarrow _{r4}5\end{aligned}}}$

그에 상응하는 동일성은 다음과 같다.

$디스플레이 스타일 {\displaystyle}&A_{2}(1)=A_{1}^{2}(1)=A_{1}(A_{1}(1)=A_{1}(A_{0}^{2}(1)=A_{1}(A_{0}(A_{0}(1))\\&=A_{1}(A_{0}(2)=A_{1}(3)=A_{0}^{4}(1)=A_{0}^{3}(A_{0}(1)=A_{0}^{3}(2)\&=A_{0}^{2}(A_{0}(2)=A_{0}^{2}(3)=A_{0}(A_{0}(3)=A_{0}(4)=5\end{aigned}}$

언급

• 주어진 입력에서 지금까지 제시된 TRS는 동일한 수의 단계로 수렴한다.또한 동일한 감소 규칙을 사용한다(이 비교에서 규칙 r1, r2, r3은 각각 규칙 r4, r5, r6/r7과 "동일한" 것으로 간주된다).예를 들어, $A{\displaystyle }$( ${\displaystyle 2}$,$){\displaystyle A(2,1)}$의 감소는 6 × r1, 3 × r2, 5 × r3의 14 단계로 수렴된다$$.$A{\displaystyle {}_{}}$ ${\displaystyle {2\mathrm{}}_{}}$( ${\displaystyle 1}$) ${\displaystyle A_{2$}(1$)의$감소는 동일한 14단계: 6 × r4, 3 × r5, 5 × r6/r7에서 수렴된다$$.TRS는 감소 규칙이 적용되는 순서에 따라 다르다.
• When ${\displaystyle A_{i}(n)}$ is computed following the rules {r4, r5, r6}, the maximum length of the stack stays below ${\displaystyle 2\times A(i,n)}$. When reduction rule r7 is used instead of rule r6, the maximum length of the stack is only ${\displaystyle 2(i+2)}$.스택의 길이는 재귀 깊이를 반영한다.규칙 {r4, r5, r7}에 따른 감소는 최대 재귀 깊이가 작기 때문에 이 계산은 그런 점에서 더 효율적이다.^{[n 6]}

TRS, 하이퍼 오퍼레이터 기반

Sundblad (1971) 또는 Porto & Matos (1980)가 분명히 보여주었듯이, Ackermann 함수는 초동작렬의 관점에서 표현될 수 있다.

${\displaystyle A(m,n)={\begin}n+1&m=0\\\2[m](n+3)-3&m_0\\end{case}}}}$

또는 파라미터 목록에서 상수 2를 제거한 후, Buck의 기능 측면에서

${\displaystyle ={\begin}n+1&m=0\\F(m,n+3)-3&m_0\\\case}}$

Ackermann 함수의 변형인$$^[10]Buck의 함수 $F{\displaystyle \mathrm{}}$ ${\displaystyle (m}$, n${\displaystyle }$)${\displaystyle }$= 2${\displaystyle }$[ ${\displaystyle m}$ ${\displaystyle ]n}$ ${\displaystyle \operatorname {F}(m,n)=2[m]n}$은(는) 다음과 같은 감소 규칙을 사용하여 계산할 수 있다.

${\displaystyle{\begin{배열}{lll}{\text{(b1)}}&F(S(0),0,n)&\rightarrow&S(n)\\{\text{(b2)}}&F(S(0),S(0),0)&\rightarrow&S(S(0))\\{\text{(b3)}}&F(S(0),S(S(0)),0)&\rightarrow&0\\{\text{(b4)}}&F(S(0),S(S(S(m))),0)&\rightarrow&S(0)\\{\text{(b5)}}&F(S(0),S(m),S(n))&\rightarrow&F(S(n),m,F(S(.0,S(m),0))\\{\text{(b6)}}&F(S(S)(x), m,n)&\오른쪽 화살표 &F(S(0),m(x),m,n)\end{array}}}}}}$

규칙 b6 대신 규칙을 정의할 수 있다.

${\displaystyle {\begin{array}{lll}{\text{(b7)}}&F(S(S)(x), m,n)&\rightarrow &F(S),m,n)\end{array}}}}}$

Ackermann 기능을 계산하려면 세 가지 감소 규칙을 추가하면 된다.

${\displaystyle {\begin{array}{lll}{\text{(r8)}}&A(0,n)&\rightarrow &S(n)\\{\text{(r9)}}&A(S(m),n)&\rightarrow &P(F(S(0),S(m),S(S(S(n)))))\\{\text{(r10)}&P(S(S(S)(m))))&\rightarrow &m\\\end{array}}$

이 규칙은 베이스 케이스 A(0,n), 정렬(n+3) 및 퍼지(-3)를 처리한다.

예

계산 $A{\displaystyle (2}$, ${\displaystyle 1}$)${\displaystyle {}_{}}$→ ${\displaystyle {\ast }_{}}$ ${\displaystyle {}_{}\mathrm{}}$ ${\$디스플레이 $스타일 A(2,1)\$오른쪽 $화살표 _{*}5}$

축소 규칙 ${\displaystyle \text{b7}}$ ${\$ 사용$$[n 5]:	축소 규칙 ${\displaystyle \text{b6}}$ ${\$ 사용$$[n 5]:
${\displaystyle {\underline {A(2,1)}$	${\displaystyle {\underline {A(2,1)}$
${\displaystyle \rightarrow _{r9}P({\underline {F(1,2,4)})}$	${\displaystyle \rightarrow _{r9}P({\underline {F(1,2,4)})}$
${\displaystyle \rightarrow_{b5}P(F(4,1,{\underline {F(1,2,0)})}$	${\displaystyle \rightarrow_{b5}P(F(4,1,{\underline {F(1,2,0)})}$
${\displaystyle \rightarrow _{b3}P({\underline {F(4,1,0)})}$	${\displaystyle \rightarrow _{b3}P({\underline {F(4,1,0)})}$
${\displaystyle \rightarrow _{b7}P(F(3,1,{\underline {F(1,1,0)})}$	${\displaystyle \rightarrow _{b6}P(F(1,1,{\underline {F(3,1,0)})}$
${\displaystyle \rightarrow _{b2}P({\underline {F(3,1,2)}}$	${\displaystyle \rightarrow_{b6}P(F(1,1,1,{\underline{F(2,1,0})))}$
${\displaystyle \rightarrow _{b7}P(F(2,1,{\underline {F(1,1,2})})}$	${\displaystyle \rightarrow_{b6}P(F(1,1,1,{\underline{F(1,1,0}))))}$
${\displaystyle \rightarrow_{b5}P(F(2,1,F,{\underline{F(1,1,0})))}$	${\displaystyle \rightarrow_{b2}P(F(1,1,1,{\underline{F(1,1,2})))}$
${\displaystyle \오른쪽 화살표 _{b2}P(F(2,1,{\밑줄 {F(2,0,2)})}$	${\displaystyle \rightarrow_{b5}P(F(1,1,1,F(2,0,{\underline{F(1,1,0})))))}$
${\displaystyle \rightarrow_{b7}P(F(2,1,1,F(1,0,2}})))}$	${\displaystyle \rightarrow_{b2}P(F(1,1,F(1,1,{\underline{F(2,0,2}})))}$
${\displaystyle \오른쪽 화살표 _{b1}P(F(2,1,{\밑줄 {F(1,0,3)})}$	${\displaystyle \rightarrow_{b6}P(F(1,1,1,F(1,0,2}))))}$
${\displaystyle \rightarrow _{b1}P({\underline {F(2,1,4)}}$	${\displaystyle \rightarrow_{b1}P(F(1,1,1,{\underline{F(1,0,3})))}$
${\displaystyle \rightarrow_{b7}P(F(1,1,{\underline {F(1,1,4)})))}$	${\displaystyle \rightarrow _{b1}P(F(1,1,{\underline {F(1,1,4)})))}$
${\displaystyle \rightarrow_{b5}P(F(1,1,0,{\underline {F(1,1,0})))}$	${\displaystyle \rightarrow_{b5}P(F(1,1,0,{\underline {F(1,1,0})))}$
${\displaystyle \오른쪽 화살표 _{b2}P(F(1,1,{\밑줄 {F(4,0,2)})}$	${\displaystyle \오른쪽 화살표 _{b2}P(F(1,1,{\밑줄 {F(4,0,2)})}$
${\displaystyle \rightarrow_{b7}P(F(1,1,1,F(3,{\underline{F(1,0,2}})))}$	${\displaystyle \오른쪽 화살표 _{b6}P(F(1,1,F(1,0,{\underline{F(3,0,2}})))}$
${\displaystyle \rightarrow _{b1}P(F(1,1,{\underline {F(3,0,3)})}$	${\displaystyle \rightarrow_{b6}P(F(1,1,1,F(1,0,{\underline{F(2,0,2}}))))}$
${\displaystyle \오른쪽 화살표 _{b7}P(F(1,1,F(2,0,{\underline{F(1,0,3})))}$	${\displaystyle \rightarrow_{b6}P(F(1,1,0,F(1,0,{\underline{F(1,0,2}})))))))))}$
${\displaystyle \rightarrow _{b1}P(F(1,1,{\underline {F(2,0,4))})}$	${\displaystyle \오른쪽 화살표 _{b1}P(F(1,1,1,F(1,0,{\언더라인 {F(1,0,3}))))}$
${\displaystyle \rightarrow_{b7}P(F(1,1,1,F(1,0,4})))}$	${\displaystyle \오른쪽 화살표 _{b1}P(F(1,1,1,F(1,0,4})))}$
${\displaystyle \rightarrow_{b1}P(F(1,1,{\underline {F(1,0,5)})}$	${\displaystyle \rightarrow_{b1}P(F(1,1,{\underline {F(1,0,5)})}$
${\displaystyle \rightarrow _{b1}P({\underline {F(1,1,6)}}$	${\displaystyle \rightarrow _{b1}P({\underline {F(1,1,6)}}$
${\displaystyle \rightarrow _{b5}P(F(6,0,{\underline {F(1,1,0)})}$	${\displaystyle \rightarrow _{b5}P(F(6,0,{\underline {F(1,1,0)})}$
${\displaystyle \rightarrow _{b2}P({\underline {F(6,0,2)}}$	${\displaystyle \rightarrow _{b2}P({\underline {F(6,0,2)}}$
${\displaystyle \rightarrow _{b7}P(F(5,0,{\underline {F(1,0,2})})}$	${\displaystyle \rightarrow _{b6}P(F(1,0,{\underline {F(5,0,2)})}$
${\displaystyle \rightarrow _{b1}P({\underline {F(5,0,3)}}$	${\displaystyle \오른쪽 화살표 _{b6}P(F(1,0,F(1,0,{\underline {F(4,0,2}})))}$
${\displaystyle \rightarrow_{b7}P(F(4,0,{\underline {F(1,0,3)})}$	${\displaystyle \rightarrow_{b6}P(F(1,0,F(1,0,{\underline{F(3,0,2}}))))}$
${\displaystyle \rightarrow _{b1}P({\underline {F(4,0,4)}}$	${\displaystyle \rightarrow_{b6}P(F(1,0,F(1,0,{\underline{F(2,0,2}})))))))))}$
${\displaystyle \rightarrow _{b7}P(F(3,0,{\underline {F(1,0,4)})))}$	${\displaystyle \rightarrow_{b6}P(1,0,F(1,0,F(1,0,{\underline{F(1,0,2}})))))}$
${\displaystyle \rightarrow _{b1}P({\underline {F(3,0,5)}}$	${\displaystyle \rightarrow_{b1}P(1,0,F(1,0,{\underline{F(1,0,3})))))))}$
${\displaystyle \rightarrow _{b7}P(F(2,0,{\underline {F(1,0,5)})}$	${\displaystyle \오른쪽 화살표 _{b1}P(F(1,0,F(1,0,{\underline{F(1,0,4}))))}$
${\displaystyle \rightarrow _{b1}P({\underline {F(2,0,6)}}$	${\displaystyle \rightarrow_{b1}P(F(1,0,F,{\underline {F(1,0,5})))}$
${\displaystyle \오른쪽 화살표 _{b7}P(F(1,0,{\underline {F(1,0,6)})}$	${\displaystyle \오른쪽 화살표 _{b1}P(F(1,0,{\underline {F(1,0,6)})}$
${\displaystyle \rightarrow _{b1}P({\underline {F(1,0,7})}$	${\displaystyle \rightarrow _{b1}P({\underline {F(1,0,7})}$
${\displaystyle \rightarrow _{b1}{\underline {P(8)}}$	${\displaystyle \rightarrow _{b1}{\underline {P(8)}}$
${\displaystyle \rightarrow _{r10}5}$	${\displaystyle \rightarrow _{r10}5}$

일치하는 동일성은

• 감소 규칙 ${\displaystyle \text{b6}}$ ${\$이(가) 있는 TRS가 적용되는$$ 경우:

${\displaystyle {\begin{aigned}&A(2,1)+3=F(2,4)=\dots =F^{6}(0,2)=F(0,F^{5}(0,2))=F(0,F(0,F^{4}(0,2))\\&=F(0,F(0,F^{3}(0,2))))=F(0,F(0,F)(0,F^{2})(0,F^{2})(0,2))))))=F(0,F(0,F(0,F(0,F(0,F(0,2))))))))\&=F(0,F(0,F(0,F(0,F(0,3))))))=F(0,F(0,F(0,F(0,4))))=F(0,F(0,F(0,5))=F(0,F(0,6))=F(0,7)=8\end{aigned}}$

• 감소 규칙 ${\displaystyle \text{b7}}$ ${\$이(가) 있는 TRS가 적용되는$$ 경우:

${\displaystyle {\begin{aigned}&A(2,1)+3=F(2,4)=\dots=F^{6}(0,2)=F^{5}(0,F(0,2)=F^{5}(0,3)=F^{4}(0,F(0,3))=F^{4}(0,4)\&=F^{3}(0,F(0,4))=F^{3}(0,5)=F^{2}(0,F(0,5))=F^{2}(0,6)=F(0,F(0,6))=F(0,7)=8\end{aigned}}$

언급

• 규칙 {b1 - b5, b6, r8 - r10}에 따른$$ $A{\displaystyle {\mathrm{}}_{}}$ ${\displaystyle i_{}}$ ${\displaystyle {}_{}}$(${\displaystyle n}$) ${\displaystyle \operatorname {A} _{i}(n)}$의 계산은 매우 반복적이다.중첩된 $F{\displaystyle }$ ${\displaystyle F}$의 최대 깊이는 A${\displaystyle (}i{\displaystyle }$ ,${\displaystyle n}$)${\displaystyle }$+ ${\displaystyle 1}$ ${\displaystyle A(i,n)+1}$이다$.$범인은 반복이 실행되는 순서다.${\displaystyle {}^{}F}$ n${\displaystyle {}^{}}$+ ${\displaystyle 1^{}}$ (${\displaystyle {}^{}x}$)${\displaystyle }$= F${\displaystyle }$( ${\displaystyle F^{}}$ (${\displaystyle {}^{}x}$)${\displaystyle }$) ${\displaystyle F^{n+1}(x)=F(F^{n})(x)}}$.첫 번째 $F{\displaystyle }$ ${\displaystyle F}$은 전체 시퀀스를 펼친 후에만 사라진다$$.
• 그런 점에서 규칙 {b1 - b5, b7, r8 - r10}에 따른 계산이 더 효율적이다.반복 $F{\displaystyle {}^{}}$ ${\displaystyle {\mathrm{n}}^{}}$+ 1 (${\displaystyle {}^{}x}$)${\displaystyle }$= ${\displaystyle {}^{}}$ ${\displaystyle n^{}}$( ${\displaystyle F}$( )${\displaystyle }$)${\displaystyle$ F$^{n+1}(x)=$$F^{n}(F(x)})}$은(는) 코드 블록에 대한 반복 루프를 시뮬레이션한다$$.^{[n 7]}중첩은${\displaystyle }$(${\displaystyle i}$+ ${\displaystyle 1}$) ${\displaystyle (i+1)}($으)로 제한되며$,$ 반복 기능당 1회 반복 수준임.마이어 앤 리치(1967)는 이런 서신을 보여주었다.
• 이러한 고려사항은 재귀 깊이에만 관련된다.어떤 식으로든 반복하면 동일한 규칙(규칙 b6와 b7이 "동일한" 것으로 간주되는 경우)을 수반하는 동일한 수의 감축 단계로 이어진다.예를$$ 들어 $A{\displaystyle (2}$, ${\displaystyle 1}$) ${\displaystyle A(2,1$)의 감소는 12 × b1, 4 × b2, 1 × b3, 4 × b5, 12 × b6/b7, 1 × r9, 1 × r10의 35 단계로 수렴된다.modus iterandi는 감소 규칙이 적용되는 순서에만 영향을 미친다.
• 실행 시간의 진정한 이득은 하위 결과를 반복해서 재계산하지 않는 것만이 달성할 수 있다.메모화는 기능 호출의 결과를 캐시해 같은 입력이 다시 발생할 때 반환하는 최적화 기법이다.예를 들어 Ward(1993)를 참조하십시오.그로스만&제이트먼(1988)은 $O{\displaystyle \mathcal{}(A,}$ ${\displaystyle i,}$ ${\displaystyle n}$ $){\displaystyle$$A(i$$,$$)}$시간과$$$$ $O{\displaystyle \mathcal{}(}$i${\displaystyle ,}$$n)$시간 내에, 그리고 O($){\displaystyle {\mathcal{O}}}$공간$$ 내에서 $A{\displaystyle }$(${\displaystyle i,}$n$)$를 계산하는 교활한 알고리즘을 발표했다.

엄청난 숫자

$A{\displaystyle (4}$, ${\displaystyle 3}$) ${\displaystyle$ A$(4,3)}$의 계산 결과가 여러 단계로 어떻게 나타나는지$$ 시연하려면 다음과 같이 하십시오.^{[n 5]}

${\displaystyle {\begin{argin}A(4,3)&\오른쪽 화살표 A(3,A(4,2)\&\오른쪽 화살표 A(3,A(4,1))\\&\오른쪽 화살표 A(3,A(3,A(4,0))))\\&\오른쪽 화살표 A(3,A(3,A(3,A(3,1))))\\&\오른쪽 화살표 A(3,A(3,A(2,A(3,0))))))\\&\오른쪽 화살표 A(3,A(3,A(2,A(2,1)))))\\&\rightarrow A(3,A(3,A(3,A(2,A(1,A(2,0))))))\\&\rightarrow A(3,A(3,A(3,A(2,A(1,A(1,1))))))\\&\rightarrow A(3,A(3,A(3,A(2,A(1,A(0,A(1,0)))))))\\&\rightarrow A(3,A(3,A(3,A(2,A(1,A(0,A(0,1)))))))\\&\rightarrow A(3,A(3,A(3,A(2,A(1,A(0,2))))))\\&\rightarrow A(3,A(3,A(3,A(2,A(1,3)))))\\&, \rightarrow A(3,A(3,A(3,A(2,A(0,A(1,2))))))\\&, A(3,A(3,A(3,A(2,A(0,A(0,A(1,1)))))))\\&, A(3,A(3,A(3,A(2,A(0,A(0,A(0,A(1,0))))))))\\& \rightarrow, A(3,A(3,A(3,A(2,A(0,A(0,A(0,A(0,1))))))))\\& \rightarrow, A(3,A(3,A(3,A(2,A(0,A(0,A(0.2)))))))\\& \rightarrow, \rightarrow \rightarrow A(3,A(3,A(3,A(2,A(0,A(0,3))))))\\&, \rightarrow A.(3,A(3,A(3,A(2,A(0,4)))))\\&\오른쪽 화살표 A(3,A(3,A(2,5)))\\&\qquad \vdots \&\오른쪽 화살표 A(3,A(3,13)))\\&\qquad \vdots \&\오른쪽 화살표 A(3,A(3,65533))\\&\qquad \vdots \&\오른쪽 화살표 A(3,2^{65536}-3)\\&\qquad \vdots \\\오른쪽 화살표 2^{2^{65536}-3.\\end{aigned}}$

값표

Ackermann 함수를 계산하는 것은 무한대의 표의 관점에서 재작성될 수 있다.먼저 맨 위 행을 따라 자연수를 배치한다.표에서 숫자를 결정하려면 번호를 즉시 왼쪽으로 이동하십시오.그런 다음 해당 번호와 한 행 위로 제공된 열에서 필요한 숫자를 찾으려면 이 번호를 사용하십시오.왼쪽에 숫자가 없으면 이전 행의 "1"로 표시된 열을 보십시오.다음은 표의 왼쪽 상단 부분:

A(m, n)의 값

n m	0	1	2	3	4	n
0	1	2	3	4	5	${\displaystyle n+1}$
1	2	3	4	5	6	${\displaystyle n+2=2+(n+3)-3}$
2	3	5	7	9	11	${\displaystyle 2n+3=2\cdot(n+3)-3}$
3	5	13	29	61	125	${\displaystyle 2^{(n+3)-3}$
4	13 ${\displaystyle ={2^{2^{2}}-3}$ $\displaystyle =2\uparrow \uparrow 3-3}$	65533 ${\displaystyle ={2^{2^{2}}-3}$ $\displaystyle =2\uparrow \uparrow 4-3}$	265536 − 3 ${\displaystyle ={2^{2^{2^{2}}-3}$ $\displaystyle =2\uparrow \uparrow 5-3}$	${\displaystyle {2^{2^{65536}}-3}$ ${\displaystyle ={2^{2^{2^{2^{2}}:}}}}$ $\displaystyle =2\uparrow \uparrow 6-3}$	${\displaystyle{2^{2^{65536}}}}}$ ${\displaystyle ={2^{2^{2^{2^{2^{2}}}}}}}$ $\displaystyle =2\uparrow \uparrow 7-3}$	${\displaystyle {\cd}\underbrace {{2^{2}}^{{\cdot }^{{\cdot }^{{\cdot }2}} _{n+3}-3-end{nd}}}}}}}}}$ $\displaystyle =2\uparrow \uparrow (n+3)-3}$
5	65533 ${\displaystyle =2\uparrow \uparrow \uparrow \uparrow 2)-3}$ ${\displaystyle =2\uparrow \uparrow 3-3}$	$\displaystyle 2\uparrow \uparrow 4-3}$	$\displaystyle 2\uparrow \uparrow \uparrow 5-3}$	$\displaystyle 2\uparrow \uparrow 6-3}$	$\displaystyle 2\uparrow \uparrow 7-3}$	$\displaystyle 2\uparrow \uparrow \uparrow (n+3)-3}$
6	$\displaystyle 2\uparrow \uparrow \uparrow 3-3}$	$\displaystyle 2\uparrow \uparrow \uparrow 4-3}$	$\displaystyle 2\uparrow \uparrow \uparrow 5-3}$	$\displaystyle 2\uparrow \uparrow \uparrow 6-3}$	$\displaystyle 2\uparrow \uparrow \uparrow 7-3}$	$\displaystyle 2\uparrow \uparrow \uparrow \uparrow (n+3)-3}$
m	${\displaystyle(2\to 3\to (m-2)--3}$	${\displaystyle(2\to 4\to (m-2)--3}$	$(2\displaystyle (2\to 5\to (m-2)-}$	${\displaystyle(2\to 6\to (m-2)--3}$	${\displaystyle(2\to 7\to (m-2)-3}$	${\displaystyle(2\to(n+3)\to(m-2)--3}$

여기서 재귀적 지수화 또는 크누스 화살표로만 표현되는 숫자는 매우 크며, 너무 많은 공간을 차지하여 일반 소수 자릿수로 표기할 수 없다.

이 표의 초기 부분에서 큰 값이 발생함에도 불구하고, 크누스 화살표의 적은 숫자로 쓸 수 없는 그레이엄의 숫자와 같은 몇몇 더 큰 숫자가 정의되었다.이 숫자는 Ackermann 함수를 반복적으로 자신에게 적용하는 것과 유사한 기법으로 구성된다.

위 표의 반복이지만, 함수 정의의 관련 표현으로 대체된 값을 사용하여 패턴을 명확하게 보여준다.

A(m, n)의 값

n m	0	1	2	3	4	n
0	0+1	1+1	2+1	3+1	4+1	n + 1
1	A(0, 1)	A(0, A(1, 0) = A(0, 2)	A(0, A(1, 1) = A(0, 3)	A(0, A(1, 2) = A(0, 4)	A(0, A(1, 3) = A(0, 5)	A(0, A(1, n-1)
2	A(1, 1)	A(1, A(2, 0) = A(1, 3)	A(1, A(2, 1) = A(1, 5)	A(1, A(2, 2) = A(1, 7)	A(1, A(2, 3) = A(1, 9)	A(1, A(2, n-1)
3	A(2, 1)	A(2, A(3, 0) = A(2, 5)	A(2, A(3, 1) = A(2, 13)	A(2), A(3, 2) = A(2, 29)	A(2), A(3, 3) = A(2, 61)	A(2, A(3, n-1)
4	A(3, 1)	A(3, A(4, 0) = A(3, 13)	A(3, A(4, 1) = A(3, 655333)	A(3, A(4, 2)	A(3, A(4, 3)	A(3, A(4, n-1)
5	A(4, 1)	A(4, A(5, 0)	A(4, A(5, 1)	A(4, A(5, 2)	A(4, A(5, 3)	A(4, A(5, n-1)
6	A(5, 1)	A(5, A(6, 0)	A(5, A(6, 1)	A(5, A(6, 2)	A(5, A(6, 3)	A(5, A(6, n-1)

특성.

일반적 발언

• $A{\displaystyle }$( ${\displaystyle m}$, n$){\displaystyle A(m,n)}$의 평가가 항상$$ 종료되는 것은 즉시 분명하지 않을 수 있다.그러나 각 재귀 $애플리케이션$에서 m ${\displaystyle m}$이(가) 감소하거나 m ${\displaystyle m}$이(가) 동일하게 유지되고$$ $n{\displaystyle }$ ${\displaystyle n$}이$$(가) 감소하기 때문에 재귀가 제한된다.$n{\displaystyle }$ ${\displaystyle n}$이(가$$) $0$에 도달할$$때마다$$m {\$displaystyle m}$이(가) 감소하므로$$ $m{\displaystyle }$ {\$displaystyle m}$도 결국$$ 0에 도달한다.(더 기술적으로 표현하면 각 경우 쌍$({\displaystyle m}$, ${\displaystyle n}$) ${\displaystyle(m,n)$은 쌍에 대한 사전 순서가 감소하는데$$, 이는 의 순서와 같다.음이 아닌 단일 정수, 즉 연속적으로 무한히 여러 번 연속해서 내려갈 수 없다는 것을 의미한다.)그러나 $m{\displaystyle }$ ${\displaystyle m}$이(가) 감소하면 $n{\displaystyle }$ ${\displaystyle n}$이(가) 얼마나 증가할 수 있는지에$$ 대한 상한은 없으며 종종 크게 증가할 것이다.
• m과 같은 작은 값의 경우, ackermann 함수는 n(최대 기하급수적으로)에 대해 상대적으로 느리게 성장한다.그러나 $m{\displaystyle }$ ${\displaystyle \ge }$ ${\displaystyle 4}$ ${\displaystyle m\geq$ 4$\}$의 경우 훨씬 더 빠르게 성장하며, 심지어 $A{\displaystyle }$(${\displaystyle 4,}$ 2${\displaystyle }$) ${\displaystyle A (4,$ 2)도 약 2×10이며$$¹⁹⁷²⁸, A (4, 3)의 십진 확장도 어떤 전형적인 척도로 보아도 매우 크다.
• 흥미로운 점은 그것이 지금까지 사용한 유일한 산술 연산은 1을 더하는 것이라는 것이다.그것의 빠른 성장 동력은 단지 내포된 재귀에 기초한다.이것은 또한 그것의 가동 시간이 최소한 그것의 생산량에 비례한다는 것을 의미하며, 또한 매우 크다.실제로 대부분의 경우 실행 시간은 출력보다 훨씬 크다. 위 내용을 참조하십시오.
• 단일 인수 버전 $f{\displaystyle (}$$n$ ) =${\displaystyle A(n,}$ n$){\$$displaystyle$ $f(n$$)=$$A{\displaystyle }$$(n$$,n)}$는 지수함수, 요인함수, 다요소, 초요인 펑크와 같은 매우 빠르게 성장하는 함수를 포함하여 $모든{\displaystyle }$ 원시 재귀함수를 동시에$$ 증가시킨다$.$Tions, 그리고 Knuth의 위쪽 화살표 표기법을 사용하여 정의된 함수(인덱스된 위쪽 화살표를 사용하는 경우는 제외).급성장하는 계층 $구조$에서${\displaystyle }$$f{\displaystyle {}_{}}$${\displaystyle }$(${\displaystyle n_{}}$ )$${\$displaystyle$ f${\displaystyle (n{}_{}}${\$displaystyle f_{\omega }(n)}$과 대략 비슷한 수준임을 알 수 있다.$이러한{\displaystyle }$ 극단적인 성장은 튜링 기계와 같은 무한한 메모리를 가진 시스템에서 계산이 가능하고 계산 가능한 함수인 f$$ ${\displaystyle$ f$}$이(가) 어떤 원시 재귀 함수보다 빠르게 성장하며 따라서 원시 재귀 함수가 아님을 보여주는 데 이용될 수 있다.

원시 재귀가 아님

아커만 함수는 어떤 원시 재귀함수보다 빨리 성장하므로 그 자체가 원시 재귀함수는 아니다.

구체적으로는 모든 원시 재귀 $함수{\displaystyle }$ f${\displaystyle ({}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$,${\displaystyle }$… ,${\displaystyle }$x ${\displaystyle n_{}}$) ${\displaystyle f(x_{1},\ldots,x_$${n}}}$에 음이 아닌 정수 $t{\displaystyle }$ ${\$$displaystyt$ $t}$이(가) 존재한다는 것을 보여준다$.$ 이러한 정수$$ t는 $음$이 $아닌$ 모든 정수 x 1${\displaystyle {}_{}}$,${\displaystyle }$x 1 , x ${\displaystyle n_{}}$에 대해 음을 $나타내지 않는다.$

${\displaystyle f(x_{1},\ldots ,x_{n}}<A(t,\max _{i}x_{i}).}$

${\displaystyle {일단\mathrm{}}_{}}$ 이것이 성립되면$,$ $x{\displaystyle }$ $1{\displaystyle {}_{}}$= ${\displaystyle x}$ ${\displaystyle {2\mathrm{}}_{}}$= t ${\displaystyle x_{1}=x_{2}=t}$를 붙이면 모순 , )< A )$<<A(t,t$)>. {\$displaystystyle A($t,$t,t$$)$ 자체는$$ 원시적인 재귀가 아니라는 것을 따른다$.$$}$

증명은^[18] 다음과 같이 진행된다: Ackermann 함수보다 느리게 증가하는 모든 함수의 $클래스$ A ${\${\$mathcal {A}$을(를) 정의하십시오.

${\displaystyle {\mathcal {A}=\f\{f\,{\bigg }\exists t\\forall x_{n}\f(x_{n}),\f(x_{n},\ldots,x_{n}}}}<A(t,\max }x_{i}_{i}).$

$그리고{\displaystyle \mathcal{}}$ A ${\$에 모든 원시 재귀 함수가 포함되어$$ 있음을 보여준다.후자는 $A{\displaystyle \mathcal{}}$ ${\$이(가) 상수함수, 후계함수, 투영함수를 포함하고$$ 있으며, 함수구성 및 원시 재귀의 연산에 따라 폐쇄됨을 보여줌으로써 달성된다.

반비례

위에서 고려한 함수 f(n) = A(n, n)가 매우 빠르게 성장하기 때문에 역 함수 f는⁻¹ 매우 느리게 성장한다.이 역 Ackermann 함수 f는⁻¹ 보통 α로 표시된다.실제로 A(4, 4)는 2 $2{\displaystyle {\mathrm{}}^{}}$ ${\displaystyle {2{\mathrm{}}^{}}^{}}$ ${\displaystyle {{2{\mathrm{}}^{}}^{}}^{}}$ 2 ${\displaystyle {{{{16}^{}}^{}}^{}}^{}}$ ${\$^{16$}}}$의 순서에 있기 때문에 α(n)는 어떤 실제 입력 크기 n에 대해서도 5보다 작다$.$

이 역행은 최소 스패닝 트리에 대한 분리 집합 데이터 구조와 샤젤의 알고리즘과 같은 일부 알고리즘의 시간 복잡성에 나타난다.때로는 아커만의 원래 기능이나 다른 변형이 이 설정에 사용되기도 하지만 모두 비슷하게 높은 비율로 성장한다.특히 일부 수정된 함수는 -3 및 이와 유사한 용어를 제거하여 표현을 단순화한다.

역 Ackermann 함수의 2-모수 변동은 다음과 같이 정의할 수 있으며, 여기서 $\lfloor {\displaystyle }$ ${\displaystyle x}$ ${\displaystyle \rfloor }$ ${\displaystyle \lfloor$x\$rfloor}$은 플로어 함수다.

${\displaystyle \alpha(m,n)=\min\{i\geq 1:A(i,\lfloor m/n\rfloor )\geq \log _{2}n\}}$

이 함수는 위에서 언급한 알고리즘의 보다 정밀한 분석에서 발생하며, 보다 정교한 시간 범위를 제공한다.이산설정 데이터 구조에서 m은 연산의 개수를 나타내는 반면 n은 원소의 개수를 나타내는 반면, 최소 스패닝 트리 알고리즘에서는 m은 에지의 개수를, n은 정점의 개수를 나타낸다.α(m, n)에 대한 몇 가지 약간 다른 정의가 존재한다. 예를 들어, 로그₂ n은 n으로 대체되는 경우도 있고, 바닥 기능은 천장으로 대체되는 경우도 있다.

다른 연구에서는 m이 상수로 설정된 경우 특정 행에 역 함수를 적용할 수 있는 역 함수를 정의할 수 있다.^[19]

아커만 함수의 역행은 원시적인 재귀성이다.^[20]

벤치마크로 사용

Ackermann 함수는 극히 깊은 재귀라는 관점에서 정의되기 때문에 컴파일러의 재귀 최적화 능력에 대한 벤치마크로 사용할 수 있다.아커만의 기능을 이런 식으로 처음 출판한 것은 1970년 드라고흐 바이다에^[21] 의해, 그리고 1971년 거의 동시에 Yngve Sundblad에 의해서였다.^[13]

선드블라드의 세미날 논문은 브라이언 비히만(Whtstone 벤치마크의 공동저자)이 1975년부터 1982년 사이에 쓴 3부작의 논문에서 차지했다.^[22][23][24]

참고 항목

• 계산성 이론
• 이중재귀
• 빠르게 성장하는 계층 구조
• 굿스타인 함수
• 원시재귀함수
• 재귀(컴퓨터 과학)

메모들

참조

참고 문헌 목록

외부 링크

• "Ackermann function". Encyclopedia of Mathematics. EMS Press. 2001 [1994].
• Weisstein, Eric W. "Ackermann function". MathWorld.
• 이 문서에는 NIST 문서의 공용 도메인 자료가 포함되어 있다.
• 애니메이션 애커만 함수 계산기
• a for 루프를 사용하여 구현된 Ackerman 함수
• 스콧 애런슨, 누가 가장 많은 숫자를 댈 수 있을까?(1999)
• 아커만 함수.일부 값의 표를 포함한다.
• 하이퍼 오퍼레이션:아커만의 기능과 새로운 산술 연산
• Robert Munafo의 Large Numbers는 A의 정의에 대한 몇 가지 변형을 설명한다.
• 가브리엘 니바슈, 역 아커만 함수에 통증이 없는 역 아커만.
• Raimund Saidel, 역 Ackermann 함수의 이해(PDF 프레젠테이션)
• 다른 프로그래밍 언어로 작성된 Ackermann 함수(Rosetta Code)
• Ackermann의 기능 (아카이브 2009-10-24)—해리 J. 스미스의 연구와 프로그래밍.