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

Bách khoa toàn thư mở Wikipedia
Bước tới điều hướng Bước tới tìm kiếm

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.[1] Nó liên quan chặt chẽ đến hàm Ackermann và đặc biệt là dãy hyper. Ý 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à phép 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 phép tetration (phép lặp của luỹ thừa) và phần còn lại của dãy hyper, thường được ký hiệu bằng cách sử dụng ký hiệu mũi tê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 đơ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 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 ít hơn.

Ví dụ:

  • Mũi tên đôi là luỹ thừa lặp (tetration)

Đị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 bn):

Ở đây, ↑n là viết tắt của mũi tên n, ví dụ:

.

Giới thiệu[sửa | sửa mã nguồn]

Các phép toán số học thông thường của phép cộng, phép nhânlũ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 (hyper) 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 được định nghĩa là phép nhân lặp, mà Knuth biểu thị bằng 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 một toán tử "mũi tên đôi" để biểu thị phép 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 toán tử mũi tê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,

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 toán tử "mũi tên ba" cho tetration lặp (pentation):

theo sau là một toán tử "mũi tên bốn" cho pentation lặp (hexation):

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

Ví dụ:

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

Ký hiệu[sửa | sửa mã nguồn]

Trong các biểu thức như , ký hiệu cho luỹ thừa thường là viết số mũ dưới dạng bệ số trên cho số cơ số . Nhưng nhiều môi trường — chẳng hạn như ngôn ngữ lập trìnhe-mail văn bản thuần tuý — không hỗ trợ sắp chữ bệ trên. Mọi người đã áp dụng ký hiệu tuyến tính 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 bệ số trên 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 thay thế.

là một ký hiệu thay thế ngắn hơn cho n uparrows. Như vậy .

Viết ra ký hiệu mũi tên lên về mặt mũ[sửa | sửa mã nguồn]

Cố gắng viết sử dụng ký hiệu bệ trên quen thuộc sẽ tạo ra một tháp mũ.

Ví dụ:

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, 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, 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 như lũy thừa lặp của lũy thừa lặp cho bất kỳ a, nb (mặc dù rõ ràng nó trở nên khá cồng kềnh).

Sử dụng tetration[sửa | sửa mã nguồn]

Ký hiệu tetration 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 biểu diễn hình học (chúng ta có thể gọi những tháp tetration này)

Cuối cùng, như một ví dụ, số Ackermann thứ tư có thể được trình bày như:

Khái quát[sửa | sửa mã nguồn]

Một số con số quá lớn đến nỗi nhiều mũi tên của ký hiệu mũi tên lên Knuth trở nên quá cồng kềnh, thì toán tử n-mũi tê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, siêu toán tử.

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 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 siêu toán tử cho những cái lớn hơn.

Định nghĩa[sửa | sửa mã nguồn]

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 với .

Định nghĩa này sử dụng lũy ​​thừa như nhân lặp lại cho trường hợp cơ số, và tetration như lũy thừa lặp lại. Điều này tương đương với dãy hyper ngoại trừ nó bỏ qua ba thao tác cơ bản hơn của phép successor, phép cộngphé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 toán tử mũi tên lên (bao gồm lũy thừa bình thường, ) đô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à thay vì , 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ị[sửa | sửa mã nguồn]

Tính toán 2↑n b[sửa | sửa mã nguồn]

Tính toán 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ố ở 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.

Giá trị của = hyper(2, n + 2, b) = 2 → b → n
b
1 2 3 4 5 6 công thức
1 2 4 8 16 32 64
2 2 4 16 65536
3 2 4 65536
4 2 4      

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

Tính toán 3↑n b[sửa | sửa mã nguồn]

Chúng ta đặt các số ở 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.

Giá trị của = hyper(3, n + 2, b) = 3 → b → n
b
1 2 3 4 5 công thức
1 3 9 27 81 243
2 3 27 7,625,597,484,987
3 3 7,625,597,484,987    
4 3      

Tính toán 4↑n b[sửa | sửa mã nguồn]

Chúng ta đặt các số ở 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.

Giá trị của = hyper(4, n + 2, b) = 4 → b → n
b
1 2 3 4 5 công thức
1 4 16 64 256 1024
2 4 256
3 4    
4 4      

Tính toán 10↑n b[sửa | sửa mã nguồn]

Chúng ta đặt các số ở 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.

Giá trị của = hyper(10, n + 2, b) = 10 → b → n
b
1 2 3 4 5 công thức
1 10 100 1,000 10,000 100,000
2 10 10,000,000,000
3 10  
4 10    

Hệ thống số dựa trên dãy hyper[sửa | sửa mã nguồn]

R. L. Goodstein,[2] với một hệ thống ký hiệu khác với mũi tên Knuth, được sử dụng dãy các hyper ở đây được ký hiệu là để 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 hyper tương ứng , 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 hyper 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 ≤ nb-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] xk [k - 1] xk-1 [k - 2]... [2] x2 [1] x1
trong đó xk,..., x1 là các số nguyên lớn nhất thỏa mãn (lần lượt)
b [k] xkn
b [k] xk [k - 1] xk - 1n
...
b [k] xk [k - 1] xk - 1 [k - 2]... [2] x2 [1] x1n
Bất kỳ xi 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 bệ số trên để biểu thị các hyper.

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[sửa | sửa mã nguồn]

Tham khảo[sửa | sửa mã nguồn]

  1. ^ Knuth, Donald E. (1976). “Mathematics and Computer Science: Coping with Finiteness”. Science. 194 (4271): 1235–1242. doi:10.1126/science.194.4271.1235. PMID 17797067.
  2. ^ Goodstein, R. L. (1947). “Transfinite ordinals in recursive number theory”. Journal of Symbolic Logic. 12 (4): 123–129. doi:10.2307/2266486. JSTOR 2266486.

Liên kết ngoài[sửa | sửa mã nguồn]