Hàm Ackermann

Bách khoa toàn thư mở Wikipedia

Trong lý thuyết tính toán, Hàm Ackermann hay hàm số Ackermann (tiếng Anh: Ackermann function), được đặt theo tên của Wihelm Ackermann, là một trong những ví dụ đơn giản nhất[1] và được phát hiện sớm nhất về một hàm tính toán tổng thể không phải là đệ quy nguyên thủy. Tất cả các hàm đệ quy nguyên thủy là tổng và có thể tính toán được, nhưng hàm Ackermann minh họa rằng không phải tất cả các hàm tính toán được đều là đệ quy nguyên thủy. Sau khi Ackermann công bố[2] hàm của mình (có ba đối số nguyên không âm), nhiều tác giả đã sửa đổi nó cho phù hợp với nhiều mục đích khác nhau, để ngày nay "hàm Ackermann" có thể tham chiếu đến bất kỳ biến thể nào của hàm ban đầu. Một phiên bản chung, hàm Ackermann-Péter hai đối số được định nghĩa như sau cho các số nguyên không âm mn:

Giá trị của nó tăng lên nhanh chóng, ngay cả đối với những đầu vào nhỏ. Ví dụ, A(4, 2) là một số nguyên gồm 19,729 chữ số thập phân[3] (tương đương với 265536−3, hoặc 22222−3).

Lịch sử[sửa | sửa mã nguồn]

Vào cuối những năm 1920, các nhà toán học Gabriel SudanWilhelm Ackermann, học trò của David Hilbert, đang nghiên cứu nền tảng của tính toán. Cả Sudan và Ackermann đều được ghi nhận[4] với việc khám phá ra các hàm tính toán tổng thể (được gọi đơn giản là "đệ quy" trong một số tài liệu tham khảo) không phải là đệ quy nguyên thủy. Sudan đã xuất bản hàm Sudan ít được biết đến hơn, sau đó không lâu và một cách độc lập, vào năm 1928, Ackermann đã xuất bản hàm của mình (chữ cái Hy Lạp phi). Hàm ba đối số Ackermann, , được định nghĩa sao cho , nó tái tạo các phép toán cơ bản của cộng, nhânlũy thừa như

và đối với p > 2, nó mở rộng các phép toán cơ bản này theo cách có thể được so sánh với các hyperoperation:

(Bên cạnh vai trò lịch sử của nó như một hàm tính-toán-tổng-thể-nhưng-không-đệ-quy-nguyên-thủy, hàm gốc của Ackermann được xem là mở rộng các phép toán số học cơ bản ngoài phép lũy thừa, mặc dù không liền mạch như các biến thể của hàm Ackermann được thiết kế đặc biệt cho mục đích đó — chẳng hạn như dãy phép toán Goodstein.)

Trong cuốn On the Infinite,[5] David Hilbert đưa ra giả thuyết rằng hàm Ackermann không phải là hàm đệ quy nguyên thủy, nhưng chính Ackermann, thư ký riêng của Hilbert và là học trò cũ của ông, người đã thực sự chứng minh giả thuyết trong bài báo On Hilbert's Construction of the Real Numbers.[2][6]

Rózsa Péter[7]Raphael Robinson[8] sau đó đã phát triển một phiên bản hai biến của hàm Ackermann được hầu hết các tác giả ưa thích.

Trình tự dãy hyperoperation tổng quát, ví dụ: , cũng là một phiên bản của hàm Ackermann.[9]

Năm 1963 R.C. Buck dựa trên một biến thể hai biến[n 1] trực quan } trên chuỗi hyperoperation:[10][11]

So với hầu hết các phiên bản khác, hàm Buck không có hiệu số không cần thiết:

Nhiều phiên bản khác của hàm Ackermann đã được nghiên cứu.[12]

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

Định nghĩa: dưới dạng hàm m-ary[sửa | sửa mã nguồn]

Hàm Ackermann ba đối số ban đầu được định nghĩa một cách đệ quy như sau cho các số nguyên không âm :

Trong số các phiên bản hai đối số khác nhau, phiên bản do Péter và Robinson phát triển (được hầu hết các tác giả gọi là "các" hàm Ackermann) được định nghĩa cho các số nguyên không âm như sau:

Hàm Ackermann cũng đã được biểu thị liên quan đến dãy hyperoperation:[13][14]

hoặc, được viết bằng ký hiệu mũi tên lên Knuth (mở rộng cho các chỉ số số nguyên ):
hoặc, tương đương, theo của hàm Buck F:[10]

Định nghĩa: dưới dạng hàm 1-ary được lặp lại[sửa | sửa mã nguồn]

Xác định n - lần lặp thứ của :

Phép lặp là quá trình soạn thảo một hàm với chính nó một số lần nhất định. Hàm hợp là một phép toán kết hợp, vì vậy .

Quan niệm hàm Ackermann là một chuỗi các hàm một ngôi, người ta có thể đặt .

Sau đó, hàm trở thành một dãy của hàm một ngôi[n 2], được xác định từ phép lặp:

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

Định nghĩa đệ quy của hàm Ackermann có thể được chuyển đổi một cách tự nhiên thành một hệ thống viết lại thuật ngữ (TRS).

TRS, dựa trên hàm hai ngôi[sửa | sửa mã nguồn]

Định nghĩa của hàm Ackermann hàm hai ngôi dẫn đến các quy tắc rút gọn rõ ràng[15][16]


Thí dụ

Tính toán

Trình tự giảm là [n 3]

Chiến lược ngoài cùng bên trái-ngoài cùng (một-bước):             Chiến lược ngoài cùng bên trái-trong cùng (một-bước):
         
         
         
         
         
         

Để tính toán , người ta có thể sử dụng một ngăn xếp, ban đầu chứa các phần tử .

Sau đó lặp lại hai phần tử trên cùng được thay thế theo quy tắc[n 4]

Sơ đồ, bắt đầu từ :

WHILE stackLength <> 1
{
   POP 2 elements;
   PUSH 1 or 2 or 3 elements, applying the rules r1, r2, r3
}

Mã giả được xuất bản trên [15].

Ví dụ: trên đầu vào ,

cấu hình ngăn xếp     phản ánh sự giảm[n 5]
         
         
         
         
         
         
         
         
         
         
         
         
         
         

Nhận xét

  • Chiến lược ngoài cùng bên trái-trong cùng được triển khai bằng 225 ngôn ngữ máy tính trên Mã Rosetta
  • Đối với tất cả phép tính của không quá các bước.[17]
  • Grossman & Zeitman (1988) đã chỉ ra rằng trong phép tính độ dài tối đa của ngăn xếp là , miễn là .
Thuật toán của riêng họ, vốn có tính lặp lại, tính toán trong thời gian và trong khoảng trắng.

TRS, dựa trên hàm một ngôi được lặp lại[sửa | sửa mã nguồn]

Tính chất[sửa | sửa mã nguồn]

Sự tăng nhanh của hàm này khiến cho không thể dùng các ký hiệu toán thông thường để biểu thị được và nó sẽ không có hiệu quả trong các tính toán khả dĩ.

Mã giả[sửa | sửa mã nguồn]

int Ackermann(m,n)
{
     if(m==0) Ackermann = n+1;
     else if(n==0) Ackermann=Ackermann(m-1,1);
     else Ackermann = Ackermann(m-1,Ackermann(m,n-1));
}

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

  1. ^ Monin & Hinchey 2003, tr. 61.
  2. ^ a b Ackermann 1928.
  3. ^ “Decimal expansion of A(4,2)”. kosara.net. 27 tháng 8 năm 2000. Bản gốc lưu trữ ngày 20 tháng 1 năm 2010.
  4. ^ Calude, Marcus & Tevy 1979.
  5. ^ Hilbert 1926, tr. 185.
  6. ^ van Heijenoort 1977.
  7. ^ Péter 1935.
  8. ^ Robinson 1948.
  9. ^ Ritchie 1965, tr. 1028.
  10. ^ a b Buck 1963.
  11. ^ Meeussen & Zantema 1992, tr. 6.
  12. ^ Munafo 1999a.
  13. ^ Sundblad 1971.
  14. ^ Porto & Matos 1980.
  15. ^ a b Grossman & Zeitman 1988.
  16. ^ Paulson 2021.
  17. ^ Cohen 1987, tr. 56, Proposition 3.16 (see in proof).
  • A.V. Aho, J.E. Hopcroft and J. D. Ullman, Data Structure and Algorithms (Reading, Mass., 1983)


Lỗi chú thích: Đã tìm thấy thẻ <ref> với tên nhóm “n”, nhưng không tìm thấy thẻ tương ứng <references group="n"/> tương ứng, hoặc thẻ đóng </ref> bị thiếu