Trò chơi Cuộc sống của Conway và lời giải cho bài toán chu kỳ kéo dài hơn nửa thế kỷ

Ba quy tắc sinh tử định hình vũ trụ John Conway

Năm 1969, nhà toán học người Anh John Conway giới thiệu một hệ thống mô phỏng toán học trên lưới ô vuông vô tận mang tên Trò chơi Cuộc sống (Game of Life). Trò chơi vận hành hoàn toàn tự động dựa vào trạng thái của các ô vuông (gọi là tế bào), mỗi ô chỉ nhận một trong hai trạng thái: “sống” hoặc “chết”. Qua từng mốc thời gian rời rạc gọi là “thế hệ”, số phận của mỗi tế bào được quyết định tuyệt đối bởi số lượng ô sống trong 8 ô láng giềng kề sát nó.

Vũ trụ tế bào này chuyển động không ngừng dựa trên ba quy luật tối giản:

• Sinh sản (Birth): Một ô “chết” sẽ hồi sinh thành “sống” ở thế hệ sau nếu có đúng 3 ô láng giềng đang sống.
• Sinh tồn (Survival): Một ô “sống” tiếp tục duy trì trạng thái sống nếu có 2 hoặc 3 ô láng giềng đang sống bao quanh.
• Diệt vong (Death): Một ô “sống” sẽ chết vì cô đơn nếu có ít hơn 2 láng giềng sống, hoặc chết vì quá tải dân số nếu có nhiều hơn 3 láng giềng sống kề bên.

Từ ba quy tắc tưởng như trò chơi con trẻ này, hàng nghìn dạng mẫu (pattern) phức tạp đã ra đời và được cộng đồng lưu trữ trong các thư viện trực tuyến. Bản thân John Conway là người đầu tiên tìm ra mẫu chớp tắt (blinker) có thể dao động tuần hoàn qua lại giữa 2 trạng thái. Chỉ một năm sau đó, ông phát hiện thêm cấu trúc xung nhịp (pulsar) phức tạp hơn, dao động luân phiên qua 3 trạng thái riêng biệt.

Cuộc săn tìm bộ dao động và câu hỏi về chu kỳ toàn năng

Ngay khi các cấu trúc tuần hoàn đầu tiên xuất hiện, giới toán học đã đặt ra câu hỏi nền tảng: Liệu Game of Life có tồn tại bộ dao động (oscillators) cho mọi chu kỳ thời gian hay không? Nói cách khác, trò chơi này có mang tính omniperiodic (chu kỳ toàn năng) — nghĩa là với bất kỳ số nguyên dương nào được chọn, luôn tồn tại một mẫu tế bào có khả năng tự lặp lại chính xác sau đúng ngần ấy thế hệ?

Lập trình viên kiêm nhà toán học Bill Gosper — người từng phát hiện 17 bộ dao động độc đáo — nhớ lại: “Ban đầu, chúng tôi chỉ thấy các chu kỳ 1, 2, 3, 4 và 15. Kỳ lạ là chu kỳ 15 lại xuất hiện khá thường xuyên khi tìm kiếm ngẫu nhiên.”

Dù từng cho rằng bộ dao động chu kỳ 5 là điều không tưởng sau hàng giờ quan sát, Gosper đã chứng kiến mẫu chu kỳ 5 được tìm ra vào năm 1971, tức chỉ hai năm sau khi trò chơi ra đời. Kể từ đó, việc săn tìm các bộ dao động trở thành tâm điểm của cộng đồng nghiên cứu, được tiếp sức mạnh mẽ bởi sự bùng nổ của máy tính. Việc các nhà nghiên cứu “tranh thủ dùng trộm” năng lực xử lý của các dàn máy lớn tại trường đại học hay doanh nghiệp để chạy thuật toán tìm kiếm đã trở thành giai thoại quen thuộc của thời kỳ này.

Kỷ nguyên vòng lặp: Từ sáng kiến Buckingham đến bước tiến Snark

Trong thập niên 1970, giới nghiên cứu dần lấp đầy các chu kỳ ngắn và một số chu kỳ dài, nhưng việc dò tìm ngẫu nhiên sớm chạm giới hạn. Đến năm 1996, David Buckingham — cố vấn máy tính tự do người Canada — tạo nên bước ngoặt lớn. Ông chứng minh hoàn toàn có thể xây dựng bộ dao động cho mọi chu kỳ từ 61 trở lên bằng cách gửi một dạng mẫu di chuyển quanh đường ray đóng kín theo vòng lặp vô tận.

Bằng cách điều chỉnh chiều dài vòng lặp và thời gian để mẫu hoàn thành một vòng quay, Buckingham có thể tạo ra chu kỳ dài tùy ý, miễn là lớn hơn 61. Ông hào hứng mô tả: “Nó giống như làm hóa học nhưng không có mùi khó chịu hay vỡ thủy tinh; bạn chế tạo các hợp chất rồi khám phá tương tác giữa chúng.”

Phát minh của Buckingham giải quyết trọn vẹn miền chu kỳ lớn hơn 61, nhưng khoảng cách từ 15 đến 43 lại là “cơn đau đầu” kéo dài nhiều thập niên, buộc các nhà khoa học phải sáng tạo những kỹ thuật mới nhằm đẩy lùi giới hạn của automata tế bào. Năm 2013, phát minh vòng lặp Snark (Snark loop) ra đời, cải tiến kỹ thuật của Buckingham và hạ thấp ngưỡng dựng chu kỳ tự động từ 61 xuống còn 43. Trước năm 2023, giới toán học chỉ còn thiếu đúng hai mảnh ghép duy nhất: chu kỳ 19 và chu kỳ 41. Cả hai đều là số nguyên tố — đối tượng mà nhà toán học Matthias Merzenich giải thích là rất khó vì không thể ghép từ các bộ dao động nhỏ hơn.

Chinh phục hai mắt xích 19 và 41: Khép lại hành trình hơn nửa thế kỷ

Các cấu trúc dao động chu kỳ nguyên tố vốn cực kỳ mong manh. Mitchell Riley, nhà nghiên cứu sau tiến sĩ tại Đại học New York Abu Dhabi, nhận xét: “Nếu bạn đặt sai dù chỉ một chấm nhỏ, toàn bộ cấu trúc thường sẽ phát nổ ngay lập tức.” Riley tập trung nghiên cứu loại dao động có tên là hassler, gồm mẫu hoạt động ở trung tâm và các thành phần cố định bên ngoài đóng vai trò chất xúc tác (catalyst) để đẩy mẫu trung tâm trở về trạng thái xuất phát.

Riley lập trình phần mềm Barrister để tự động rà soát các chất xúc tác bền vững. Sau nhiều lần thất bại, ông hiệu chỉnh mã nguồn để mở rộng tìm kiếm sang các dạng đối xứng và tìm ra một tương tác chất xúc tác khối mới có thể duy trì chu kỳ 19. Riley chia sẻ: “Mọi người từng thử những cuộc tìm kiếm phức tạp với rất nhiều chất xúc tác và mẫu trung tâm hiếm gặp, nhưng hóa ra tất cả những gì cần thiết chỉ là tìm ra chất xúc tác khối mới này.”

Trong khi đó, chu kỳ 41 được khám phá bởi Nicolo Brown, sinh viên ngành toán tại Đại học California, Santa Cruz. Brown đã sử dụng các tàu lượn (gliders) làm chất xúc tác, hiện thực hóa ý tưởng mà Merzenich từng đề xuất.

Với việc tìm thấy chu kỳ 19 và 41, bài báo công bố vào tháng 12 năm 2023 của Maia Karpovich (Đại học Maryland) cùng các đồng nghiệp đã chính thức khép lại hành trình hơn 50 năm: Game of Life chính thức được xác nhận là mang tính omniperiodic!

Cửa hàng đồ chơi vô tận và những chân trời tiếp nối

Cột mốc lịch sử này vừa khép lại một câu hỏi cổ điển, vừa mở ra nhiều hướng nghiên cứu mới đầy hứa hẹn. Như Maia Karpovich chia sẻ: “Mọi người ăn mừng trong một tuần — và rồi tiếp tục chuyển sang những bài toán khác. Có quá nhiều vấn đề đang chờ được giải quyết.”

Giới toán học lập tức đặt ra các bài toán tiếp theo: Liệu có thể thu nhỏ kích thước của các bộ dao động cho từng chu kỳ cụ thể? Có thể tìm thấy những bộ dao động mà toàn bộ tế bào đều chuyển động? Liệu ta có thể tạo ra các súng sinh mẫu (guns) với chu kỳ cố định hay các tàu vũ trụ (spaceships) di chuyển với vận tốc chuẩn xác? Nghiên cứu Game of Life, như Buckingham từng nhận định, quả thực “giống như một đứa trẻ đang thỏa sức khám phá trong một cửa hàng đồ chơi vô tận.”

Tầm vóc thực tiễn: Khám phá trật tự từ sự ngẫu sinh

Việc chứng minh tính omniperiodic không chỉ là lời giải cho một trò chơi toán học thuần túy, mà còn mang ý nghĩa sâu sắc đối với khoa học phức hợp (complexity science). Trò chơi Cuộc sống của Conway là mô hình trực quan mẫu mực cho “tính trỗi dậy” (emergence): từ một vài tiền đề vi mô đơn sơ, hệ thống có thể tự tổ chức để sinh ra các cấu trúc vĩ mô tinh vi có khả năng tự sao chép và vận hành như một cơ thể sống.

Các nguyên lý automata tế bào này đã và đang được ứng dụng thực tế trong mô phỏng dịch bệnh, giải mã cấu trúc tinh thể trong vật lý, thiết kế vi mạch sinh học và nghiên cứu trí tuệ nhân tạo. Hành trình nửa thế kỷ chinh phục bài toán chu kỳ toàn năng nhắc nhở chúng ta rằng: đằng sau những quy luật giản dị nhất luôn có thể ẩn giấu một vũ trụ trật tự và sâu sắc vô biên.

Bài viết tham khảo Quanta Magazine (quantamagazine.org).