Hàm số Ackermann

Bách khoa toàn thư mở Wikipedia
Bước tới: menu, tìm kiếm

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 (18961962). Hàm Ackermann đôi khi còn được gọi là hàm Ackermann-Peter.

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

Hàm Ackermenn được trình bày lần đầu tiên trong một cuốn sách về lô gíc (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 Lô gíc 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[sửa | sửa mã nguồn]

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

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

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ả[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]

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