Không có số tự nhiên lớn nhất: số nào cũng cộng thêm 1 được. Nhưng câu hỏi thú vị hơn là toán học đã gặp những số lớn cỡ nào khi làm việc nghiêm túc. Câu trả lời đi qua số Graham, rồi TREE(3), rồi hàm hải ly bận rộn mà máy tính không bao giờ tính hết, và dừng ở số Rayo, sinh ra từ một cuộc thi đặt tên số lớn ở MIT năm 2007.
Vì sao không có số lớn nhất
Lập luận chỉ có một dòng. Giả sử N là số tự nhiên lớn nhất. Khi đó N + 1 cũng là số tự nhiên và lớn hơn N. Mâu thuẫn. Vậy không tồn tại N.
Từ đây có một điều hay bị nhầm: "vô cực" không phải là số lớn nhất, và không phải một số tự nhiên. Mọi số trong bài này, dù khổng lồ tới đâu, đều hữu hạn, và đều nhỏ hơn hầu hết các số tự nhiên khác (vì phía sau mỗi số luôn còn vô số số lớn hơn). Chuyện so sánh các loại vô hạn với nhau là đề tài riêng của Cantor, ở đây không bàn.
Vì vậy câu hỏi đúng không phải "số nào lớn nhất" mà là "những số lớn nhất từng có ý nghĩa là gì" và "làm sao để gọi tên một số thật lớn bằng ít ký hiệu nhất".
Bậc thang tốc độ tăng
Trước khi gặp những số khổng lồ, hãy xem các hàm tăng nhanh tới mức nào. Bảng dưới đây cho n chạy từ 1 tới 5:
| n | n² | 2ⁿ | n! (giai thừa) | nⁿ | 2↑↑n (tháp số 2) |
|---|---|---|---|---|---|
| 1 | 1 | 2 | 1 | 1 | 2 |
| 2 | 4 | 4 | 2 | 4 | 4 |
| 3 | 9 | 8 | 6 | 27 | 16 |
| 4 | 16 | 16 | 24 | 256 | 65.536 |
| 5 | 25 | 32 | 120 | 3.125 | số có 19.729 chữ số |
Cột cuối là tháp luỹ thừa, 2↑↑5 = 2^2^2^2^2. Thêm một tầng là con số nhảy từ năm chữ số lên gần hai vạn chữ số. Số Graham dùng những phép còn cao hơn nhiều nấc. Nhưng các số dưới đây lại tăng theo cách mà không phép toán dạng mũi tên nào đuổi kịp.
TREE(3): bài toán trồng cây lớn hơn số Graham
TREE(3) sinh ra từ định lý cây của Joseph Kruskal (1960) và được nhà logic học Harvey Friedman khai thác: từ thập niên 1980 ông chỉ ra định lý này vượt sức của số học thông thường, về sau ông đặt ra hàm TREE. Phiên bản dễ hình dung như sau.
Bạn vẽ lần lượt từng cái cây (sơ đồ phân nhánh không có vòng), mỗi nút tô một trong k màu. Luật: cây thứ nhất được tối đa 1 nút, cây thứ hai tối đa 2 nút, cây thứ i tối đa i nút. Và không cây nào được "chứa" một cây vẽ trước đó, theo một nghĩa chặt chẽ về giữ màu và giữ quan hệ tổ tiên giữa các nút. Hỏi: dãy cây dài nhất có thể là bao nhiêu?
- Với 1 màu: TREE(1) = 1. Vẽ một nút xong là hết đường, vì cây nào sau đó cũng chứa nó.
- Với 2 màu: TREE(2) = 3.
- Với 3 màu: TREE(3) hữu hạn (định lý Kruskal bảo đảm điều đó) nhưng lớn hơn số Graham tới mức số Graham gần như bằng 0 khi đặt cạnh nó.
Cú nhảy từ 3 lên TREE(3) là một trong những cảnh gây sốc nhất của toán học: chỉ thêm một màu, độ dài dãy đi từ con số đếm trên một bàn tay lên một số mà mọi ký hiệu mũi tên đều bất lực. Friedman còn chỉ ra rằng chứng minh TREE(3) hữu hạn đòi hỏi những công cụ logic mạnh hơn số học thông thường. Đó là lý do con số này được các nhà logic quan tâm, không chỉ vì nó to.
Hàm hải ly bận rộn: con số máy tính không bao giờ tính hết
Năm 1962, nhà toán học Hungary Tibor Radó đặt ra bài toán hải ly bận rộn (busy beaver). Hãy hình dung một máy Turing, mô hình đơn giản nhất của máy tính: một băng giấy dài vô hạn chia ô, một đầu đọc ghi ký hiệu 0 hoặc 1, và một bảng luật với n trạng thái. Bắt đầu với băng toàn số 0. Trong mọi máy có n trạng thái mà cuối cùng chịu dừng, máy nào chạy lâu nhất trước khi dừng?
Số bước tối đa đó ký hiệu là BB(n), hay S(n). Các giá trị đã biết chắc:
| n (số trạng thái) | Số bước tối đa trước khi dừng | Biết chắc từ |
|---|---|---|
| 1 | 1 | thập niên 1960 |
| 2 | 6 | thập niên 1960 |
| 3 | 21 | thập niên 1960 |
| 4 | 107 | chứng minh đầy đủ năm 1983 |
| 5 | 47.176.870 | chứng minh năm 2024, kiểm bằng máy |
| 6 | chưa biết; đã biết lớn hơn tháp 15 tầng số 10 | cận dưới công bố năm 2022 |
Giá trị BB(5) được nhóm cộng tác trực tuyến bbchallenge chốt năm 2024, sau khi phải phân loại và loại trừ hàng chục triệu máy năm trạng thái, rồi kiểm chứng toàn bộ bằng trợ lý chứng minh Coq. Ứng viên máy chạy 47.176.870 bước đã được Heiner Marxen và Jürgen Buntrock tìm ra từ năm 1989, nhưng phải tới 2024, tức 62 năm sau câu hỏi của Radó, mới chứng minh được không máy năm trạng thái nào chạy lâu hơn mà vẫn dừng.
Điểm đặc biệt của hàm này: nó không tính được. Không có chương trình nào nhận n và trả về BB(n) cho mọi n. Lý do nối thẳng với bài toán dừng của Alan Turing (1936): nếu biết BB(n), ta chỉ cần chạy một máy n trạng thái đủ BB(n) bước; chưa dừng thì nó không bao giờ dừng. Thế là giải được bài toán dừng, điều Turing đã chứng minh là bất khả. Hệ quả là BB(n) tăng nhanh hơn mọi hàm tính được, kể cả hàm sinh ra TREE.
Còn một điều kỳ lạ nữa. Năm 2016, Adam Yedidia và Scott Aaronson dựng một máy Turing 7.918 trạng thái mà việc nó có dừng hay không là không thể chứng minh trong hệ tiên đề ZFC, nền tảng chuẩn của toán học. Nghĩa là giá trị BB(7.918) nằm ngoài tầm với của chính toán học hiện hành. Những cải tiến sau đó đã hạ con số trạng thái xuống còn vài trăm.
Số Rayo: cuộc so tài đặt tên số lớn ở MIT
Tháng 1 năm 2007, tại Viện Công nghệ Massachusetts, hai triết gia Agustín Rayo và Adam Elga tổ chức một cuộc "đấu số lớn": mỗi người lần lượt viết lên bảng một số lớn hơn số của đối phương, với điều kiện phải định nghĩa rõ ràng, không được kiểu "số của anh cộng một".
Con số thắng cuộc được gọi là số Rayo. Định nghĩa của nó, nói gọn: số tự nhiên nhỏ nhất lớn hơn mọi số có thể được gọi tên bằng một biểu thức trong ngôn ngữ logic bậc nhất của lý thuyết tập hợp dùng không quá một googol ký hiệu.
Ý tưởng thông minh ở chỗ: thay vì dựng thêm một phép toán, Rayo nhảy ra ngoài và nói "lớn hơn tất cả những gì có thể diễn đạt bằng một googol ký tự". Vì ngôn ngữ đó đủ mạnh để mô tả cả hàm hải ly bận rộn lẫn vô số thứ khác, số Rayo vượt qua chúng. Nó thường được coi là một trong những số lớn nhất từng được đặt tên một cách nghiêm túc, dù định nghĩa của nó tựa vào những vấn đề triết học về "gọi tên được" mà giới logic còn bàn.
So sánh các số khổng lồ có tên
| Tên | Xuất xứ | Cách hình dung |
|---|---|---|
| Googol | Edward Kasner, 1940 | 10¹⁰⁰, viết ra được trên một dòng |
| Googolplex | Kasner | 10 mũ googol, tháp ba tầng |
| Số Skewes | Stanley Skewes, 1933 | tháp bốn tầng, từ bài toán số nguyên tố |
| Số Graham | Ronald Graham, phổ biến 1977 | 64 tầng mũi tên Knuth |
| TREE(3) | Kruskal, Friedman | vượt mọi tầng mũi tên dựng theo kiểu Graham |
| BB(n) với n vài chục | Radó, 1962 | vượt mọi hàm tính được |
| Số Rayo | Agustín Rayo, 2007 | vượt mọi số gọi tên được bằng một googol ký hiệu |
Một ghi chú: googol, googolplex và câu chuyện cậu bé chín tuổi đặt tên chúng đã là đề tài quen thuộc; ở đây chúng chỉ là mấy bậc đầu của chiếc thang.
Góc nhìn hôm nay: một thử thách nhỏ cho bạn
Thử chơi lại cuộc đấu của Rayo và Elga với bạn bè, giới hạn trong một tấm thẻ giấy. Người đầu viết 9^9^9 (chín mũ chín mũ chín). Người sau viết 9↑↑9. Người tiếp viết 9↑↑↑9. Rồi ai đó nghĩ ra "định nghĩa một hàm f(n) = n với n mũi tên chèn giữa n và n, rồi viết f(f(9))". Bạn sẽ thấy rất nhanh: muốn thắng không phải viết thêm chữ số mà phải nghĩ ra một cách lặp mới.
Đó cũng là bài học của cả câu chuyện: số lớn không đến từ sức bền mà từ ý tưởng. Archimedes thắng chữ số Hy Lạp bằng một hệ bậc. Knuth thắng luỹ thừa bằng mũi tên. Radó thắng mọi công thức bằng một câu hỏi về máy tính. Rayo thắng tất cả bằng một câu hỏi về ngôn ngữ.
Đọc thêm: bài luận "Who Can Name the Bigger Number?" của Scott Aaronson (1999) là bài giới thiệu dễ đọc nhất về hàm hải ly bận rộn; trang của dự án bbchallenge ghi lại chi tiết cách họ chứng minh BB(5).
Câu hỏi thường gặp
Có số lớn nhất không?
Không. Với bất kỳ số tự nhiên N nào, N + 1 luôn lớn hơn nó, nên không tồn tại số lớn nhất. Vô cực cũng không phải số lớn nhất, vì nó không phải một số tự nhiên.
TREE(3) lớn hơn số Graham không?
Có, lớn hơn rất nhiều. TREE(1) = 1, TREE(2) = 3, nhưng TREE(3) đã vượt mọi số dựng bằng ký hiệu mũi tên Knuth theo kiểu số Graham, đến mức số Graham gần như không đáng kể khi đặt cạnh nó.
Hàm hải ly bận rộn (busy beaver) là gì?
Đó là số bước tối đa mà một máy Turing có n trạng thái chạy được trước khi dừng, bắt đầu từ băng trắng. Các giá trị đã biết là 1, 6, 21, 107 và 47.176.870 (với n = 5, chứng minh năm 2024). Hàm này không tính được bằng bất kỳ chương trình nào và tăng nhanh hơn mọi hàm tính được.
Số Rayo là gì?
Số Rayo là số nhỏ nhất lớn hơn mọi số có thể gọi tên bằng một biểu thức logic về tập hợp dài không quá một googol ký hiệu. Nó được Agustín Rayo đưa ra trong cuộc đấu số lớn ở MIT tháng 1 năm 2007 và thường được nhắc như một trong những số lớn nhất từng được đặt tên.
Vô cực có phải là một số không?
Vô cực không phải số tự nhiên và không đứng cuối dãy số đếm. Trong toán học nó được xử lý bằng những khái niệm riêng như giới hạn hay lực lượng tập hợp. Mọi số khổng lồ như số Graham hay TREE(3) đều hữu hạn.
