커누스 윗화살표 표기법

최근 수정 시각 : 2023-05-28 22:18:58 | 조회수 : 28

Knuth's up-arrow notation

도널드 크누스가 1976년에 개발한 것으로, 반복되는 거듭제곱을 나타내기 위해 사용된다.

목차

1. 정의
2. 명명
3. 표현
4. 주의
5. 보기
6. 영상

1. 정의

x,yNx,y \in \mathbb{N}, 2nN2≤n\in\mathbb{N}에 대해 x1y=xyx\uparrow^1 y = x^y라 하면

xny=xn1xn1xn1y timex \uparrow ^n y=\underbrace{x \uparrow ^{n-1} x \uparrow ^{n-1} x \uparrow ^{n-1} \cdot\cdot\cdot}_{y\ \mathrm{time}}

과 같이 귀납적으로 정의한다.

2. 명명

  • n이 1일 때의 연산을 거듭제곱(Power)이라고 한다.
  • n이 2일 때의 연산을 테트레이션(Tetration)이라고 한다.
  • n이 3일 때의 연산을 펜테이션(Pentation)이라고 한다.
  • n이 4일 때의 연산을 헥세이션(Hexation)이라고 한다.

3. 표현

x,y,zNx,y,z \in \mathbb{N}에 대해
  • xzy=xz timeyx\uparrow^{z} y = x\underbrace{\uparrow\uparrow\uparrow\cdots\uparrow}_{z\ \mathrm{time}} y
  • xyz=xyzx\uparrow y \uparrow z = x^{y^z}
  • xyz=x2y2z=xxxy timexxxy timez timex\uparrow\uparrow y \uparrow\uparrow z = x \uparrow ^2 y \uparrow ^2 z=\underbrace{\underbrace{x \uparrow x \uparrow x \uparrow \cdot\cdot\cdot}_{y\ \mathrm{time}} \uparrow \underbrace{x \uparrow x \uparrow x \uparrow \cdot\cdot\cdot}_{y\ \mathrm{time}} \uparrow \cdot\cdot\cdot}_{z\ \mathrm{time}}

4. 주의

xyz=xyzx\uparrow y \uparrow z = x^{y^z}의 값은, (xy)z=xyz(x^{y})^{z}=x^{yz} 가 아닌 x(yz)x^{(y^z)}로 구해야 한다.

5. 보기

  • 애커만 함수
  • 하이퍼 연산
  • 그레이엄 수

6. 영상



이 문서의 내용 중 전체 또는 일부는 오메가에서 가져왔으며 CC BY-NC-SA 3.0에 따라 이용할 수 있습니다.