🔬

cellular-automata

🔬 Thử ngay

Đây là gì?

🎯 Mẹo sử dụng

📚 Thuật ngữ

Cellular Automaton
Một mô hình tính toán rời rạc bao gồm một lưới các ô thông thường, mỗi ô thuộc một số hữu hạn trạng thái, phát triển qua các bước thời gian riêng biệt theo các quy tắc dựa trên các trạng thái ô lân cận.
Moore Neighborhood
Tám ô bao quanh một ô trung tâm trong lưới 2D (bao gồm cả các đường chéo), được đặt theo tên của Edward F. Moore, người đã chứng minh định lý Vườn Địa Đàng vào năm 1962.
Von Neumann Neighborhood
Bốn ô liền kề trực giao (trên, dưới, trái, phải) bao quanh một ô trung tâm, được đặt tên theo thiết kế ô tô tự động ban đầu của John von Neumann.
Game of Life
Một máy tự động di động hai chiều do John Conway tạo ra vào năm 1970 với các quy tắc sinh/sống/tử đơn giản có thể tạo ra hành vi mới xuất hiện phức tạp, được chứng minh là Turing-complete.
Glider
Một mẫu nhỏ trong Trò chơi cuộc sống của Conway tự chuyển dịch trên lưới theo chu kỳ 4 bước, một trong những cấu trúc mang tính biểu tượng nhất trong máy tự động di động.
Elementary Cellular Automaton
CA một chiều có hai trạng thái và các quy tắc lân cận gần nhất, được Stephen Wolfram phân loại một cách có hệ thống thành 256 quy tắc (Quy tắc 0 đến Quy tắc 255).
Rule 110
Một máy tự động di động cơ bản đã được Matthew Cook chứng minh là Turing-complete vào năm 2004, chứng minh rằng ngay cả CA đơn giản nhất cũng có thể thực hiện bất kỳ tính toán nào.
Rule 30
Một CA cơ bản được Wolfram phát hiện, tạo ra hành vi ngẫu nhiên rõ ràng từ một ô ban đầu duy nhất, được sử dụng trong trình tạo số ngẫu nhiên của Mathematica.
Wolfram Classes
Phân loại bốn lớp của Stephen Wolfram về hành vi của automata tế bào: Lớp 1 (đồng nhất), Lớp 2 (định kỳ), Lớp 3 (hỗn loạn), Lớp 4 (phức tạp/cạnh hỗn loạn).
Garden of Eden
Một cấu hình trong máy tự động di động chỉ có thể xuất hiện dưới dạng điều kiện ban đầu và không thể đạt được từ bất kỳ trạng thái nào khác, được chứng minh là tồn tại bởi Moore (1962) và Myhill (1963).
Self-Replication
Khả năng một mẫu trong CA tạo ra các bản sao của chính nó, động lực ban đầu cho công việc của von Neumann, lấy cảm hứng từ quá trình tái tạo tế bào sinh học.
Totalistic Rule
Quy tắc CA trong đó trạng thái tiếp theo của ô chỉ phụ thuộc vào tổng (hoặc trung bình) giá trị của các ô trong vùng lân cận của nó, đơn giản hóa không gian quy tắc.
Langton's Ant
Một máy tự động di động 2D đơn giản trong đó một 'con kiến' di chuyển trên một lưới, lật các màu của ô, tạo ra hành vi hỗn loạn ban đầu mà cuối cùng tạo thành một mô hình đường cao tốc.
Reversible CA
Một máy tự động di động trong đó mọi cấu hình đều có một thiết bị tiền thân duy nhất, được nghiên cứu bởi Tommaso Toffoli (1977) để mô hình hóa các định luật vật lý tuân theo tính đối xứng nghịch đảo thời gian.
Lattice Gas Automaton
Một mô hình dựa trên CA để mô phỏng động lực học chất lỏng, trong đó các hạt di chuyển và va chạm trên lưới mắt cáo, được tiên phong vào những năm 1980.
Wireworld
Một máy tự động di động được Brian Silverman thiết kế vào năm 1987 để mô phỏng các mạch logic điện tử, sử dụng bốn trạng thái để mô hình hóa việc truyền tín hiệu.
Hashlife
Một thuật toán do Bill Gosper phát minh để tính toán cực nhanh các mẫu Sự sống bằng cách khai thác tính chất lặp đi lặp lại của quá trình tiến hóa CA thông qua quá trình ghi nhớ.
Spaceship
Bất kỳ mẫu nào trong CA tự dịch qua lưới trong khi vẫn duy trì cấu trúc của nó, khái quát hóa khái niệm về tàu lượn.
Oscillator
Một mẫu trong CA quay trở lại trạng thái ban đầu sau một số bước thời gian cố định, xoay vòng giữa một tập hợp cấu hình hữu hạn.
Still Life
Một mô hình trong CA không thay đổi từ thế hệ này sang thế hệ tiếp theo, thể hiện trạng thái cân bằng ổn định.

🏆 Nhân vật chính

John von Neumann (1948-1952)

Tạo ra máy tự động di động đầu tiên (29 trạng thái) để mô hình hóa quá trình tự sinh sản, thiết lập nền tảng lý thuyết cho toàn bộ lĩnh vực

Stanislaw Ulam (1951)

Đề xuất cách tiếp cận rời rạc dựa trên tế bào cho von Neumann, truyền cảm hứng cho sự chuyển đổi từ mô hình liên tục sang mô hình rời rạc

John Conway (1970)

Phát minh ra Trò chơi cuộc sống (1970), máy tự động di động nổi tiếng nhất, được chứng minh là một máy tính phổ quát có khả năng tính toán bất kỳ

Martin Gardner (1970)

Phổ biến Trò chơi cuộc sống của Conway thông qua chuyên mục Trò chơi toán học của ông trên tạp chí Scientific American, thu hút sự quan tâm trên toàn thế giới

Stephen Wolfram (1983-2002)

Phân loại một cách có hệ thống tất cả 256 quy tắc CA cơ bản thành bốn lớp hành vi, được tác giả là 'A New Kind of Science' (2002)

Matthew Cook (2004)

Quy tắc 110 đã được chứng minh là Turing-complete, thể hiện khả năng tính toán phổ quát trong khung CA đơn giản nhất có thể

Tommaso Toffoli (1977)

Tiên phong về máy tự động di động có thể đảo ngược (1977) để mô hình hóa các định luật vật lý, đồng phát triển máy tự động di động CAM-6

Edward Fredkin (1980s)

Đề xuất rằng bản thân vũ trụ có thể là một máy tự động di động (vật lý kỹ thuật số), đưa ra quy tắc Chẵn lẻ và chỉ đạo nghiên cứu CA tại MIT

Christopher Langton (1984)

Đã tạo ra Langton's Loop (1984), một CA tự tái tạo đơn giản và đặt ra thuật ngữ 'cuộc sống nhân tạo' để mô tả các mô phỏng cuộc sống dựa trên CA

Arthur Burks (1966)

Biên tập và xuất bản 'Lý thuyết về máy tự động tái tạo' của von Neumann (1966), bảo tồn công trình nền tảng cho các thế hệ tương lai

🎓 Tài nguyên học tập

💬 Lời nhắn cho người học

Máy tự động di động dạy chúng ta một trong những bài học sâu sắc nhất về khoa học: các quy tắc đơn giản có thể tạo ra sự phức tạp vô hạn. Từ giấc mơ về máy móc tự tái tạo của von Neumann đến tầm nhìn của Wolfram về một loại hình khoa học mới, CA cho thấy rằng bạn không cần những hướng dẫn phức tạp để xây dựng một thế giới phức tạp. Mỗi khi bạn quan sát một chiếc tàu lượn lướt qua lưới Trò chơi Cuộc sống, bạn đang chứng kiến ​​sự xuất hiện -- nguyên tắc tương tự biến các phản ứng hóa học đơn giản thành tế bào sống và các kết nối thần kinh đơn giản thành ý thức. Bắt đầu với những quy tắc đơn giản nhất, quan sát những gì xảy ra và chuẩn bị ngạc nhiên.

Bắt đầu

Miễn phí, không cần đăng ký

Bắt đầu →