커누스 윗화살표 표기법

'''커누스 윗화살표 표기법'''(Knuth's up-arrow notation)은 도널드 커누스가 1976년에 개발한 아주 큰 수를 표기하는 방법이다. 이 표기법은 아커만 함수와 특히 하이퍼 연산 수열과 매우 밀접한 관련이 있으며, 곱셈은 반복되는 덧셈으로 볼 수 있고, 거듭제곱도 반복되는 곱셈으로 볼 수 있다는 사실에 기반해서 아이디어를 얻었다. 이런 방식으로 계속하면 테트레이션(반복된 거듭제곱)과 보통 커누스 윗화살표 표기법으로 표시되는 하이퍼 연산 수열의 나머지로 이어진다. 이 표기법은 명시적으로 쓸 수 있는 수보다 훨씬 더 큰 수를 간단하게 표기할 수 있다.
윗화살표 한 개는 거듭제곱(반복되는 곱셈)을 의미하고, 한 개 이상의 윗화살표는 한 개 적은 화살표를 반복하는 것을 의미한다.
예를 들어,
* 윗화살표 한 개는 곱셈의 반복(거듭제곱)이다 
* 윗화살표 두 개는 거듭제곱의 반복(테트레이션)이다 
* 윗화살표 세 개는 테트레이션의 반복(펜테이션)이다 
이 표기법의 일반적인 정의는 다음과 같다(정수 ''a''와 음이 아닌 정수 ''b'',''n''에 대해서):
: 
덧셈, 곱셈, 그리고 거듭제곱의 일반 산술 연산은 자연적으로 다음과 같이 하이퍼 연산의 수열로 확장된다.
자연수에 의한 곱셈은 덧셈의 반복으로 정의된다:
:
예를 들면,
:
자연수 지수 에 의한 거듭제곱은 곱셈의 반복으로 정의되며, 커누스는 윗화살표 한 개로 표기했다:
:
예를 들면,
:
연산의 수열을 거듭제곱을 넘어서 확장하기 위해서 커누스는 거듭제곱의 반복(테트레이션)을 의미하는 “이중 윗화살표” 연산을 정의했다:
:
예를 들면,
:
여기와 아래의 계산은 오른쪽에서 왼쪽으로 일어난다, 왜냐하면 커누스 윗화살표 연산(거듭제곱과 같은)은 Right associative 연산으로 정의했기 때문이다.
이 정의에 의해서,
:
:
:
:
:etc.
이것만 해도 상당히 큰 수가 나오지만 커누스는 이 표기법을 확장했다. 커누스는 테트레이션의 반복(펜테이션)을 의미하는 “삼중 윗화살표” 연산을 정의했다:
:
잇따라 “사중 윗화살표“ 연산은 펜테이션의 반복(헥세이션)을 의미한다:
:
그리고 계속된다. 일반적인 규칙은 중 윗화살표 연산은 right-associative ()중 윗화살표 연산으로 확장할 수 있다는 것이다. 기호적으로는
:
예시:
:
:
의 표기는 일반적으로 에서 윗화살표가 ''n''개인 것을 나타낸다. 사실 는 하이퍼 연산으로 ''a'' ''n''+2 ''b''이다. 예를 들어, 는 39 4 14 ("4"는 테트레이션을 의미한다)로 쓸 수 있지만 39 2 14 = 39 × 14 = 546인 것은 아니다. 비슷하게, 은 77 79 77이지 77 77 77이 아니다.
와 같은 표현에서, 거듭제곱의 표기법은 보통 지수 를 밑 의 윗 첨자로 쓴다. 하지만 많은 프로그래밍 언어나 이메일같은 환경은 윗첨자 조판을 지원하지 않는다. 이런 환경에서 선형 표기법인 를 적용했다. 윗화살표는 '다음을 지수로 올린다'는 것을 제시한다. 문자 인코딩에서는 윗화살표를 포함하지 않기 때문에 캐럿(^)을 대신해서 쓴다.
윗첨자 표기법 는 일반화에 도움이 되지 않는다, 이것이 커누스가 인라인 표기법 를 대신에 쓴 이유이다.
는 윗화살표 n개의 더 짧은 표기법이다. 따라서 이다.
===윗화살표 표기법을 거듭제곱으로 쓰기===
를 익숙한 윗첨자 표기법으로 쓰려고 하면 거듭제곱의 탑을 얻게 된다.
:예: 
''b''가 변수면 (또는 너무 크면), 거듭제곱의 탑은 점들과 탑의 높이를 나타내는 표시로 써야 할 수 있다.
:
이 표기법으로 계속하면, 는 각각이 위의 탑의 높이를 나타내는 거듭제곱의 탑의 스택으로 쓸 수 있다.
:
또 ''b''가 변수거나 너무 클 경우에는 스택도 점들과 스택의 높이를 나타내는 표시로 써야 할 수 있다.
:
더 나아가서, 는 각각이 왼쪽의 스택의 개수를 나타내는 거듭제곱의 탑의 스택의 열로 쓸 수 있다:
:
또다시 일반적으로:
:
이것은 을 어떤 ''a'', ''n''과 ''b''에 대해서든지 (비록 이것이 분명히 더 번거롭지만) 반복되는 거듭제곱의 반복외는 거듭제곱으로 부정적으로 나타낼 수 있다는 것을 나타낸다.
====테트레이션을 사용====
테트레이션 표기법 는 여전히 기하학적 표현 (이것을 ''테트레이션의 탑''이라고 부른다)을 사용하지만 이 다이어그램을 약간 간단하게 만든다.
: 
: 
: 
결국, 한 예로 네 번째 아커만 수 는 다음과 같이 나타낼 수 있다:
: 
어떤 수는 너무 커서 커누스 윗화살표 표기법으로 쓰기에도 버거울 수 있다. 그러면 ''n''중 화살표 연산 이나 동동한 하이퍼 연산이 유용하다 (그리고 화살표의 개수가 변수일 때를 나타낼 때도 유용하다).
어떤 수는 너무 커서 이 표기법도 충분하지 않을 수 있다. 그러면 콘웨이 연쇄 화살표 표기법을 쓸 수 있다: 세 원소들의 연쇄 화살표는 다른 표기법과 동일하지만, 길이가 4 이상이면 더 강력하다.
:
보통 커누스 윗화살표는 비교적 작은 수에, 연쇄 화살표나 하이퍼 연산은 더 큰 수에 써야 한다고 주장한다.
윗화살표 표기법은 공식적으로 인 모든 정수 에 대해서 다음과 같이 정의된다.
:
이 정의는 곱셈을 기본 연산으로 두고, 거듭제곱 을 곱셈의 반복으로, 테트레이션 을 거듭제곱의 반복으로, 등등을 얻는다. (이 정의는 더 기본적인 두 함수가 없는것을 제외하고 하이퍼 연산 수열과 동등핟다. 여기서 없는 함수는 다음수와 덧셈으로, 이 함수를 포함하려면 정의를 더 복잡하게 하는 추가 시작값을 필요로 한다.)
모든 윗화살표 연산(평범한 거듭제곱 를 포함해서)은 right associative이다. 즉, 수식의 오른쪽에서 왼쪽으로 계산한다.
 —— not .
 is  —— not 
right-associativity 때문에 일 때 다음과 같다
각 는 화살표 연산의 왼쪽 항으로 나타나고 (화살표 연산은 가환이 아니기 때문에 이 점은 중요하다), 는 함수 를 ''b''번 합성한 것으로 썼다. 이기 때문에, 원래 정의를 인 모든 정수 에 대해 다음과 같이 간결하게 쓸 수 있다:
:===2↑''m'' ''n'' 계산===
을 계산하는 것은 무한한 표에서 재기술 할 수 있다. 을 가장 윗 행에 채우고, 왼쪽 열에 2로 채운다. 표의 값을 결정하기 위해서는 바로 왼쪽의 값을 얻어서 이전 행의 그 값의 위치에 있는 값을 얻는다.
+  = hyper(2, ''m'' + 2, ''n'') = 2 → n → m의 값
 ''m''\''n''
 1
 2
 3
 4
 5
 6
 공식
 1
 2 
 4 
 8 
 16 
 32 
 64 
 
 2
 2 
 4 
 16 
 65536 
  
  
 
 3
 2 
 4 
 65536 
  
  
  
 
 4
 2 
 4 
  
   
   
  
 
이 표는 과 이 약간 밀린 것과 모든 값에 3이 더해진 것을 제외하고는 아커만 함수의 표와 같다.
===3↑''m'' ''n'' 계산===
을 가장 윗 행에 채우고, 왼쪽 열에 3으로 채운다. 표의 값을 결정하기 위해서는 바로 왼쪽의 값을 얻어서 이전 행의 그 값의 위치에 있는 값을 얻는다.
+  = hyper(3, ''m'' + 2, ''n'') = 3 → n → m의 값
 ''m''\''n''
 1
 2
 3
 4
 5
 공식
 1
 3 
 9 
 27 
 81 
 243 
 
 2
 3 
 27 
 7,625,597,484,987  
   
   
 
 3
 3 
 7,625,597,484,987 
  
   
   
 
 4
 3 
  
   
   
  
 
===4↑''m'' ''n''의 계산===
을 가장 윗 행에 채우고, 왼쪽 열에 4로 채운다. 표의 값을 결정하기 위해서는 바로 왼쪽의 값을 얻어서 이전 행의 그 값의 위치에 있는 값을 얻는다.
+  = hyper(4, ''m'' + 2, ''n'') = 4 → n → m의 값
 ''m''\''n''
 1
 2
 3
 4
 5
 공식
 1
 4 
 16 
 64 
 256 
 1024 
 
 2
 4 
 256 
    
   
   
 
 3
 4 
  
  
   
   
 
 4
 4 
  
   
   
  
 
===10↑''m'' ''n''의 계산===
을 가장 윗 행에 채우고, 왼쪽 열에 10으로 채운다. 표의 값을 결정하기 위해서는 바로 왼쪽의 값을 얻어서 이전 행의 그 값의 위치에 있는 값을 얻는다.
+  = hyper(10, ''m'' + 2, ''n'') = 10 → n → m의 값
 ''m''\''n''
 1
 2
 3
 4
 5
 공식
 1
 10 
 100 
 1,000 
 10,000 
 100,000 
 
 2
 10 
 10,000,000,000 
   
   
  
 
 3
 10 
  
  
  
   
 
 4
 10 
  
  
   
  
 
2 ≤ ''n'' ≤ 9일 때 의 수치적인 순서는 ''m''이 가장 우선적인 사전식 순서여서 이 8열에서 수치적인 순서는 단순히 행의 순서대로인 것을 보라. 3 ≤ ''n'' ≤ 99인 97열에도 마찬가지로 적용이 되고, ''m'' = 1에서 시작하면 3 ≤ ''n'' ≤ 9,999,999,999까지 가능하다.
루벤 루이스 굿스타인은 커누스 화살표와 다른 표기법 시스템을 가지고 으로 표기한 하이퍼 연산 수열을 이용해서 음이 아닌 정수에 대한 기수법을 만들었다. 대괄호 (1, 2, 3, 4, ... )를 각각의 하이퍼 연산을 나타낸다고 하면 소위 ''b''를 밑으로 하는 정수 ''n''의 ''k''단계 ''완전 hereditary 표현''은 처음 ''k'' 하이퍼 연산과 0, 1, ..., ''b'' − 1의 자릿수와 밑인 ''b'' 자신을 포함하는 숫자들만을 이용해서 다음과 같이 나타낼 수 있다:
* 0 ≤ ''n'' ≤ ''b''-1일 때는, ''n''은 단순히 대응하는 숫자로 표현한다.
* ''n'' > ''b''-1일 때는, ''n''의 표현은 재귀적으로 찾는다. 먼저 ''n''은 다음의 형태로 나타난다:
:''b'' ''k'' ''x''''k'' ''k'' - 1 ''x''''k''-1 ''k'' - 2 ... 2 ''x''2 1 ''x''1
:이 때 ''x''''k'', ..., ''x''1는 다음을 (차례로)만족하는 가장 큰 정수이다.
:''b'' ''k'' ''x''''k'' ≤ ''n''
:''b'' ''k'' ''x''''k'' ''k'' - 1 ''x''''k'' - 1 ≤ ''n''
:...
:''b'' ''k'' ''x''''k'' ''k'' - 1 ''x''''k'' - 1 ''k'' - 2 ... 2 ''x''2 1 ''x''1 ≤ ''n''
:''b''-1을 넘는 ''x''''i''는 같은 방법으로 다시 표현하고 0, 1, ..., ''b''-1과 밑인 ''b''만 남을 때까지 계속한다.
이 부분의 나머지는 하이퍼 연산을 표현하기 위해 윗첨자로 사용한다.
계산할 때 고차 연산에 높은 우선도를 부여해서 불필요한 괄호를 피할 수 있다; 따라서,
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''도 이 형태이다.
그리고 계속된다.
밑이 ''b''인 ''hereditary'' 표현의 종류에서, 밑 자신이 {0, 1, ..., ''b''-1}의  "자릿수"처럼 표현에서 나타난다는 점을 주목하라. 이 표현은 문자가 밑을 ''b''로 표시했을  때 ''일반적인'' 이진법과 비교된다. 예를 들어, 일반적인 이진법에서는 6 = (110)2 = 2 3 2 2 1 1 2 3 1 2 1 1 2 3 0 2 0이고 밑이 2인 3단계 hereditary 표현은 6 = 2 3 (2 3 1 2 1 1 0) 2 1 1 (2 3 1 2 1 1 0)이다. hereditary 표현은 1 0, 2 1, 3 1, 4 1, 등등의 요소를 제거해서 간략하게 만들 수 있다. 예를 들어, 위의 밑이 2인 6의 3단계 표현은 2 3 2 1 2로 간단히 할 수 있다.
예:
266의 밑이 2인 유일한 1, 2, 3, 4, 그리고 5단계 표현은 다음과 같다:
:1단계: 266 = 2 1 2 1 2 1 ... 1 2 (2가 133개)
: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
커누스 윗화살표는 그레이엄 수 G64(4)를 표기할 때 사용되고 있다. 그레이엄 수는 이름이 붙은 자연수 중에서 수학적 의미를 갖고 있는 가장 큰 수이다.
 (여기서 윗화살표의 개수는 G63(4)개이다.)
* 원시 재귀 함수
* 하이퍼 연산
* 커틀러 묶음부호 표기법
* 테트레이션
* 펜테이션
* 콘웨이 화살표 사슬 표기법
* 아커만 함수
* 그레이엄 수
* 스테인하우스-모서 표기법
* 
* Robert Munafo, '' Large Numbers''
분류:큰 수
분류:수학 표기법
분류:도널드 커누스