KHÔNG THUẬT TOÁN NÀO NHẬN DIỆN ĐƯỢC MỘT SỐ HÌNH DẠNG BỐN CHIỀU

Có những câu hỏi không có công thức giải. Không phải vì chưa ai tìm ra, mà vì người ta đã chứng minh được rằng không có thuật toán nào — không có quy trình từng bước nào, dù dài đến đâu, chạy trên bất kỳ máy tính nào — có thể luôn trả lời chúng chính xác. Cameron McA. Gordon, tại Đại học Texas ở Austin, bổ sung thêm hai câu hỏi như vậy về các hình dạng bốn chiều.

Đây có phải cùng một hình dạng?

Các nhà toán học gọi những hình dạng này là đa tạp 4 chiều (4-manifolds): những không gian mà, khi nhìn cận cảnh, ở mọi nơi đều trông giống không gian bốn chiều thông thường. Để đưa chúng cho máy tính, bài báo giả định chúng được dựng từ những mảnh phẳng dán lại với nhau (“tuyến tính từng mảnh”, hay PL — piecewise linear), để mỗi hình dạng có thể được mô tả bằng một danh sách dữ liệu hữu hạn. Câu hỏi cơ bản khi đó là: cho hai hình dạng như vậy, chúng có giống nhau không, nếu được phép biến dạng liên tục?

Năm 1958, A. A. Markov chứng minh rằng câu hỏi này không có thuật toán. Chứng minh của Markov biến bài toán về hình dạng thành một bài toán về nhóm: tồn tại những nhóm, được xác định bởi hữu hạn quy tắc, mà với chúng không thuật toán nào có thể quyết định một tổ hợp cho trước của các phần tử có bằng phần tử đơn vị hay không — “bài toán từ” (word problem). Từ một nhóm như vậy, người ta có thể dựng nên những hình dạng mà một thuật toán chỉ có thể phân biệt bằng cách giải bài toán bất khả đó.

Đếm ngược xuống bảy

Lập luận của Markov thậm chí còn gắn độ khó vào những hình dạng cụ thể. Lấy S², bề mặt của một quả bóng thông thường, và tạo tích S² × S², một hình dạng bốn chiều. Dán k bản sao của nó lại với nhau (một “tổng liên thông”, ký hiệu #k). Với một số giá trị k, không thuật toán nào có thể quyết định một hình dạng cho trước có phải là #k(S² × S²) hay không. Vậy k là bao nhiêu?

Bài báo lần lại cuộc đếm ngược. Một nhóm có bài toán từ không giải được và 12 quy tắc, do Borisov tìm ra năm 1969, cho ra 14 bản sao. Gordon hạ con số đó xuống 12 vào năm 2022. M. Tancer tìm ra một lối đi mới, qua phép phân loại các hình dạng bốn chiều của Freedman, và đạt 9 trong phiên bản “tô pô”, nơi các hình dạng không nhất thiết phải được dựng từ những mảnh phẳng. Một phiên bản trước của công trình này đạt 8. Rồi Kegel, Li và Ren dựng một nhóm không giải được nhỏ hơn nhiều — 3 phần tử sinh và 9 quy tắc — đạt 7 trong phiên bản tô pô và 9 trong phiên bản mảnh phẳng.

Gordon làm cho lối đi của Tancer cũng hiệu quả với các hình dạng được dựng từ những mảnh phẳng, và chứng minh:

Không có thuật toán nào quyết định được một đa tạp 4 chiều cho trước có giống hệt, từng mảnh một, với tổng liên thông của 7 bản sao của S² × S² hay không.

Cốt lõi của chứng minh là một bộ từ điển. Với mỗi từ w trong nhóm của Kegel, Li và Ren, Gordon dựng một hình dạng bốn chiều. Nếu w bằng phần tử đơn vị, một chuỗi các phép biến đổi được phép trên các quy tắc — các phép biến đổi Andrews-Curtis, vốn viết lại mô tả mà không làm thay đổi hình dạng — cho thấy hình dạng đúng là bảy bản sao của S² × S². Nếu không, hình dạng chứa những vòng lặp không thể thắt lại thành một điểm — điều không bao giờ xảy ra trong bảy bản sao của S² × S² — nên nó không thể là bảy bản sao đó. Do đó, một thuật toán nhận diện được #7(S² × S²) sẽ giải được bài toán từ, điều vốn không thể.

Những mặt cầu thắt nút

Câu hỏi thứ hai là về nút. Một nút thông thường là một đường tròn bị thắt lại trong không gian ba chiều, và việc quyết định một nút có thể gỡ ra được hay không là khả thi: có một thuật toán, do Haken đưa ra. Lên một chiều, một mặt cầu hai chiều có thể bị thắt nút bên trong không gian bốn chiều. Ở các chiều cao hơn, bài toán tương ứng đã được biết là không có thuật toán. Với các mặt cầu hai chiều trong mặt cầu bốn chiều S⁴, chưa ai biết.

Gordon chứng minh rằng bên trong #7(S² × S²), không có thuật toán nào quyết định được một mặt cầu hai chiều — hay bất kỳ mặt nào, định hướng được hay không — có bị thắt nút hay không. Trên đường đi, bài báo dựng một mặt cầu trong hình dạng đó mà không gian bao quanh nó có một nhóm với bài toán từ không giải được, và, trong 12 bản sao của S² × S², một mặt cầu mà nhóm của nó chứa một bản sao của mọi nhóm có thể được mô tả bởi một máy tính.

Giải thưởng: không bản sao nào

Bài báo nêu rõ mục tiêu: đưa số bản sao xuống không. Không bản sao nghĩa là chính mặt cầu bốn chiều S⁴. Ở năm chiều trở lên, không thuật toán nào có thể nhận diện mặt cầu; ở hai và ba chiều thì có. Bốn chiều vẫn còn bỏ ngỏ — câu hỏi liệu có thể phát hiện các mặt cầu thắt nút trong S⁴ hay không cũng vậy. Mỗi bản sao được loại bỏ lại đưa cả hai câu hỏi đến gần lời giải hơn.