하이퍼 연산 수학에서 하이퍼 연산(Hyperoperation)은 기본적인 산술 연산(덧셈, 곱셈, 거듭제곱 등)을 일반화하여 무한한 수열로 확장한 개념이다. 이 수열은 0단계(후계자 함수)부터 시작하여 1단계(덧셈), 2단계(곱셈), 3단계(거듭제곱), 4단계(테트레이션), 5단계(펜테이션) 등으로 이어지며, 각 단계는 이전 단계의 반복으로 정의된다.
정의와 수열 일반적으로 $n$단계 하이퍼 연산을 $H_n(a, b)$로 표기하며, 다음과 같이 재귀적으로 정의된다(Goodstein의 정의 기준).
- $H_0(a, b) = b + 1$ (후계자 함수, $a$와 무관)
- $H_1(a, b) = a + b$ (덧셈)
- $H_2(a, b) = a \times b$ (곱셈)
- $H_3(a, b) = a^b$ (거듭제곱)
- $H_4(a, b) = {}^b a$ (테트레이션: $a$를 $b$번 거듭제곱으로 쌓음)
- $H_{n+1}(a, b) = H_n(a, H_{n+1}(a, b-1))$ (단, $b > 0$이며 적절한 기본 케이스 적용)
표기법 높은 단계의 하이퍼 연산을 표현하기 위해 여러 표기법이 개발되었다.
- 크누스 위쪽 화살표 표기법 (Knuth's up-arrow notation):
- $a \uparrow b = a^b$ (거듭제곱)
- $a \uparrow\uparrow b = {}^b a$ (테트레이션)
- $a \uparrow^n b$ ($n$개의 화살표)는 $n+2$단계 하이퍼 연산에 대응.
- 콘웨이 체인 화살표 표기법 (Conway chained arrow notation): 더 거대한 수를 표현하기 위한 확장 표기법.
- 박스 표기법 (Box notation) / 굿스타인 표기법: 초기 정의에서 사용된 방식.
역사
- 1914년 빌헬름 아커만(Wilhelm Ackermann)이 아커만 함수를 통해 재귀 함수의 개념을 연구하며 초거대 수의 증가율을 다룸.
- 1947년 R. L. 굿스타인(Reuben Goodstein)이 이 연산 수열을 체계화하고 '하이퍼 연산'이라는 용어를 제안하며 테트레이션, 펜테이션 등의 이름을 붙임.
- 1976년 도널드 크누스(Donald Knuth)가 위쪽 화살표 표기법을 도입하여 컴퓨터 과학과 조합론에서 널리 쓰이게 함.
수학적 의의
- 계산 복잡도와 거대 수 연구: 하이퍼 연산은 매우 빠르게 증가하는 함수들을 분류하는 기준이 되며, 그레이엄 수(Graham's number)나 티리(TRY) 함수 등 거대 수를 정의하는 토대가 된다.
- 컴퓨터 과학: 알고리즘의 시간 복잡도 분석(예: 아커만 함수의 역함수 $\alpha(n)$)이나 자료 구조(Disjoint-set 등)의 분석에 등장한다.
- 논리학 및 집합론: 원시 재귀 함수를 넘어서는 일반 재귀 함수의 성장률을 계층화하는 그르초프스키 위계(Grzegorczyk hierarchy) 등과 연관된다.
한계와 확장 정수 단계($n \in \mathbb{N}$)에 대한 정의는 명확하나, 분수나 실수, 복소수 단계로의 확장(분수 반복, Fractional iteration)은 수학적으로 아직 완전히 정립되지 않은 연구 주제이다. 테트레이션($H_4$) 이상의 연산은 결합 법칙과 교환 법칙이 성립하지 않으며, 항등원과 역원 개념도 일반적이지 않다.
