Về kiến của Langton | Đường cao tốc, luật & turmite

Các luật

Kiến đi trên một lưới ô vuông vô hạn. Mỗi ô là trắng hoặc đen, và kiến hướng về bắc, đông, nam hoặc tây. Màu dưới chân nó quyết định toàn bộ bước đi tiếp theo. Trên ô trắng, kiến quay phải 90° (theo chiều kim đồng hồ), tô ô thành đen rồi tiến một ô. Trên ô đen, kiến quay trái 90° (ngược chiều kim đồng hồ), tô ô thành trắng rồi tiến một ô. Không có yếu tố ngẫu nhiên. Chạy cùng một khởi đầu hai lần, bạn sẽ được cùng một bức tranh.

Ba giai đoạn

Cho kiến bắt đầu trên một lưới trắng trống, và hành vi của nó chia thành ba quãng quen thuộc. 1. Đơn giản và đối xứng, từ bước 1 đến khoảng bước 500. Vệt đi nhỏ và thường đối xứng. 2. Hỗn loạn, từ khoảng bước 500 đến khoảng bước 10.000. Kiến bị mắc kẹt trong chính đường đi của mình. Bức tranh trông như nhiễu, dù mọi bước đều đã được định sẵn. 3. Đường cao tốc, sau khoảng 10.000 bước. Kiến khóa vào một chu kỳ 104 bước. Mỗi chu kỳ thêm một khối chéo lặp lại và dịch kiến sang ngang hai ô, tiến lên hai ô. Khi chu kỳ này bắt đầu ở vùng lưới trống, nó tiếp diễn mãi mãi, và kiến xây một đường cao tốc thẳng từ trong hỗn loạn.

Vì sao điều này quan trọng

Con kiến là một trong những minh họa rõ ràng nhất về tính trồi: cấu trúc phức tạp, khó đoán sinh ra từ một vài luật cục bộ. Nó cũng Turing-đầy đủ. Với một mẫu khởi đầu phù hợp, cùng loại luật có thể thực hiện bất kỳ phép tính nào mà máy tính đa năng làm được. Bạn không cần đến cơ chế đó để thưởng thức bức tranh. Riêng đường cao tốc đã là điều bất ngờ.

Màu, đàn kiến, lục giác và turmite

Ý tưởng này đã được mở rộng theo nhiều hướng. Các luật nhiều màu thay đen trắng bằng một danh sách hướng rẽ, viết thành chuỗi chữ L và R. RL là con kiến cổ điển. RLR, LLRR và LRRRRRLLR cho mỗi màu một hướng rẽ riêng. Kiến ghi màu kế tiếp trong danh sách, và một số luật mọc thành các hình học đối xứng thay vì một đường cao tốc duy nhất. Nhiều con kiến có thể dùng chung một lưới. Khi các vệt đi gặp nhau, chúng có thể cắt đứt đường cao tốc hoặc dệt nên hoa văn mà không con nào tự tạo được. Lưới lục giác cho kiến sáu hướng. Khi đó một lần rẽ phải hoặc trái là 60° thay vì 90°. Turmite giữ một trạng thái nội tại, một bộ nhớ nhỏ. Hướng rẽ và màu nó ghi phụ thuộc vào cả ô lẫn trạng thái đó, nên chính luật cũng thay đổi khi kiến di chuyển. Xoắn ốc, Đan dệt và Trôi dạt trong ứng dụng là các turmite hai trạng thái, hai màu.

Khám phá trong PictorX

Mở Kiến của Langton để chạy con kiến cổ điển, nhảy vào giai đoạn hỗn loạn hoặc bắt đầu trên đường cao tốc. Nhập luật rẽ, thêm kiến, chuyển lưới sang lục giác hoặc chọn một turmite. Kéo để di chuyển, cuộn để thu phóng, tô ô và thả thêm kiến. Lưu PNG hoặc mở khung vẽ trong trình chỉnh sửa PictorX. Kết hợp với Giả thuyết Collatz hoặc Phòng thí nghiệm phản ứng-khuếch tán để xem thêm những luật đơn giản tạo ra hình ảnh bất ngờ.

Hỏi thường xuyên

Ai đã phát minh ra kiến của Langton?

Chris Langton, vào năm 1986. Đây là một máy Turing hai chiều: một con kiến, một lưới vô hạn và một lần rẽ chỉ phụ thuộc vào màu của ô hiện tại.

Mọi mẫu khởi đầu đều xây nên đường cao tốc sao?

Lưới trống thì có, sau khoảng 10.000 bước, và chu kỳ 104 bước tiếp diễn khi kiến đã lên đường cao tốc. Các mẫu khởi đầu và luật khác có thể xây đường cao tốc, giữ trong giới hạn hoặc phát triển theo hình dạng khác. Mục yêu thích Đường cao tốc trong ứng dụng đặt con kiến cổ điển ngay sau khi chu kỳ bắt đầu.

Chuỗi luật có nghĩa là gì?

Mỗi ký tự là hướng rẽ cho một màu. R nghĩa là rẽ phải, L nghĩa là rẽ trái. Sau khi rẽ, kiến chuyển ô sang màu kế tiếp và tiến lên. RL là đen trắng. Chuỗi dài hơn là một con kiến nhiều màu.

Turmite khác con kiến thế nào?

Con kiến cổ điển không có bộ nhớ nào ngoài lưới. Turmite còn có một trạng thái nội tại. Màu ô và trạng thái đó cùng quyết định màu được ghi, hướng rẽ và trạng thái tiếp theo.