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ụ:
Định nghĩa chung của ký hiệu (theo đệ quy) như sau (đối với số nguyên formula_4 và số nguyên không âm formula_5 và formula_6):
Ở đây, formula_8 là viết tắt của mũi tên lên formula_9, ví dụ:
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:
Phép nhân với số tự nhiên được định nghĩa là phép cộng lặp:
Ví dụ,
Luỹ thừa với mũ tự nhiên formula_5 đượ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:
Ví dụ,
Để 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):
Ví dụ,
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,
Đ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):
theo sau là một ký hiệu "mũi tên lên bốn" cho pentation lặp (hexation):
vân vân. Nguyên tắc chung là ký hiệu "formula_6-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 "(formula_26)-mũi tên lên". Tượng trưng,
Ví dụ:
Ký hiệu formula_29 thường được sử dụng để biểu thị formula_30 với formula_9-mũi tên lên. Trong thực tế, formula_29 là formula_33 với hyperoperation. Ví dụ, formula_34 cũng có thể được viết là formula_359 ("[4]" có nghĩa là tetration), nhưng nó không bằng formula_36. Tương tự, formula_37 bằng formula_38, thay vì formula_39.
Ký hiệu.
Trong các biểu thức như formula_40, ký hiệu cho luỹ thừa thường là viết số mũ formula_5 dưới dạng chỉ số trên cho số cơ số formula_4. Nhưng nhiều môi trường — chẳng hạn như ngôn ngữ lập trình và e-mail văn bản thuần tuý — 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 formula_43 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 formula_40 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 formula_43 thay thế.
formula_29 là một ký hiệu thay thế ngắn hơn cho n mũi tên lên. Như vậy formula_47.
Viết ra ký hiệu mũi tên lên về luỹ thừa.
Cố gắng viết formula_48 sử dụng ký hiệu chỉ số trên quen thuộc sẽ tạo ra một tháp mũ.
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.
Tiếp tục với ký hiệu này, formula_51 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ó.
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ó.
Hơn nữa, formula_54 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:
Và nói chung hơn:
Điều này có thể được thực hiện vô thời hạn để đại diện cho formula_29 như lũy thừa lặp của lũy thừa lặp cho bất kỳ formula_4, formula_6 và formula_5 (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 formula_61 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").
Ví dụ, số Ackermann thứ tư formula_65 có thể được trình bày như:
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 formula_6-mũi tên lên formula_68 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.
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
cho tất cả các số nguyên formula_71 với formula_72.
Định nghĩa này sử dụng lũy ​​thừa formula_73 như nhân lặp lại cho trường hợp cơ số, và tetration formula_74 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, formula_43) đô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à formula_76 thay vì formula_77, 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" "b".
Tính toán formula_78 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ố formula_79 ở 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 formula_6 và formula_5, và thêm 3 vào tất cả các giá trị.
Tính toán 3↑"n" "b".
Chúng ta đặt các số formula_82 ở 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" "b".
Chúng ta đặt các số formula_83 ở 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" "b".
Chúng ta đặt các số formula_84 ở 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à formula_85 để 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 formula_85, 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":
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: