Về ô tô-mát tế bào | Trò chơi của sự sống, Luật 30, Luật 110 & hơn nữa

Bốn thành phần cơ bản

Mọi ô tô-mát tế bào đều được xây từ cùng bốn thành phần. Lưới là không gian các ô sinh sống. Nó có thể là một đường thẳng một chiều, một mặt phẳng hai chiều như bàn cờ, hay thậm chí một không gian ba chiều. Trạng thái là những gì một ô có thể là. Trong trường hợp đơn giản nhất, ô mang giá trị nhị phân: đen hoặc trắng, 1 hoặc 0. Lân cận là tập hợp các ô ảnh hưởng trực tiếp đến một ô. Trên lưới vuông, đó thường là lân cận Moore, gồm cả tám ô xung quanh, hoặc lân cận von Neumann, chỉ gồm các ô phía bắc, đông, nam và tây. Luật là bộ não của ô tô-mát: phần logic cho mỗi ô trạng thái mới. Ví dụ: nếu tôi đang sống nhưng có ít hơn hai ô lân cận sống, tôi sẽ chết vì cô đơn. Mọi ô áp dụng cùng các luật vào cùng một thời điểm.

1. Trò chơi của sự sống của Conway

Luật: B3/S23. Một ô sống tiếp tục sống nếu có 2 hoặc 3 ô lân cận sống. Một ô chết trở nên sống nếu có đúng 3. Mọi ô khác đều chết ở thế hệ tiếp theo. John Conway tạo ra nó năm 1970, và chuyên mục của Martin Gardner trên tạp chí Scientific American đã làm nó nổi tiếng. Nó tạo ra tàu lượn, bộ dao động và tàu vũ trụ. Cùng năm đó, Bill Gosper tìm ra súng tàu lượn đầu tiên: một mẫu bắn ra một tàu lượn mới sau mỗi 30 thế hệ, mãi mãi. Trò chơi của sự sống có thể thực hiện tính toán, vì tàu lượn có thể mang tín hiệu và va chạm như các cổng logic. Trên hết, nó cho thấy hành vi phức tạp mọc lên từ những luật đơn giản.

Súng tàu lượn Gosper trong Trò chơi của sự sống bắn ra một dòng tàu lượn chéo — Súng tàu lượn Gosper sau 330 thế hệ. Kết xuất bằng PictorX.

2. Luật 30

Loại: ô tô-mát tế bào sơ cấp một chiều. Trạng thái tiếp theo của mỗi ô phụ thuộc vào chính nó và hai ô lân cận, và mỗi thế hệ được vẽ thành một hàng mới bên dưới hàng cuối. Stephen Wolfram giới thiệu Luật 30 năm 1983. Bắt đầu từ một ô đen duy nhất, nó mọc thành một tam giác hỗn loạn. Dù luật là tất định, nó vẫn trông ngẫu nhiên, ngẫu nhiên đến mức cột giữa của nó từng được dùng làm bộ sinh số giả ngẫu nhiên. Những tam giác cùng kiểu xuất hiện trên sắc tố vỏ ốc biển Conus textile.

Tam giác Luật 30 mọc từ một ô đen duy nhất, hỗn loạn ở bên phải và có sọc ở bên trái — Luật 30 từ một ô đen, 224 thế hệ. Kết xuất bằng PictorX.

3. Luật 110

Loại: ô tô-mát tế bào sơ cấp một chiều, giống Luật 30, nhưng với một bảng tám câu trả lời khác. Luật 110 đã được chứng minh là vạn năng về mặt tính toán: Matthew Cook chỉ ra rằng với một hàng đầu tiên phù hợp, nó có thể mô phỏng bất kỳ phép tính nào mà máy tính đa năng thực hiện được. Nó có những cấu trúc chuyển động đi xuyên qua một nền lặp lại và tương tác khi gặp nhau. Chính những va chạm đó là phần logic mà phép chứng minh sử dụng. Nó cho thấy những luật rất đơn giản có thể mô phỏng phép tính bất kỳ như thế nào.

Luật 110 mọc từ một ô ở bên phải, lan sang trái thành những tam giác lồng nhau — Luật 110 từ một ô đen ở mép phải. Kết xuất bằng PictorX.

4. Brian's Brain

Trạng thái: tắt, bật (phát xung) và trơ. Luật: một ô tắt sẽ bật nếu có đúng 2 ô lân cận đang bật. Một ô bật chuyển sang trơ. Một ô trơ thì tắt. Brian Silverman đã tạo ra nó. Vì một ô phải nghỉ một thế hệ sau khi phát xung, mọi xung đều tiếp tục rời xa nơi nó vừa đi qua. Kết quả là một đám đông những họa tiết tự di chuyển, giống như sóng trong môi trường kích thích được, chẳng hạn mô thần kinh hay cơ tim, và thường trông sống động, hữu cơ.

Brian's Brain lan ra từ một mảng ngẫu nhiên, ô phát xung màu vàng và vệt mờ dần màu tím — Brian's Brain 70 thế hệ sau một mảng ngẫu nhiên, với các vệt mờ dần. Kết xuất bằng PictorX.

5. Wireworld

Trạng thái: trống, đầu electron, đuôi electron và dây dẫn. Luật: đầu thành đuôi, đuôi thành dây dẫn, và dây dẫn thành đầu khi có đúng 1 hoặc 2 ô lân cận là đầu. Ô trống vẫn trống. Brian Silverman cũng tạo ra Wireworld, vào năm 1987. Các ô dây dẫn là dây điện, và một đầu theo sau là một đuôi chính là một electron chạy dọc theo chúng. Nó có thể mô phỏng mạch điện tử: một vòng dây có một electron là bộ tạo xung nhịp, một khía nhỏ là điốt, và vài ô tạo thành một cổng logic. Người ta đã xây cả những chiếc máy tính hoàn chỉnh bên trong nó, chẳng hạn máy tính Wireworld của David Moore và Mark Owen, cỗ máy tính ra các số nguyên tố.

Mạch Wireworld với hai vòng tạo xung nhịp, hai điốt và một cổng XOR, electron màu xanh lam và đỏ trên dây vàng — Hai bộ tạo xung nhịp, hai điốt và một cổng XOR trong Wireworld. Kết xuất bằng PictorX.

256 luật và bốn lớp của Wolfram

Một ô một chiều có hai ô lân cận sẽ thấy một trong tám mẫu, từ 111 đến 000. Một luật cho trạng thái mới ứng với mỗi mẫu, nên nó gồm tám bit, và có 2⁸ = 256 luật sơ cấp. Đọc tám câu trả lời như một số nhị phân, bạn có tên của luật: Luật 30 là 00011110, và Luật 110 là 01101110. Stephen Wolfram phân loại các luật theo hành vi của chúng, từ trật tự đến hỗn loạn. 1. Lớp 1 ổn định thành một trạng thái đồng nhất. 2. Lớp 2 ổn định thành các cấu trúc bền vững hoặc lặp lại. 3. Lớp 3 vẫn hỗn loạn và trông ngẫu nhiên, như Luật 30. 4. Lớp 4 tạo ra các cấu trúc chuyển động và tương tác ở ranh giới giữa trật tự và hỗn loạn, như Luật 110.

Xếp hạng độ khó

Trò chơi của sự sống ★☆☆☆☆ · Luật 30 ★☆☆☆☆ · Brian's Brain ★★☆☆☆ · Wireworld ★★★★☆ · Luật 110 ★★★★★. Hai cái đầu tiên tự giải thích khi bạn quan sát. Luật 110 giấu các cấu trúc chuyển động của nó trong một nền lặp lại.

Đẹp nhất về thị giác

1. Brian's Brain · 2. Trò chơi của sự sống của Conway · 3. Luật 30 · 4. Luật 110 · 5. Wireworld.

Quan trọng nhất về toán học

1. Luật 110, vì tính vạn năng · 2. Trò chơi của sự sống, vì tính vạn năng và tính trồi · 3. Luật 30, vì hỗn loạn và ngẫu nhiên · 4. Wireworld, vì logic số · 5. Brian's Brain, vì các hệ kích thích được.

Trong tự nhiên, vật lý và mật mã học

Ô tô-mát tế bào được dùng để mô phỏng các hệ phức tạp trong tự nhiên, vật lý và mật mã học. Ý tưởng này bắt nguồn từ Stanisław Ulam và John von Neumann vào những năm 1940, khi họ dùng một lưới ô để thiết kế một cỗ máy có thể tự sao chép. Trong thế giới thực, bạn có thể thấy ô tô-mát tế bào trên sắc tố của một số vỏ ốc, như Conus textile, với những tam giác trông giống Luật 30, và trên vảy của thằn lằn đốm mắt (Timon lepidus), vốn chuyển giữa màu xanh lá và đen theo một luật gần với ô tô-mát tế bào. Các nhà vật lý dùng chúng để mô hình hóa dòng khí, đống cát và cháy rừng. Vẻ ngẫu nhiên bề ngoài của Luật 30 khiến nó trở thành ứng viên cho bộ sinh số ngẫu nhiên và mã dòng.

Khám phá trong PictorX

Mở Ô tô-mát tế bào để chạy cả năm. Xem súng tàu lượn, một hạm đội tàu vũ trụ, hoặc R-pentomino, mẫu cần 1.103 thế hệ mới ổn định. Nhập bất kỳ luật dạng Life nào như B36/S23, hoặc bất kỳ số luật sơ cấp nào từ 0 đến 255. Vẽ và xóa ô, gửi electron qua các mạch Wireworld, nối các cạnh và chuyển sang chế độ nhiều màu. Lưu PNG hoặc mở khung vẽ trong trình chỉnh sửa PictorX.

Hỏi thường xuyên

Ô tô-mát tế bào là gì?

Một lưới ô trong đó mỗi ô có một trạng thái. Ở mỗi nhịp, mọi ô cập nhật cùng nhau theo một luật cố định chỉ xét một ô và các ô lân cận. Dù luật đơn giản, các họa tiết có thể phức tạp và khó đoán.

Ai đã phát minh ra ô tô-mát tế bào?

Stanisław Ulam và John von Neumann, vào những năm 1940 tại Los Alamos. Trò chơi của sự sống của John Conway (1970) đã làm ý tưởng này trở nên phổ biến, và Stephen Wolfram nghiên cứu 256 luật sơ cấp vào những năm 1980.

Những ô tô-mát tế bào nào là Turing đầy đủ?

Trong năm ô tô-mát ở đây, Luật 110 và Trò chơi của sự sống đã được chứng minh là vạn năng, còn Wireworld có thể chứa một máy tính hoàn chỉnh. Vạn năng nghĩa là với mẫu khởi đầu phù hợp, chúng 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 lớp của Wolfram là gì?

Lớp 1 tắt dần thành một trạng thái đồng nhất, lớp 2 ổn định thành các cấu trúc bền vững hoặc lặp lại, lớp 3 vẫn hỗn loạn như Luật 30, và lớp 4 tạo ra các cấu trúc chuyển động, tương tác với nhau như Luật 110.

Vì sao Luật 30 trông ngẫu nhiên?

Mọi bước đều cố định, nhưng mỗi ô trộn ô lân cận bên trái với hai ô còn lại theo cách khiến những khác biệt nhỏ lan ra rất nhanh. Chưa ai tìm thấy mẫu hình đơn giản nào trong cột giữa của nó, vì vậy nó từng được dùng để tạo số ngẫu nhiên.