Hàm số Ackermann

Bài viết này cần thêm chú thích nguồn gốc để kiểm chứng thông tin. Mời bạn giúp hoàn thiện bài viết này bằng cách bổ sung chú thích tới các nguồn đáng tin cậy. Các nội dung không có nguồn có thể bị nghi ngờ và xóa bỏ. (Tháng 12/2022)

Hàm số Ackermann là một hàm thực được mang tên nhà toán học người Đức Wilhelm Ackermann (1896–1962). Hàm Ackermann đôi khi còn được gọi là hàm Ackermann-Peter.

Hàm Ackermenn được trình bày lần đầu tiên trong một cuốn sách về logic (mà nhà toán học David Hilbert là đồng tác giả) tựa đề Đức ngữ là Grundzuege der Theoretischen Logik (dịch nghĩa: Nền tảng của Lý thuyết Logic) xuất bản năm 1928.

Nguyên thủy thì hàm này được miêu tả với 3 biến số A (x, y, z). Sau đó, Rosza Peter đã đơn giản hóa bớt sang chỉ còn là hàm hai biến với các điều kiện ban đầu. Dạng ngày nay (thường được trình bày trong các sách giáo khoa) của hàm Ackermann là sự đơn giản hóa của Raphael Robinson.

Cho hàm A(x, y), với miền xác định ${\displaystyle \mathbb {N} ^{2}}$ và miền giá trị là ${\displaystyle \mathbb {N} }$

A (0, y) = 1, nếu y ≥ 0
A (1, 0) = 2
A (x, 0) = x + 2, nếu x ≥ 0
A (x, y) = A (A (x - 1, y), y - 1), nếu x ≥ 1 và y ≥ 1

${\displaystyle A(x,1)=2x}$

${\displaystyle A(x,2)=2^{x}}$

${\displaystyle A(x,3)=2^{2^{2^{...x}}}}$

Sự tăng nhanh của hàm này khiến cho ${\displaystyle A(x,4)}$ 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ĩ.

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));
}

• A.V. Aho, J.E. Hopcroft and J. D. Ullman, Data Structure and Algorithms (Reading, Mass., 1983)