Hàm số Ackermann

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.

Lịch sử

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.

Định nghĩa

Cho hàm A(x, y), với miền xác định $\mathbb {N} ^{2}$ và miền giá trị là $\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

Tính chất

$A(x,1)=2x$

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

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

Sự tăng nhanh của hàm này khiến cho $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ĩ.

Mã giả

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

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