Ký hiệu mũi tên lên Knuth

Trong toán học, ký hiệu mũi tên lên Knuth (tiếng Anh: Knuth's up-arrow notation) là một phương pháp ký hiệu cho các số nguyên rất lớn, được giới thiệu bởi Donald Knuth vào năm 1976.

Nó liên quan chặt chẽ đến hàm Ackermann và đặc biệt là dãy hyperoperation. Ý tưởng này dựa trên thực tế là phép nhân có thể được xem như là phép lặp của phép cộng và lũy thừa như là phép lặp của phép nhân. Tiếp tục theo cách này dẫn đến tetration (phép lặp của luỹ thừa) và phần còn lại của dãy hyperoperation, thường được ký hiệu bằng cách sử dụng ký hiệu mũi tên lên Knuth. Ký hiệu này cho phép mô tả đơn giản các số lớn hơn nhiều so với có thể được viết rõ ràng.

Mũi tên lên đơn có nghĩa là lũy thừa (phép nhân lặp), nhiều hơn một mũi tên lên có nghĩa là lặp lại phép toán được liên kết với một mũi tên lên ít hơn.

Ví dụ:
Mũi tên lên đơn là phép nhân lặp (luỹ thừa)
::2 \uparrow 4 = 2\times(2\times(2\times 2)) = 2^4 = 16
Mũi tên lên đôi là luỹ thừa lặp (tetration)
::2 \uparrow\uparrow 4 = 2 \uparrow (2 \uparrow (2 \uparrow 2)) = 2^{2^{2^{2}}} = 65536
Mũi tên lên ba là tetration lặp (pentation)

::\begin{align}
2 \uparrow\uparrow\uparrow 4
&= 2 \uparrow\uparrow (2 \uparrow\uparrow (2 \uparrow\uparrow 2))\\
&= 2 \uparrow\uparrow (2 \uparrow\uparrow (2 \uparrow 2))\\
&= 2 \uparrow\uparrow (2 \uparrow\uparrow 4)\\
&= \underbrace{2 \uparrow (2 \uparrow (2 \uparrow\dots))}\\
& 2 \uparrow\uparrow 4\mbox{ là số lần của }2\\
\end{align}

Định nghĩa chung của ký hiệu (theo đệ quy) như sau (đối với số nguyên a và số nguyên không âm b và n):
:
a\uparrow^n b=
\begin{cases}
a^b, & \text{nếu }n=1; \\
1, & \text{nếu }n\ge 1\text{ và }b=0; \\
a\uparrow^{n-1}(a\uparrow^{n}(b-1)), & \text{cách khác }
\end{cases}


Ở đây,
\uparrow^{n}
là viết tắt của mũi tên lên
n
, ví dụ:
:2 \uparrow\uparrow\uparrow\uparrow 3 = 2\uparrow^4 3.

Giới thiệu

Các phép toán số học thông thường của phép cộng, phép nhân và lũy thừa được mở rộng một cách tự nhiên thành một dãy các phép toán như sau.

Phép cộng với số tự nhiên được định nghĩa là đếm lặp:

:
\begin{matrix}
a+b & = & a+\underbrace{1+1+\dots+1} \\
& & b\mbox{ là số lần lặp của }1
\end{matrix}


Phép nhân với số tự nhiên được định nghĩa là phép cộng lặp:

:
\begin{matrix}
a\times b & = & \underbrace{a+a+\dots+a} \\
& & b\mbox{ là số lần lặp của }a
\end{matrix}


Ví dụ,

:
\begin{matrix} 3\times 4 & = & \underbrace{3+3+3+3} & = & 12\\
& & 4\mbox{ là số lần lặp của }3
\end{matrix}


Luỹ thừa với mũ tự nhiên b được định nghĩa là phép nhân lặp, mà Knuth biểu thị bằng ký hiệu mũi tên lên đơn:

:
\begin{matrix}
a\uparrow b= a^b = & \underbrace{a\times a\times\dots\times a}\\
& b\mbox{ là số lần lặp của }a
\end{matrix}


Ví dụ,

:
\begin{matrix}
4\uparrow 3= 4^3 = & \underbrace{4\times 4\times 4} & = & 64\\
& 3\mbox{ là số lần lặp của }4
\end{matrix}


Để mở rộng dãy các phép toán vượt quá lũy thừa, Knuth đã định nghĩa ký hiệu "mũi tên lên đôi" để biểu thị lũy thừa lặp (tetration):

:
\begin{matrix}
a\uparrow\uparrow b =& \underbrace{a^{a^{{}^{.\,^{.\,^{.\,^a}}}}}} &
= & \underbrace{a\uparrow (a\uparrow(\dots\uparrow a))}
\\
& b\mbox{ là số lần lặp của }a
& & b\mbox{ là số lần lặp của }a
\end{matrix}


Ví dụ,

:
\begin{matrix}
4\uparrow\uparrow 3 = & \underbrace{4^{4^4}} &
= & \underbrace{4\uparrow (4\uparrow 4)} & = & 4^{256} & \approx & 1.34078079\times 10^{154}&
\\
& 3\mbox{ là số lần lặp của }4
& &3\mbox{ là số lần lặp của }4
\end{matrix}


Việc đánh giá ở đây và bên dưới là diễn ra từ phải sang trái, vì các ký hiệu mũi tên lên đơn của Knuth (giống như lũy thừa) được định nghĩa là kết hợp phải.

Theo định nghĩa này,
:3\uparrow\uparrow 2=3^3=27
:3\uparrow\uparrow 3=3^{3^3}=3^{27}=7,625,597,484,987
:3\uparrow\uparrow 4=3^{3^{3^3}}=3^{3^{27}}=3^{7625597484987}\approx 1.2580143\times 10^{3638334640024}

:3\uparrow\uparrow 5=3^{3^{3^{3^3}}}=3^{3^{3^{27}}}=3^{3^{7625597484987}}\approx 3^{1.2580143\times 10^{3638334640024}}
:v.v.

Điều này đã dẫn đến một số con số khá lớn, nhưng Knuth đã mở rộng ký hiệu. Ông ấy tiếp tục định nghĩa ký hiệu "mũi tên lên ba" cho tetration lặp (pentation):

:
\begin{matrix}
a\uparrow\uparrow\uparrow b= &
\underbrace{a_{}\uparrow\uparrow (a\uparrow\uparrow(\dots\uparrow\uparrow a))}\\
& b\mbox{ là số lần lặp của }a
\end{matrix}


theo sau là một ký hiệu "mũi tên lên bốn" cho pentation lặp (hexation):

:
\begin{matrix}
a\uparrow\uparrow\uparrow\uparrow b= &
\underbrace{a_{}\uparrow\uparrow\uparrow (a\uparrow\uparrow\uparrow(\dots\uparrow\uparrow\uparrow a))}\\
& b\mbox{ là số lần lặp của }a
\end{matrix}


vân vân. Nguyên tắc chung là ký hiệu "n-mũi tên lên" mở rộng thành một loạt liên kết phải của ký hiệu "(n - 1)-mũi tên lên". Tượng trưng,

:
\begin{matrix}
a\ \underbrace{\uparrow_{}\uparrow\!\!\dots\!\!\uparrow}_{n}\ b=
\underbrace{a\ \underbrace{\uparrow\!\!\dots\!\!\uparrow}_{n-1}
\ (a\ \underbrace{\uparrow_{}\!\!\dots\!\!\uparrow}_{n-1}
\ (\dots
\ \underbrace{\uparrow_{}\!\!\dots\!\!\uparrow}_{n-1}
\ a))}_{b\text{ là số lần lặp của }a}
\end{matrix}


Ví dụ:

:
\begin{matrix}
3\uparrow\uparrow\uparrow3 = 3\uparrow\uparrow(3\uparrow\uparrow3) = 3\uparrow\uparrow(3\uparrow3\uparrow3) = &
\underbrace{3_{}\uparrow 3\uparrow\dots\uparrow 3} \\
& 3\uparrow3\uparrow3\mbox{ là số lần lặp của }3
\end{matrix}
\begin{matrix}
= & \underbrace{3_{}\uparrow 3\uparrow\dots\uparrow 3} \\
& \mbox{7,625,597,484,987 là số lần lặp của 3}
\end{matrix}
\begin{matrix}
= & \underbrace{3^{3^{3^{3^{\cdot^{\cdot^{\cdot^{\cdot^{3}}}}}}}}} \\
& \mbox{7,625,597,484,987 là số lần lặp của 3}
\end{matrix}


Ký hiệu a \uparrow^n b thường được sử dụng để biểu thị a \uparrow\uparrow \dots \uparrow b với
n
-mũi tên lên. Trong thực tế, a \uparrow^n b là
a[n+2]b
với hyperoperation. Ví dụ, 39\uparrow\uparrow14 cũng có thể được viết là
39[4]14
9 ("[4]" có nghĩa là tetration), nhưng nó không bằng
39[2]14=39\times {14}=546
. Tương tự, 77 \uparrow^{77} 77 bằng
77[79]77
, thay vì
77[77]77
.

Ký hiệu
Trong các biểu thức như a^b, ký hiệu cho luỹ thừa thường là viết số mũ b dưới dạng chỉ số trên cho số cơ số a. Nhưng nhiều môi trường &mdash; chẳng hạn như ngôn ngữ lập trình và e-mail văn bản thuần tuý &mdash; không hỗ trợ sắp chữ chỉ số trên. Mọi người đã áp dụng ký hiệu tuyến tính a \uparrow b cho các môi trường như vậy, mũi tên lên gợi ý 'nâng cao sức mạnh của'. Nếu bộ ký tự không chứa mũi tên lên, dấu mũ (^) được sử dụng thay thế.

Ký hiệu chỉ số trên a^b không thêm vào chính nó để khái quát hóa, điều này giải thích tại sao Knuth chọn hoạt động từ ký hiệu nội tuyến a \uparrow b thay thế.

a \uparrow^n b là một ký hiệu thay thế ngắn hơn cho n mũi tên lên. Như vậy a \uparrow^4 b = a \uparrow \uparrow \uparrow \uparrow b.

Viết ra ký hiệu mũi tên lên về luỹ thừa
Cố gắng viết a \uparrow \uparrow b sử dụng ký hiệu chỉ số trên quen thuộc sẽ tạo ra một tháp mũ.

:Ví dụ: a \uparrow \uparrow 4 = a \uparrow (a \uparrow (a \uparrow a)) = a^{a^{a^a}}

Nếu b là một biến số (hoặc quá lớn), tháp mũ có thể được viết bằng các dấu chấm và một ghi chú cho biết chiều cao của tháp.

:a \uparrow \uparrow b = \underbrace{a^{a^{.^{.^{.{a}}}}}}_{b}

Tiếp tục với ký hiệu này, a \uparrow \uparrow \uparrow b có thể được viết bằng một chồng các tháp mũ như vậy, mỗi tháp mô tả kích thước của tháp bên trên nó.

:a \uparrow \uparrow \uparrow 4 = a \uparrow \uparrow (a \uparrow \uparrow (a \uparrow \uparrow a)) =
\underbrace{a^{a^{.^{.^{.{a}}}}}}_{ \underbrace{a^{a^{.^{.^{.{a}}}}}}_{ \underbrace{a^{a^{.^{.^{.{a}}}}}}_{a} }}

Một lần nữa, nếu b là một biến hoặc quá lớn, ngăn xếp có thể được viết bằng các dấu chấm và một ghi chú chỉ ra chiều cao của nó.

:a \uparrow \uparrow \uparrow b =
\left. \underbrace{a^{a^{.^{.^{.{a}}}}}}_{ \underbrace{a^{a^{.^{.^{.{a}}}}}}_{ \underbrace{\vdots}_{a} }} \right\} b

Hơn nữa, a \uparrow \uparrow \uparrow \uparrow b có thể được viết bằng cách sử dụng một số cột của các tháp mũ như vậy, mỗi cột mô tả số lượng mũ trong ngăn xếp bên trái:

:a \uparrow \uparrow \uparrow \uparrow 4 = a \uparrow \uparrow \uparrow (a \uparrow \uparrow \uparrow (a \uparrow \uparrow \uparrow a)) =
\left.\left.\left. \underbrace{a^{a^{.^{.^{.{a}}}}}}_{ \underbrace{a^{a^{.^{.^{.{a}}}}}}_{ \underbrace{\vdots}_{a} }} \right\}
\underbrace{a^{a^{.^{.^{.{a}}}}}}_{ \underbrace{a^{a^{.^{.^{.{a}}}}}}_{ \underbrace{\vdots}_{a} }} \right\}
\underbrace{a^{a^{.^{.^{.{a}}}}}}_{ \underbrace{a^{a^{.^{.^{.{a}}}}}}_{ \underbrace{\vdots}_{a} }} \right\}
a

Và nói chung hơn:

:a \uparrow \uparrow \uparrow \uparrow b =
\underbrace{
\left.\left.\left. \underbrace{a^{a^{.^{.^{.{a}}}}}}_{ \underbrace{a^{a^{.^{.^{.{a}}}}}}_{ \underbrace{\vdots}_{a} }} \right\}
\underbrace{a^{a^{.^{.^{.{a}}}}}}_{ \underbrace{a^{a^{.^{.^{.{a}}}}}}_{ \underbrace{\vdots}_{a} }} \right\}
\cdots \right\}
a
}_{b}

Điều này có thể được thực hiện vô thời hạn để đại diện cho a \uparrow^n b như lũy thừa lặp của lũy thừa lặp cho bất kỳ a, n và b (mặc dù rõ ràng nó trở nên khá cồng kềnh).

Sử dụng ký hiệu tetration

Ký hiệu Rudy Rucker ^{b}a cho phép chúng ta làm cho các sơ đồ này đơn giản hơn một chút trong khi vẫn sử dụng một biểu diễn hình học (chúng ta có thể gọi đây là những tháp tetration).

: a \uparrow \uparrow b = { }^{b}a

: a \uparrow \uparrow \uparrow b = \underbrace{^{^{^{^{^{a}.}.}.}a}a}_{b}

: a \uparrow \uparrow \uparrow \uparrow b =
\left. \underbrace{^{^{^{^{^{a}.}.}.}a}a}_{ \underbrace{^{^{^{^{^{a}.}.}.}a}a}_{ \underbrace{\vdots}_{a} }} \right\} b

Ví dụ, số Ackermann thứ tư 4 \uparrow^4 4 có thể được trình bày như:
: \underbrace{^{^{^{^{^{4}.}.}.}4}4}_{ \underbrace{^{^{^{^{^{4}.}.}.}4}4}_{ \underbrace{^{^{^{^{^{4}.}.}.}4}4}_{4} }} =
\underbrace{^{^{^{^{^{4}.}.}.}4}4}_{ \underbrace{^{^{^{^{^{4}.}.}.}4}4}_{ ^{^{^{4}4}4}4 }}
:

Khái quát
Một số con số quá lớn đến nỗi nhiều mũi tên lên của ký hiệu mũi tên lên Knuth trở nên quá cồng kềnh, thì ký hiệu n-mũi tên lên \uparrow^n là hữu ích (và cũng cho các mô tả với một số mũi tên khác nhau), hoặc tương đương, ký hiệu hyperoperation.

Một số con số quá lớn đến nỗi ngay cả ký hiệu đó cũng không đủ. Ký hiệu mũi tên xích Conway sau đó có thể được sử dụng: một chuỗi gồm ba yếu tố tương đương với các ký hiệu khác, nhưng một chuỗi bốn hoặc nhiều hơn thậm chí còn mạnh hơn.

:
\begin{matrix}
a\uparrow^{n} b & = & a [n+2] b & = & a\to b\to n \\
\mbox{(Knuth)} & & \mbox{(ký hiệu hyperoperation)} & & \mbox{(Conway)}
\end{matrix}


Người ta thường gợi ý rằng mũi tên lên của Knuth nên được sử dụng cho các số độ lớn nhỏ hơn, và mũi tên xích hoặc hyperoperation cho những cái lớn hơn.

Định nghĩa

Ký hiệu mũi tên lên được định nghĩa chính thức bởi

:
a\uparrow^n b=
\begin{cases}
a^b, & \text{nếu }n=1; \\
1, & \text{nếu }n\ge 1\text{ và }b=0; \\
a\uparrow^{n-1}(a\uparrow^{n}(b-1)), & \text{cách khác }
\end{cases}


cho tất cả các số nguyên a, b, n với b \ge 0, n \ge 1.

Định nghĩa này sử dụng lũy thừa (a\uparrow^1 b = a\uparrow b = a^b) như nhân lặp lại cho trường hợp cơ số, và tetration (a\uparrow^2 b = a\uparrow\uparrow b) như lũy thừa lặp lại. Điều này tương đương với dãy hyperoperation ngoại trừ nó bỏ qua ba thao tác cơ bản hơn của successor, phép cộng và phép nhân. Bao gồm ba điều này đòi hỏi các giá trị bắt đầu bổ sung phần nào làm phức tạp định nghĩa.

Các ký hiệu mũi tên lên (bao gồm lũy thừa bình thường, a \uparrow b) đôi khi được sử dụng kết hợp phải, tức là được đánh giá từ phải sang trái trong một biểu thức, nghĩa là a \uparrow b \uparrow c = a \uparrow (b \uparrow c) thay vì (a \uparrow b) \uparrow c, nhưng không có quy ước chung, vì vậy việc sử dụng dấu ngoặc đơn là phổ biến để ngăn ngừa sự mơ hồ.

Bảng giá trị

Tính toán 2↑n&nbsp;b
Tính toán 2\uparrow^n b có thể được trình bày lại dưới dạng bảng vô hạn. Chúng ta đặt các số 2^b ở hàng trên cùng, và điền vào cột bên trái với các giá trị 2. Để xác định một số trong bảng, hãy lấy số ngay bên trái, sau đó tra cứu số được yêu cầu ở hàng trước, tại vị trí được cung cấp bởi số vừa lấy.

Bảng này giống như của hàm Ackermann, ngoại trừ sự thay đổi trong n và b, và thêm 3 vào tất cả các giá trị.

Tính toán 3↑n&nbsp;b
Chúng ta đặt các số 3^b ở hàng trên cùng, và điền vào cột bên trái với các giá trị 3. Để xác định một số trong bảng, hãy lấy số ngay bên trái, sau đó tra cứu số được yêu cầu ở hàng trước, tại vị trí được cung cấp bởi số vừa lấy.

Tính toán 4↑n&nbsp;b
Chúng ta đặt các số 4^b ở hàng trên cùng, và điền vào cột bên trái với các giá trị 4. Để xác định một số trong bảng, hãy lấy số ngay bên trái, sau đó tra cứu số được yêu cầu ở hàng trước, tại vị trí được cung cấp bởi số vừa lấy.

Tính toán 10↑n&nbsp;b
Chúng ta đặt các số 10^b ở hàng trên cùng, và điền vào cột bên trái với các giá trị 10. Để xác định một số trong bảng, hãy lấy số ngay bên trái, sau đó tra cứu số được yêu cầu ở hàng trước, tại vị trí được cung cấp bởi số vừa lấy.

Hệ thống số dựa trên dãy hyperoperation
R. L. Goodstein, với một hệ thống ký hiệu khác với mũi tên lên Knuth, được sử dụng dãy các phép toán ở đây được ký hiệu là ( +, \ \times, \ \uparrow, \ \uparrow\uparrow, \ \dots) để tạo các hệ số cho các số nguyên không âm. Để dấu ngoặc vuông ([1], [2], [3], [4],...) biểu thị các phép toán tương ứng ( +, \ \times, \ \uparrow, \ \uparrow\uparrow, \ \dots), cái gọi là đầy đủ biểu diễn di truyền của số nguyên n, tại cấp k và cơ số b, có thể được biểu thị như sau chỉ sử dụng các phép toán k đầu tiên và chỉ sử dụng dưới dạng các chữ số 0, 1,..., b - 1, cùng với chính cơ số b:

Với 0 ≤ n ≤ b-1, n được biểu diễn đơn giản bằng chữ số tương ứng.
Với n > b-1, đại diện của n được tìm thấy đệ quy, đầu tiên đại diện cho n ở dạng
:b [k] x'k [k - 1] x'k-1 [k - 2]... [2] x2 [1] x1
:trong đó x'k,..., x1 là các số nguyên lớn nhất thỏa mãn (lần lượt)

: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] x2 [1] x1 ≤ n

:Bất kỳ x'i vượt quá b-1 sau đó được thể hiện lại theo cách tương tự, v.v., lặp lại quy trình này cho đến khi biểu mẫu kết quả chỉ chứa các chữ số 0, 1,..., b-1, cùng với cơ số b.

Phần còn lại của phần này sẽ sử dụng các chỉ số trên để biểu thị các phép toán.

Có thể tránh các dấu ngoặc đơn không cần thiết bằng cách ưu tiên các toán tử cấp cao hơn theo thứ tự đánh giá, do đó,

Các biểu diễn cấp 1 có dạng b [1] X, với X cũng thuộc dạng này,

Các biểu diễn cấp 2 có dạng b [2] X [1] Y, với X, Y cũng thuộc dạng này,

Các biểu diễn cấp 3 có dạng b [3] X [2] Y [1] Z, với X, Y, Z cũng thuộc dạng này,

Các biểu diễn cấp 4 có dạng b [4] X [3] Y [2] Z [1] W, với X,Y,Z,W cũng thuộc dạng này,

vân vân.

Trong loại biểu diễn di truyền cơ số b này, cơ số chính nó xuất hiện trong các biểu thức, cũng như "chữ số" từ tập hợp {0, 1,..., b-1}. Điều này so sánh với biểu diễn cơ số 2 thông thường khi phần sau được viết ra dưới dạng cơ số b. Ví dụ trong ký hiệu cơ số 2 thông thường, 6 = (110)2 = 2 [3] 2 [2] 1 [1] 2 [3] 1 [2] 1 [1] 2 [3] 0 [2] 0,
trong khi biểu diễn di truyền cấp 3 cơ số 2 là 6 = 2 [3] (2 [3] 1 [2] 1 [1] 0) [2] 1 [1] (2 [3] 1 [2] 1 [1] 0). Các biểu diễn di truyền có thể được viết tắt bằng cách bỏ qua bất kỳ trường hợp nào của [1] 0, [2] 1, [3] 1, [4] 1, v.v.. Ví dụ, biểu diễn cấp 3 cơ số 2 ở trên gồm 6 chữ viết tắt thành 2 [3] 2 [1] 2.

Ví dụ:
Các biểu diễn cơ số 2 duy nhất của số 266, ở các cấp 1, 2, 3, 4 và 5 như sau:

:Cấp 1: 266 = 2 [1] 2 [1] 2 [1]... [1] 2 (với 133 lần 2)
:Cấp 2: 266 = 2 [2] (2 [2] (2 [2] (2 [2] 2 [2] 2 [2] 2 [2] 2 [1] 1)) [1] 1)
:Cấp 3: 266 = 2 [3] 2 [3] (2 [1] 1) [1] 2 [3] (2 [1] 1) [1] 2
:Cấp 4: 266 = 2 [4] (2 [1] 1) [3] 2 [1] 2 [4] 2 [2] 2 [1] 2
:Cấp 5: 266 = 2 [5] 2 [4] 2 [1] 2 [5] 2 [2] 2 [1] 2

Xem thêm
Đệ quy cơ bản
Hyperoperation
Ký hiệu thanh Cutler
Tetration
Pentation
Hàm Ackermann
Số Graham
Ký hiệu Steinhaus–Moser

Tham khảo

Liên kết ngoài

Robert Munafo, Large Numbers