하이퍼 연산

3. 표기법

하이퍼 연산은 덧셈, 곱셈, 거듭제곱 등의 기본적인 연산을 확장한 것으로, 이를 나타내는 다양한 표기법이 존재한다.

{| class="wikitable"

|-

! 이름

! 표기법

! 비고

|-

| '''기본 화살표 표기법'''

| $a\; \backslash uparrow^\{n-2\}\; b\; =\; H\_n(a,\; b)$

| 커누스가 최초로 사용^[10]

|-

| ''굿스틴 표기법''

| $G(n,\; a,\; b)$

| 굿스틴(Goodstein)이 최초로 사용^[12]

|-

| ''초기 아커만 함수''

| $A(a,\; b,\; n-1)\; =\; H\_n(a,\; b)$

| 하이퍼 연산과는 약간 다르다.

|-

| ''현대 아커만 함수''

| $A(n,\; b\; -\; 3)\; +\; 3\; =\; H\_n(2,\; b)$

| 밑이 2일 때의 하이퍼 연산과 동일하다.

|-

| ''냄비어 표기법''

| $a\; \backslash otimes^n\; b$

| 냄비어(Nambiar)가 최초로 사용^[11]

|-

| 상자 표기법

| $a\; \{\backslash ,\backslash begin\{array\}$

5. 계산

하이퍼 연산의 기본 정의는 다음 축약 규칙을 따른다.^[1]

$H\_\{n\}(a,\; b)$를 계산하기 위해, 초기에는 $\backslash langle\; n,a,b\; \backslash rangle$ 요소를 포함하는 스택을 사용한다. 그런 다음, 더 이상 불가능할 때까지 세 개의 요소를 꺼내고 다음 규칙에 따라 대체한다.^[1]

하이퍼 연산은 이처럼 스택을 활용하여 계산할 수 있으며, 구체적인 예시는 #TRS 기반 계산에서 확인할 수 있다.

하이퍼 연산의 표기법은 다음과 같다.

5. 1. TRS 기반 계산

간단히 설명하면, $\backslash langle\; n,a,b\; \backslash rangle$에서 시작하여 스택 길이가 1이 될 때까지 3개의 요소를 꺼내고 규칙 r1, r2, r3, r4, r5에 따라 1개 또는 5개의 요소를 집어넣는 과정을 반복한다.
예시: $H\_2(2,2)\; \backslash rightarrow\_\{*\}\; 4$ 계산^[1][2]

축약 과정은 다음과 같다.

스택을 사용한 구현에서 입력 $\backslash langle\; 2,2,2\; \backslash rangle$에 대한 스택 구성과 해당 방정식은 다음과 같다.

반복을 사용한 정의는 다른 축약 규칙을 사용하며, 스택에는 네 개의 요소 $\backslash langle\; 1,n,a,b\; \backslash rangle$가 초기값으로 들어간다. 계산 과정에서 네 개의 요소를 꺼내 규칙에 따라 1개 또는 7개의 요소로 대체한다.^[1]

규칙 {r6 - r10, r11}에 따른 $H\_\{n\}(a,b)$ 계산은 재귀적이다. 반복이 실행되는 순서 때문에 전체 시퀀스가 펼쳐진 후에야 첫 번째 $H$가 사라진다.^[3] 반면, 규칙 {r6 - r10, r12}에 따른 계산은 더 효율적이며, 재귀 깊이는 초연산 순서와 일치한다.^[4] 어느 쪽으로 반복하든 동일한 규칙을 포함하므로 축약 단계 수는 동일하다. 축약 규칙이 적용되는 순서만 영향을 받는다.

6. 특수한 경우

''H_n''(0, ''b'')의 값은 다음과 같다.^[6][7]

• n = 0일 때, ''b'' + 1
• n = 1일 때, ''b''
• n = 2일 때, 0
• n = 3이고 ''b'' = 0일 때, 1
• n = 3이고 ''b'' > 0일 때, 0
• n > 3이고 ''b''가 짝수일 때 (0 포함), 1
• n > 3이고 ''b''가 홀수일 때, 0

• n = 2일 때, ''b''
• n ≥ 3일 때, 1

• n = 2일 때, 0
• n = 0 또는 n ≥ 3일 때, 1
• n = 1일 때, ''a''

• n ≥ 2일 때, ''a''

• n ≥ 1일 때, ''H_n+1''(''a'', 2)

• n = 0 또는 n ≥ 4일 때, 0
• n = 1일 때, ''a'' − 1
• n = 2일 때, −''a''
• n = 3일 때, (분수형태)

• n = 0일 때, 3
• n ≥ 1일 때, 4 (재귀적으로 쉽게 증명 가능)

7. 역사

하이퍼 연산은 1914년 알베르트 베네트가 처음 논의했는데, 그는 "가환 하이퍼 연산" 이론을 개발했다.^[9] 1928년 빌헬름 아커만은 하이퍼 연산 수열과 어느 정도 연관성이 있는 함수 $\backslash phi(a,\; b,\; n)$을 정의했다.^[9]

1947년 루벤 굿스타인^[12]은 현재 사용되는 하이퍼 연산 수열을 정의하고, 커누스 윗화살표 표기법으로는 $a\; \backslash uparrow^\{n-2\}b$와 같은 $G(n,a,b)$ 기호를 사용했다. 또한, 굿스타인은 테트레이션, 펜테이션, 헥세이션 등 거듭제곱 이상의 연산에 명칭을 부여했다.

굿스타인의 정의는 원래 아커만 함수와 몇 가지 차이점이 있다. 원래의 삼항 아커만 함수 $\backslash phi$는 굿스타인 버전과 동일한 재귀 규칙을 사용하지만, 두 가지 면에서 다르다. 첫째, $\backslash phi(a,\; b,\; n)$은 승계 함수가 아닌 덧셈(''n'' = 0)에서 시작하는 연산 시퀀스를 정의하고, 이후 곱셈(''n'' = 1), 지수 연산(''n'' = 2) 등을 정의한다. 둘째, $\backslash phi$에 대한 초기 조건은 $\backslash phi(a,\; b,\; 3)\; =\; G(4,a,b+1)\; =\; a\; [4]\; (b\; +\; 1)$의 결과를 가져오므로 지수 연산을 넘어서는 하이퍼 연산과 차이가 있다.

8. 변형

하이퍼 연산에는 다양한 변형이 존재한다. 그중 하나는 왼쪽에서 오른쪽으로 연산하는 방식으로, 다음과 같이 정의된다. (° 또는 아래 첨자 사용):

:$a\_\{(n+1)\}b\; =\; \backslash left(a\_\{(n\; +\; 1)\}(b\; -\; 1)\backslash right)\_\{(n)\}\; a$

여기서

:$\backslash begin\{align\}$

a_{(1)} b &= a + b \\

a_{(2)} 0 &= 0 \\

a_{(n)} 1 &= a & \text{for } n>2 \\

\end{align}

이것은 도너(Doner)와 타르스키(Tarski)에 의해 서수로 확장되었다.^[8] ''a'' ≥ 2이고 ''b'' ≥ 1인 경우,

:$a\; O\_n\; b\; =\; a\_\{(n\; +\; 1)\}\; b$

가 성립한다. 그러나 이 연산은 하이퍼 연산에서 전통적으로 예상되는 "지수탑"을 형성하지 못하고 붕괴된다.^[8] 예를 들어,

:$\backslash alpha\_\{(4)\}(1\; +\; \backslash beta)\; =\; \backslash alpha^\{\backslash left(\backslash alpha^\backslash beta\backslash right)\}.$

이다. 만약 α ≥ 2이고 γ ≥ 2이면,^{[Corollary 33(i)][8]}

:$\backslash alpha\_\{(1\; +\; 2\backslash gamma\; +\; 1)\}\backslash beta\; \backslash leq\; \backslash alpha\_\{(1\; +\; 2\backslash gamma)\}(1\; +\; 3\backslash alpha\backslash beta).$

이다.

8. 1. ''a''에서 시작하는 변형

8. 2. 아래첨자 하이퍼 연산자

• a₍₁₎ b = a + b
• a₍₂₎ 0 = 0
• n>2일 때, a_(n) 1 = a

8. 3. 가환 하이퍼 연산

9. 수 체계

R. L. 굿스타인은 하이퍼 연산 수열을 기반으로 음이 아닌 정수를 표현하는 수 체계를 제시했다.^[1] 이 수 체계에서 정수 ''n''의 ''완전한 유전적 표현''은 레벨 ''k''와 밑 ''b''에서 처음 ''k''개의 하이퍼 연산자와 숫자 0, 1, ..., ''b'' − 1, 그리고 밑 ''b''만을 사용하여 표현된다.

• 0 ≤ ''n'' ≤ ''b'' − 1인 경우, ''n''은 해당 숫자로 표현된다.
• ''n'' > ''b'' − 1인 경우, ''n''은 먼저 다음과 같은 형태로 표현된다.

• 레벨-1 표현: b [1] X 형식 (''X''도 이 형식)
• 레벨-2 표현: b [2] X [1] Y 형식 (''X'', ''Y''도 이 형식)
• 레벨-3 표현: b [3] X [2] Y [1] Z 형식 (''X'', ''Y'', ''Z''도 이 형식)
• 레벨-4 표현: b [4] X [3] Y [2] Z [1] W 형식 (''X'', ''Y'', ''Z'', ''W''도 이 형식)

• 레벨 1: 266 = 2 [1] 2 [1] 2 [1] ... [1] 2 (133개의 2)
• 레벨 2: 266 = 2 [2] (2 [2] (2 [2] (2 [2] 2 [2] 2 [2] 2 [2] 2 [1] 1)) [1] 1)
• 레벨 3: 266 = 2 [3] 2 [3] (2 [1] 1) [1] 2 [3] (2 [1] 1) [1] 2
• 레벨 4: 266 = 2 [4] (2 [1] 1) [3] 2 [1] 2 [4] 2 [2] 2 [1] 2
• 레벨 5: 266 = 2 [5] 2 [4] 2 [1] 2 [5] 2 [2] 2 [1] 2

참조

_[1] 문서
_[2] 문서
_[3] 간행물
_[4] 문서
_[5] 문서
_[6] 문서
_[7] 문서
_[8] 문서
_[9] 저널 Zum Hilbertschen Aufbau der reellen Zahlen https://archive.org/[...]
_[10] 저널 Mathematics and Computer Science: Coping with Finiteness http://www.sciencema[...] 2009-04-21
_[11] 저널 Ackermann Functions and Transfinite Ordinals http://www.sciencema[...] 2009-04-21
_[12] 저널 Transfinite Ordinals in Recursive Number Theory http://www.jstor.org[...] 2009-04-17
_[13] 웹인용 Inventing New Operators and Functions http://www.mrob.com/[...] 1999-11
_[14] 웹인용 Ackermann's Function and New Arithmetical Operation http://forum.wolfram[...] 2005-12