Automata tế bào là gì
Automata tế bào là một bàn cờ gồm các ô, mỗi ô ở một trạng thái (ở đây là sống hoặc chết), thay đổi theo từng bước gọi là thế hệ. Ở mỗi bước, tất cả các ô được cập nhật cùng lúc theo cùng một luật, và luật đó chỉ nhìn vào tám ô lân cận bao quanh mỗi ô.
Trò chơi cuộc sống không có thắng hay thua: bạn chọn vị trí ban đầu và các luật lo phần còn lại. Điều thú vị là từ những luật đơn giản như vậy xuất hiện hành vi rất phức tạp và khó đoán, vì thế nó được nghiên cứu trong toán học, tin học và cả sinh học.
Các luật, nói đơn giản
Người ta đếm số tế bào sống lân cận của mỗi ô (tám ô xung quanh, kể cả đường chéo) và áp dụng các luật sau đồng thời trên toàn bàn:
- Một tế bào sống có ít hơn hai tế bào sống lân cận sẽ chết vì cô độc.
- Một tế bào sống có hai hoặc ba tế bào sống lân cận tiếp tục sống.
- Một tế bào sống có nhiều hơn ba tế bào sống lân cận sẽ chết vì quá đông.
- Một ô chết có đúng ba tế bào sống lân cận sẽ sinh ra tế bào.
Ký hiệu viết tắt của các luật này là B3/S23: B (birth, sự sinh ra) 3 nghĩa là sinh ra khi có 3 tế bào lân cận, còn S (survival, sự sống sót) 23 nghĩa là sống sót khi có 2 hoặc 3. Các luật thay thế trong công cụ dùng cùng ký hiệu, ví dụ HighLife là B36/S23 và Hạt giống là B2/S.
Tính một thế hệ bằng tay
Lấy đèn nháy: ba tế bào sống xếp thành hàng ngang. Tế bào ở giữa có 2 tế bào sống lân cận nên sống sót. Hai tế bào ở hai đầu chỉ có 1 tế bào lân cận nên chết. Các ô ngay trên và ngay dưới tế bào giữa có 3 tế bào sống lân cận (ba tế bào của hàng) nên được sinh ra. Kết quả: một hàng dọc gồm ba tế bào.
Ở thế hệ kế tiếp, quá trình lặp lại và hàng trở lại nằm ngang. Vì vậy đèn nháy là một vật dao động chu kỳ 2. Hãy thử tương tự với khối vuông, hình vuông 2 × 2: mỗi tế bào có 3 tế bào lân cận nên tất cả đều sống sót, và không ô trống nào có 3 tế bào sống lân cận. Nó không bao giờ thay đổi, nên được gọi là hình tĩnh (still life).
Lịch sử: Conway, Gardner và tạp chí
Nhà toán học người Anh John Conway nghĩ ra trò chơi này vào năm 1970. Martin Gardner phổ biến nó trong chuyên mục trò chơi toán học của Scientific American, số tháng 10 năm 1970, và từ đó nó tạo ra một cộng đồng người đam mê khổng lồ chuyên tìm và lập danh mục các mẫu hình.
Theo thời gian, người ta đã chứng minh trò chơi này là Turing đầy đủ: với những hình phù hợp, về nguyên tắc nó có thể tính bất cứ thứ gì mà một máy tính tính được. Đó là một trong những lý do nó vẫn nổi tiếng: độ phức tạp vô hạn từ những luật tối giản.
Các họ mẫu hình và những mẫu nên thử
Các mẫu hình được phân loại theo hành vi. Tất cả đều có trong menu «Mẫu hình» của công cụ với những tên sau:
| Họ | Mẫu hình | Hành vi |
|---|---|---|
| Hình tĩnh | Khối vuông, Tổ ong | Không bao giờ thay đổi: khối vuông 4 tế bào, tổ ong 6 tế bào |
| Dao động | Đèn nháy, Con cóc, Đèn hiệu | Chu kỳ 2: bắt đầu lại sau mỗi 2 thế hệ |
| Dao động | Pulsar | Chu kỳ 3, 48 tế bào ở pha đầu |
| Dao động | Pentadecathlon | Chu kỳ 15 |
| Tàu | Tàu lượn (glider) | 5 tế bào; tiến 1 ô theo đường chéo sau mỗi 4 thế hệ |
| Tàu | Tàu vũ trụ nhẹ | Đi ngang qua bàn theo đường thẳng, chu kỳ 4 |
| Súng | Súng tàu lượn Gosper | Bắn ra một tàu lượn mới sau mỗi 30 thế hệ |
| Hỗn loạn ban đầu | R-pentomino | 5 tế bào cần 1.103 thế hệ để ổn định trên mặt phẳng vô hạn |
Súng Gosper do Bill Gosper tìm ra năm 1970 và là bằng chứng đầu tiên cho thấy một quần thể có thể tăng trưởng không giới hạn. Ngoài những mẫu này, công cụ còn có Quả sồi và Diehard, hai mẫu hình nhỏ cần rất lâu mới ổn định.
Cách dùng công cụ Trò chơi cuộc sống
- Chạm hoặc kéo trên bàn để vẽ tế bào sống (chạm lại vào ô đang sống để xóa), hoặc chọn một mẫu hình từ menu «Mẫu hình».
- Nhấn «Bắt đầu». Với «Một thế hệ», bạn đi từng bước để theo dõi quá trình tiến hóa thong thả, còn «Tạm dừng» sẽ dừng mọi thứ. Bạn cũng có thể dùng bàn phím khi đã chọn bàn: phím cách để bắt đầu hoặc tạm dừng, N để sang một bước, R để điền ngẫu nhiên và C để xóa hết.
- Chỉnh «Tốc độ», «Kích thước bàn» và «Luật», và thử «Ngẫu nhiên» (cùng «Mật độ ngẫu nhiên») để bắt đầu với một bàn đầy tế bào. «Xóa hết» sẽ làm bàn trống.
- Bật «Tô màu theo tuổi của từng tế bào» để xem vùng nào ổn định lâu hơn. Phía trên hiển thị thế hệ và số tế bào sống, và công cụ sẽ báo khi bàn đã ổn định, rơi vào một chu kỳ hoặc không còn sự sống.
Mọi thứ được tính trên thiết bị của bạn và không có gì được gửi đến máy chủ. Công cụ lưu trong trình duyệt của bạn các thiết lập (kích thước, tốc độ, luật), nhưng không lưu hình bạn vẽ.
Những thí nghiệm nên làm
- Nạp tàu lượn và đếm xem cần bao nhiêu thế hệ để nó dịch một ô theo đường chéo: là 4. Khi các mép bàn được nối, nó đi hết một vòng bàn và xuất hiện lại ở phía bên kia.
- Đặt hai tàu lượn trên quỹ đạo va chạm nhau và xem kết thúc ra sao: tùy cách chúng đến, chúng có thể phá hủy nhau hoặc để lại một hình tĩnh.
- Nạp súng Gosper trên bàn ít nhất 48 × 48 và đếm xem mất bao lâu để bắn ra mỗi tàu lượn: 30 thế hệ.
- Nạp R-pentomino trên bàn lớn và so sánh khi có và không nối mép. Trên mặt phẳng vô hạn nó cần 1.103 thế hệ để ổn định, nhưng trên bàn hữu hạn kết quả thay đổi.
- Đổi luật với cùng một hình vẽ. Với Hạt giống (B2/S), mọi tế bào đều chết ở mỗi thế hệ và chỉ còn các tế bào mới sinh, nên hình lan ra ngoài; với Mê cung (B3/S12345), xuất hiện các cấu trúc giống hành lang.
Giới hạn của bàn hữu hạn
Trò chơi gốc diễn ra trên mặt phẳng vô hạn. Bàn của công cụ có kích thước cố định, nên thứ gì chạm tới mép sẽ có hành vi khác: khi nối các mép, nó đi vào lại từ phía đối diện (bàn trở thành một dạng chiếc bánh vòng), còn khi không nối, nó tắt đi khi va vào tường.
Vì vậy các mẫu hình lớn cần chỗ rộng (súng Gosper cần ít nhất 48 × 48) và một số mẫu, như R-pentomino, có thể kết thúc khác với những gì bạn thấy trên mặt phẳng vô hạn. Nếu mẫu hình không vừa, công cụ sẽ yêu cầu bạn chọn bàn lớn hơn.
Câu hỏi thường gặp
Luật của Trò chơi cuộc sống của Conway là gì?
Một tế bào sống có 2 hoặc 3 tế bào sống lân cận thì tiếp tục sống; ít hơn 2 thì chết vì cô độc và nhiều hơn 3 thì chết vì quá đông. Một ô chết có đúng 3 tế bào sống lân cận sẽ sinh ra tế bào. Viết tắt là B3/S23.
B3/S23 nghĩa là gì?
B là sự sinh ra (birth) và S là sự sống sót (survival). B3 nghĩa là một tế bào được sinh ra khi có 3 tế bào sống lân cận và S23 nghĩa là tế bào có 2 hoặc 3 tế bào lân cận sẽ sống sót.
Tàu lượn (glider) là gì?
Là hình gồm năm tế bào di chuyển theo đường chéo, mỗi 4 thế hệ tiến một ô. Đây là mẫu hình nổi tiếng nhất của trò chơi.
Ai đã phát minh ra Trò chơi cuộc sống?
Nhà toán học người Anh John Conway, năm 1970. Martin Gardner đã giới thiệu nó trên tạp chí Scientific American cùng năm đó.
Vì sao hình vẽ của tôi biến mất hoặc đứng yên?
Đó là chuyện phổ biến nhất: nhiều hình nhỏ tắt hẳn hoặc ổn định chỉ sau vài thế hệ. Hãy thử một điểm xuất phát khác, một bàn lớn hơn hoặc «Ngẫu nhiên».