Các nhà khoa học đã tìm ra số Dedekind thứ 9 với giá trị không thể tưởng tượng

Làm nên lịch sử với con số có 42 chữ số

Các nhà khoa học tại Đại học Paderborn và KU Leuven đã giải mã một bí ẩn toán học kéo dài hàng thập niên với số Dedekind thứ 9. Các chuyên gia trên toàn thế giới đã tìm kiếm giá trị này từ năm 1991. Các nhà khoa học Paderborn đã tìm ra dãy số chính xác với sự trợ giúp của siêu máy tính Noctua. Các kết quả sẽ được trình bày vào tháng 9 tại Hội thảo quốc tế về hàm Boolean và ứng dụng của chúng (BFA) tổ chức tại Na Uy.

Khởi đầu là dự án luận văn thạc sĩ của Lennart Van Hirtum (khi đó là sinh viên khoa học máy tính tại KU Leuven và hiện là cộng tác viên nghiên cứu tại Đại học Paderborn) đã đạt được thành công lớn. Các nhà khoa học tham gia nối tiếp một công trình lừng lẫy: Những con số trước đó trong dãy số Dedekind được tìm thấy bởi chính nhà toán học Richard Dedekind khi ông xác định vấn đề vào năm 1897, và sau đó là những bộ óc vĩ đại trong khoa học máy tính thời kỳ đầu như Randolph Church và Morgan Ward. Van Hirtum nói: “Trong 32 năm, việc tính toán D(9) là một thách thức để ngỏ và người ta đặt câu hỏi liệu có bao giờ có thể tính được con số này hay không".

Số trước đó trong dãy số Dedekind, tức số Dedekind thứ 8, được tìm thấy vào năm 1991 bằng cách sử dụng Cray 2, siêu máy tính mạnh nhất vào thời điểm đó. Cùng với những người hướng dẫn luận văn thạc sĩ tại Đại học quốc gia Anh, Van Hirtum mô tả động cơ thúc đẩy dự án đầy tham vọng khi dự định thực hiện: “Chúng tôi bấy giờ đã hình dung được rằng mình có thể tính được số thứ 9 trên một siêu máy tính lớn”.

Hạt cát, cờ vua và siêu máy tính

Đối tượng chính của các số Dedekind là cái gọi là các hàm Boolean đơn điệu. Van Hirtum giải thích: "Về cơ bản, bạn có thể nghĩ về một hàm Boolean đơn điệu trong hai, ba và vô hạn chiều như một trò chơi với một khối lập phương n chiều. Bạn cân bằng khối lập phương ở một góc và sau đó tô màu mỗi góc còn lại thành màu trắng hoặc màu đỏ. Chỉ có một quy tắc: bạn không bao giờ được đặt một góc màu trắng trên một màu đỏ. Điều này tạo ra một loại giao điểm đỏ-trắng thẳng đứng. Mục tiêu của trò chơi là đếm xem có bao nhiêu vết cắt khác nhau. Số của chúng là những gì được định nghĩa là số Dedekind. Các con số nhanh chóng trở nên khổng lồ trong quá trình này: số Dedekind thứ 8 đã có 23 chữ số".

Các con số tương đối lớn - nhưng dễ tính toán hơn nhiều - được biết đến từ một câu chuyện cổ liên quan đến việc phát minh ra trò chơi cờ vua. Van Hirtum kể: “Theo giai thoại này, người phát minh ra trò chơi cờ vua chỉ yêu cầu nhà vua cho một vài hạt gạo trên mỗi ô của bàn cờ như một phần thưởng: một hạt trên ô thứ nhất, hai hạt trên ô thứ hai, bốn hạt trên ô thứ ba… cứ thế gấp đôi số hạt gạo trên mỗi ô sau. Nhà vua ban đầu tưởng là ít nhưng sau đó nhanh chóng nhận ra rằng yêu cầu này là không thể thực hiện được. Đơn giản vì trên toàn thế giới không tồn tại nhiều gạo như vậy. Số hạt gạo trên bảng hoàn chỉnh sẽ có 20 chữ số - một số lượng không thể tưởng tượng được, nhưng vẫn nhỏ hơn D(8). Khi bạn nhận ra các mức độ lớn của con số này, rõ ràng là cần cả một phương pháp tính toán hiệu quả và một máy tính cực nhanh để tìm ra D(9)" .

Cột mốc: Năm trở thành tháng

Để tính toán D(9), các nhà khoa học đã sử dụng một kỹ thuật được phát triển bởi Patrick De Causmaecker được gọi là công thức hệ số P. Nó cung cấp một cách để tính các số Dedekind không phải bằng cách đếm mà bằng nhiều thuật toán kết hợp. Điều này cho phép D(8) được giải mã chỉ trong 8 phút trên máy tính xách tay thông thường. Tuy nhiên, với tốc độ "8 phút" cho ra D(8) sẽ trở thành hàng trăm nghìn năm mới cho ra D(9). Van Hirtum cho rằng ngay cả khi sử dụng một siêu máy tính lớn dành riêng cho nhiệm vụ này, vẫn sẽ mất nhiều năm để hoàn thành phép tính. Vấn đề chính là số lượng thuật toán trong công thức này tăng lên cực kỳ nhanh.

Van Hirtum phân tích: "Trong trường hợp của chúng tôi, bằng cách khai thác tính đối xứng trong công thức, chúng tôi có thể giảm số lượng số hạng xuống 'chỉ' 5,5*10^18 - một lượng rất lớn. Để so sánh, thì bạn cần biết số lượng hạt cát trên Trái đất là khoảng 7,5* 10^18. Con số này cũng không quá ghê gớm. Đối với một siêu máy tính hiện đại, các hoạt động trong phạm vi 5,5*10^18 khá dễ quản lý nhưng vấn đề là việc tính toán các thuật toán này trên bộ xử lý thông thường sẽ rất chậm và việc sử dụng GPU với công nghệ tăng tốc phần cứng nhanh nhất hiện tại cho nhiều ứng dụng AI, cũng không hiệu quả đối với thuật toán này.

Giải pháp: phần cứng dành riêng cho ứng dụng sử dụng các đơn vị số học song song và chuyên dụng cao - gọi là FPGA. Van Hirtum đã phát triển một nguyên mẫu ban đầu cho bộ tăng tốc phần cứng và bắt đầu tìm kiếm một siêu máy tính có các FPGA cần thiết. Trong quá trình này, Van Hirtum biết đến máy tính Noctua 2 tại Trung tâm điện toán song song Paderborn (PC2) thuộc Đại học Paderborn, nơi có một trong những hệ thống FPGA mạnh nhất thế giới.

Giáo sư Tiến sĩ Christian Plessl, người đứng đầu PC2, giải thích: "Khi Lennart Van Hirtum và Patrick De Causmaeker liên hệ với chúng tôi, ngay lập tức chúng tôi sẵn lòng hỗ trợ dự án táo bạo này. Giải quyết các bài toán tổ hợp khó với FPGA là một lĩnh vực đầy hứa hẹn của ứng dụng và Noctua 2 là một trong số ít siêu máy tính trên toàn thế giới mà thử nghiệm này hoàn toàn có thể thực hiện được. Các yêu cầu về độ ổn định và độ tin cậy cực cao cũng đặt ra thách thức và thử nghiệm đối với cơ sở hạ tầng của chúng tôi. Nhóm tư vấn chuyên gia FPGA đã làm việc chặt chẽ với Van Hirtum để điều chỉnh và tối ưu hóa ứng dụng".

Sau vài năm phát triển, chương trình đã chạy trên siêu máy tính trong khoảng năm tháng. Và rồi thời điểm thu hoạch đã đến, các nhà khoa học đã tìm thấy số Dedekind thứ 9: 28638657766829811128469151667598498 812 366.

Vấn đề lại đặt ra là khi nào tìm ra con số Dedekind thứ 10. Chắc chắn là có số đó nhưng tính toán để tìm ra nó thì cần một siêu máy tính mạnh hơn nữa mà hiện tại thì con người chưa có. Nếu dùng máy tính hiện giờ để tính toán thì cũng giống như tìm cách dùng tàu du hành có tốc độ âm thanh đi đến hành tinh nào đó ngoài hệ Mặt trời cách chúng ta hàng chục năm ánh sáng.

8 số đầu trong dãy Dedekind: 3, 6, 20, 168, 7581, 7828354, 2414682040998, 56130437228687557907788.