Ô tự động (cellular automaton) là một lưới ô, mỗi ô mang một trạng thái (ví dụ sống hoặc chết, đen hoặc trắng), và sau mỗi bước thời gian, mọi ô cùng đổi trạng thái theo một luật chỉ nhìn vào chính nó và các ô hàng xóm. Luật thường ngắn đến mức viết vừa một dòng, nhưng khi chạy hàng trăm, hàng nghìn bước, lưới có thể sinh ra hoa văn đều đặn, hỗn loạn, thậm chí những "sinh vật" di chuyển được. Ô tự động là công cụ cơ bản để hiểu vì sao trật tự phức tạp trong tự nhiên có thể nảy sinh mà không cần ai vẽ sẵn.
Bốn thành phần của một ô tự động
| Thành phần | Nghĩa | Ví dụ |
|---|---|---|
| Lưới | Không gian chia thành các ô bằng nhau | Một hàng ô (một chiều), một bàn cờ ô vuông (hai chiều), lưới lục giác |
| Trạng thái | Mỗi ô ở một trong số hữu hạn tình trạng | Sống/chết; cây/cháy/tro; 0/1/2 |
| Vùng lân cận | Những ô mà luật được phép "nhìn" | Hai ô kề bên trong lưới một chiều; 4 hoặc 8 ô quanh trong lưới vuông |
| Luật | Cách tính trạng thái mới từ trạng thái cũ của ô và lân cận | "Ô chết có đúng 3 hàng xóm sống thì sống lại" |
Thêm một điều kiện ngầm: mọi ô cập nhật cùng một lúc, dựa trên trạng thái của bước trước. Nếu cập nhật lần lượt từng ô, kết quả sẽ khác hẳn. Nhiều người viết chương trình đầu tiên mắc đúng lỗi này.
Lân cận von Neumann và lân cận Moore
Trên lưới ô vuông có hai cách chọn hàng xóm phổ biến. Lân cận von Neumann gồm 4 ô chung cạnh: trên, dưới, trái, phải. Lân cận Moore gồm 8 ô, tính cả 4 ô chéo. Hai cái tên lấy từ John von Neumann và Edward F. Moore, những người dùng chúng trong các nghiên cứu đầu tiên.
Lịch sử ngắn: từ máy tự sao chép tới màn hình máy tính
- Thập niên 1940: ở Los Alamos, nhà toán học Stanisław Ulam nghiên cứu sự lớn lên của các hình trên lưới. Ông gợi ý cho John von Neumann dùng lưới ô để mô hình hoá một cỗ máy tự sao chép. Von Neumann xây dựng một ô tự động 29 trạng thái; công trình được Arthur Burks biên tập và in năm 1966, sau khi von Neumann mất.
- 1970: nhà toán học John Horton Conway công bố mô hình "Đời sống", được giới thiệu trong cột toán giải trí của Martin Gardner trên tạp chí Scientific American. Chỉ bốn luật trên lưới vuông hai trạng thái, nhưng sinh ra vô số hình kỳ lạ. Đây là lúc ô tự động được công chúng biết đến.
- 1983: Stephen Wolfram nghiên cứu có hệ thống các ô tự động một chiều đơn giản nhất, trong đó có quy tắc 30 sinh ra hoa văn trông như ngẫu nhiên.
- Từ thập niên 1980 trở đi: ô tự động được dùng để mô phỏng cháy rừng, dòng xe cộ, tinh thể băng, sự lan của dịch bệnh, đống cát sụt lở, và trở thành nền móng của lĩnh vực sự sống nhân tạo.
Thử tay một ô tự động trên giấy kẻ ô
Cách hiểu nhanh nhất là làm bằng bút chì. Lấy một tờ giấy kẻ ô, dùng mỗi hàng là một bước thời gian, chạy từ trên xuống. Luật đơn giản sau thường gọi là quy tắc 90:
Ô ở hàng dưới được tô đen nếu đúng một trong hai ô chéo phía trên nó (trên-trái, trên-phải) đen; còn lại để trắng.
Bắt đầu hàng đầu tiên với một ô đen duy nhất ở giữa. Sau khoảng 16 hàng, một hình tam giác lồng tam giác sẽ hiện ra, giống tam giác Sierpiński mà sách hình học hay vẽ. Không ai vẽ hình đó; nó tự nảy ra từ một luật chỉ nhìn hai ô. Đây chính là bài học trung tâm của ô tự động: luật cục bộ, hình toàn cục.
Bốn kiểu hành vi theo Wolfram
Khi chạy thử hàng loạt luật, Wolfram nhận thấy kết quả thường rơi vào bốn nhóm. Cách chia này không phải định lý chặt chẽ mà là một bảng phân loại thực nghiệm, nhưng rất hữu ích khi quan sát:
| Lớp | Hành vi | Hình ảnh gợi nhớ |
|---|---|---|
| Lớp 1 | Mọi thứ nhanh chóng về một trạng thái đồng nhất | Một cánh đồng tắt lửa hết |
| Lớp 2 | Ổn định thành các khối đứng yên hoặc lặp lại theo chu kỳ | Hoa văn vải dệt |
| Lớp 3 | Hỗn loạn, trông như ngẫu nhiên, không lặp lại | Mặt nước sôi |
| Lớp 4 | Các cấu trúc nhỏ di chuyển, va chạm, tương tác phức tạp ở ranh giới giữa trật tự và hỗn loạn | Một hệ sinh thái |
Lớp 4 là lớp hấp dẫn nhất, vì chính ở đây xuất hiện những thứ giống như "sự sống": cấu trúc tự duy trì, di chuyển, sinh ra cấu trúc khác. "Đời sống" của Conway thuộc lớp này.
Ô tự động mô phỏng tự nhiên thế nào
Cháy rừng
Mỗi ô là đất trống, cây hoặc lửa. Luật: cây cạnh lửa thì bắt lửa, lửa cháy xong thành đất trống, đất trống thỉnh thoảng mọc cây mới. Chạy lâu, mô hình cho thấy các đám cháy có đủ mọi kích cỡ, nhiều đám nhỏ, ít đám rất lớn, giống phân bố mà các nhà sinh thái quan sát ngoài thực tế. Nó cũng gợi ý vì sao dập tắt mọi đám cháy nhỏ có thể làm tích nhiên liệu cho một đám cháy lớn.
Dòng xe cộ
Năm 1992, Kai Nagel và Michael Schreckenberg đưa ra một ô tự động một chiều cho giao thông: mỗi ô là một đoạn đường, xe tăng tốc nếu phía trước trống, giảm tốc nếu gần xe trước, đôi khi phanh ngẫu nhiên. Mô hình tái tạo được hiện tượng "tắc đường ma" tự xuất hiện mà không có tai nạn nào.
Hoa văn và tinh thể
Một số ô tự động trên lưới lục giác tạo ra hình giống bông tuyết sáu cánh. Hoa văn trên vỏ một số loài ốc cũng được so sánh với hoa văn của ô tự động một chiều, vì mép vỏ ốc lớn lên từng dải, mỗi dải phụ thuộc vào dải trước, đúng như một lưới ô chạy theo thời gian.
Giới hạn: mô hình không phải là thật
Ô tự động hấp dẫn đến mức dễ khiến người ta nghĩ "vũ trụ là một lưới ô". Đây là một giả thuyết đã được vài nhà khoa học đề xuất, nhưng không phải là kết luận được chấp nhận rộng rãi. Phần lớn nhà sinh thái và sinh học dùng ô tự động như công cụ suy nghĩ: nó giúp kiểm tra xem một cơ chế đơn giản có đủ để sinh ra hiện tượng quan sát được hay không. Nếu đủ, đó là gợi ý đáng nghiên cứu tiếp; nếu không, phải tìm thêm yếu tố khác.
Góc nhìn hôm nay: tự thử luật
Ngày nay có thể chạy ô tự động ngay trên trình duyệt với nhiều chương trình miễn phí, hoặc tự viết bằng vài chục dòng mã Python. Học sinh có thể bắt đầu bằng giấy kẻ ô với quy tắc 90, rồi tự đặt luật riêng: đổi số hàng xóm cần để sống, đổi vùng lân cận, thêm trạng thái thứ ba. Mỗi thay đổi nhỏ có thể cho ra một thế giới hoàn toàn khác.
Muốn đọc thêm, có thể tìm sách giới thiệu về hệ phức hợp, các bài của Wolfram về ô tự động một chiều đơn giản, hay các tài liệu nhập môn về sự sống nhân tạo. Các bài tiếp theo trong danh mục này đi sâu vào từng mô hình: "Đời sống" của Conway, cỗ máy của von Neumann, quy tắc 30, hoa văn Turing, bầy chim Boids.
Câu hỏi thường gặp
Ô tự động là gì?
Là một lưới ô, mỗi ô có một trạng thái, và sau mỗi bước mọi ô cùng đổi trạng thái theo một luật chỉ dựa vào chính nó và các ô lân cận. Từ luật đơn giản, lưới có thể sinh ra hình rất phức tạp.
Ai phát minh ra ô tự động?
Ý tưởng được Stanisław Ulam và John von Neumann phát triển ở thập niên 1940, khi von Neumann tìm cách mô hình hoá một cỗ máy tự sao chép. Mô hình "Đời sống" của Conway năm 1970 làm ô tự động trở nên nổi tiếng.
Lân cận Moore và lân cận von Neumann khác nhau thế nào?
Lân cận von Neumann gồm 4 ô chung cạnh với ô đang xét. Lân cận Moore gồm 8 ô, tính thêm 4 ô ở góc chéo. Mô hình "Đời sống" của Conway dùng lân cận Moore.
Ô tự động được dùng để làm gì?
Để mô phỏng cháy rừng, dòng xe cộ, tinh thể, sự lan của dịch bệnh, hoa văn trên vỏ sinh vật và nghiên cứu sự sống nhân tạo. Nó giúp kiểm tra xem một cơ chế đơn giản có đủ sinh ra hiện tượng quan sát được không.
Vì sao ô tự động lại tạo ra hình phức tạp?
Vì mỗi ô ảnh hưởng tới hàng xóm, hàng xóm ảnh hưởng tiếp ra xa, và hiệu ứng tích lại qua nhiều bước. Luật cục bộ, lặp lại nhiều lần, có thể sinh ra trật tự toàn cục mà không ai thiết kế sẵn.
