ĐÚNG, NHƯNG KHÔNG THỂ CHỨNG MINH
Hãy hình dung một đám đông hàng xóm, mỗi cặp có một yêu cầu riêng. Nếu mọi yêu cầu đều có thể được đáp ứng cùng lúc, ai cũng hài lòng. Nếu hai yêu cầu xung đột, sẽ có người phải nhường. Các nhà vật lý nghiên cứu những nam châm làm từ các spin lượng tử đối mặt với đúng câu hỏi này. Mỗi cặp spin lân cận có một quy tắc năng lượng, và hệ cố gắng đạt tới năng lượng thấp nhất của nó. Khi một trạng thái duy nhất có thể thỏa mãn mọi cặp cùng lúc, mô hình được gọi là không bất mãn (frustration-free).
Những mô hình như vậy rất được coi trọng. Các ví dụ nổi tiếng gồm mô hình AKLT và mã toric (toric code) của Kitaev, những điểm tham chiếu cho các pha vật chất kỳ lạ. Việc không bất mãn cũng đặt ra những giới hạn chặt chẽ về cách một vật liệu có thể hành xử ở năng lượng thấp. Vì vậy, một câu hỏi tự nhiên nảy sinh: cho trước quy tắc của một cặp, mô hình có không bất mãn trên các mạng ở mọi kích thước hay không?
Naoto Shiraishi, ở Đại học Tokyo, đã nghiên cứu câu hỏi này trên một lưới vuông các spin, với cùng một quy tắc lặp lại giữa mọi cặp lân cận. Mỗi spin có thể nhận d trạng thái khác nhau. Câu trả lời gồm hai phần tưởng chừng mâu thuẫn với nhau.
Một mạng là đủ
Với bất kỳ một kích thước mạng riêng lẻ nào, câu hỏi chỉ là đại số tuyến tính thông thường. Rắc rối nằm ở vô số kích thước. Kiểm tra những lưới ngày càng lớn có thể phát hiện một thất bại, nhưng không bao giờ chứng minh được thành công cho tất cả.
Định lý thứ nhất loại bỏ cái vô hạn đó. Với mỗi giá trị của d, có một kích thước ngưỡng hữu hạn, như nhau cho mọi quy tắc khả dĩ. Nếu một mô hình không bất mãn trên một lưới có kích thước đó, nó không bất mãn trên mọi lưới. Vậy bài toán là quyết định được: tồn tại một thuật toán luôn trả lời có hoặc không.
Chìa khóa là một kết quả kinh điển của đại số, định lý cơ sở Hilbert. Điều kiện ở mỗi kích thước có thể được viết thành một tập các phương trình đa thức, luôn với cùng 2d⁴ ẩn — các phần tử của hai ma trận quy tắc. Định lý bảo đảm rằng một danh sách vô hạn các phương trình như vậy có cùng tập nghiệm với một phần hữu hạn nào đó của nó. Vì một lưới không bất mãn thì cũng vẫn không bất mãn trên mọi lưới nhỏ hơn được cắt ra từ nó, khi đó một kích thước duy nhất là đủ.
Đây không phải là một kết quả hiển nhiên. Trên đúng cùng loại mô hình, một câu hỏi liên quan — liệu có một khe năng lượng phía trên trạng thái thấp nhất hay không — đã được chứng minh là không quyết định được, ngay cả với d cố định.
Một bộ gạch đi săn mâu thuẫn
Định lý thứ hai đi theo chiều ngược lại. Giả sử rằng các tiên đề chuẩn của toán học, được gọi là ZFC, không chứa mâu thuẫn nào, thì tồn tại một mô hình không bất mãn mà tính không bất mãn của nó không thể chứng minh được từ các tiên đề đó.
Cách dựng sử dụng gạch Wang: những hình vuông có các cạnh được tô màu, được đặt mà không xoay, trong đó các viên kề nhau phải khớp nhau. Với bất kỳ chương trình máy tính nào, người ta có thể thiết kế một tập hữu hạn các viên gạch có thể phủ kín toàn bộ mặt phẳng vô hạn khi và chỉ khi chương trình chạy mãi mãi. Mỗi viên gạch trở thành một trạng thái của một spin. Mỗi cặp gạch lân cận bị cấm tốn một đơn vị năng lượng. Mô hình là không bất mãn đúng khi các viên gạch có thể phủ kín mặt phẳng.
Bây giờ hãy chọn chương trình duyệt qua mọi chứng minh khả dĩ để tìm một mâu thuẫn trong ZFC, và dừng lại nếu tìm thấy. Nếu ZFC nhất quán, chương trình không bao giờ dừng, và mô hình là không bất mãn. Nhưng nếu ZFC có thể chứng minh điều đó, nó sẽ chứng minh được tính nhất quán của chính nó — điều mà định lý bất toàn thứ hai của Gödel cấm.
Mô hình là tường minh, dù quá phức tạp để viết ra. Các quy tắc của nó thậm chí không thực sự mang tính lượng tử: các số hạng năng lượng đều giao hoán với nhau, giống như những ràng buộc cổ điển đơn giản.
Một ngưỡng tồn tại nhưng không thể gọi tên
Làm sao một bài toán có thể quyết định được mà vẫn chứa một mệnh đề không thể chứng minh? Câu trả lời nằm ở ngưỡng. Ngưỡng hữu hạn với mọi d, nhưng không thuật toán nào tính được nó từ d. Với số chiều ứng với mô hình không thể chứng minh ấy, các tiên đề chứng minh được rằng tồn tại một ngưỡng hữu hạn — vậy mà chúng không thể chứng minh rằng bất kỳ con số cụ thể nào là một ngưỡng như vậy.
Ngưỡng này cũng tăng nhanh đến phi lý: ít nhất cũng nhanh như hàm hải ly bận rộn (busy beaver) — số dấu lớn nhất mà một chương trình dừng với một số trạng thái cho trước có thể để lại trên băng của nó — hàm vượt xa mọi hàm mà máy tính có thể tính được. Giá trị của nó cho các máy năm trạng thái chỉ mới được xác định vào năm 2024, theo bài báo; giá trị cho sáu trạng thái vẫn chưa được biết.
Khoảng cách giữa tồn tại và biết được
Tính quyết định được chỉ đòi hỏi tồn tại một thuật toán đúng, chứ không đòi hỏi ai đó có thể xây dựng nó. Trong hầu hết các trường hợp quen thuộc, sự khác biệt này không quan trọng. Ở đây, tác giả lập luận, nó trở thành toàn bộ câu chuyện — và nó xuất hiện trong một bài toán vật lý bình thường trên một lưới vuông đơn giản. Tác giả cho biết ChatGPT đã được dùng để xác lập kết quả về tính quyết định được và để làm rõ cách kết quả này ăn khớp với kết quả về tính không thể chứng minh. Việc xác định các ngưỡng thực tế, ngay cả với những spin rất nhỏ, được để lại như một thách thức mở.
