Đặt vấn đề

Có một ý tưởng hơi ngáo thế này.

Giả sử chúng ta muốn làm một vũ trụ.

Không phải game 3D có núi, biển, rồng phun lửa, NPC đi loanh quanh rồi mắc kẹt vào cái ghế.

Một vũ trụ thật sự.

Nhưng ngân sách hơi thấp.

Ta chỉ có một tờ giấy ô vuông vô hạn.

Mỗi ô chỉ được phép có hai trạng thái:

sống hoặc chết.

Hết.

Không DNA.

Không não.

Không chân.

Không vật lý lượng tử.

Không có một ông thần đứng ngoài màn hình thỉnh thoảng bấm nút cho mọi thứ chạy đúng kịch bản.

Vậy mà nếu chọn luật đủ khéo, những ô vuông ngu ngơ ấy có thể kết thành những cấu trúc đứng yên, những vật thể nhấp nháy, những thứ bò qua không gian, những cỗ máy liên tục bắn ra tín hiệu, và cuối cùng là những hệ thống có khả năng thực hiện phép tính.

Đó là Conway’s Game of Life — Trò chơi Sự sống của nhà toán học John Horton Conway, được giới thiệu rộng rãi năm 1970 qua chuyên mục Mathematical Games của Martin Gardner trên Scientific American. Nó thuộc một nhóm mô hình gọi là cellular automata, hay ô-tô-mát tế bào. (Wikipedia)

Điều buồn cười nhất là:

Đây là một trò chơi không cần người chơi.

Bạn chỉ cần đặt vài ô sống ban đầu.

Sau đó luật tự chạy.

Vũ trụ tự lo phần còn lại.

Một thế giới chỉ có những ô vuông

Hãy tưởng tượng một tờ giấy caro khổng lồ.

Mỗi ô có tám hàng xóm:

1↖  ↑  ↗
2←  X  →
3↙  ↓  ↘

Ô X không biết toàn bộ thế giới đang xảy ra chuyện gì.

Nó không biết có một con glider đang bay qua phía đông.

Nó không biết cách đó 10.000 ô đang có một cỗ máy khổng lồ đang tính số π.

Nó thậm chí không biết mình thuộc về một “sinh vật”.

Nó chỉ làm đúng một việc:

đếm tám hàng xóm quanh mình.

Rồi quyết định sống hay chết.

Đây là điểm rất đẹp của Game of Life.

Không có trung tâm điều khiển.

Không có một hàm kiểu:

1if this_is_a_glider:
2    move_right()

Không một ô nào biết khái niệm “glider” tồn tại.

Glider xuất hiện chỉ vì hàng triệu quyết định cực kỳ ngu ngơ ở cấp độ địa phương vô tình ghép lại thành một hành vi thông minh ở cấp độ lớn hơn.

Nghe quen không?

Một con kiến chẳng hiểu tổ kiến.

Một neuron chẳng hiểu bài thơ.

Một transistor chẳng biết nó đang chạy ChatGPT.

Một phân tử nước chẳng biết thế nào là con sóng.

Nhưng hàng tỷ thứ đơn giản đứng cạnh nhau đôi khi lại sinh ra một thứ mà từng phần riêng lẻ hoàn toàn không hiểu.

Game of Life là một mô hình tí hon để nhìn thẳng vào hiện tượng đó.

Bốn luật của sự sống

Mỗi thế hệ, tất cả các ô được cập nhật đồng thời.

Đây là chi tiết rất quan trọng. Ta không cập nhật ô đầu tiên rồi lấy trạng thái mới của nó để tính ô thứ hai. Mọi ô đều nhìn vào cùng một thế hệ hiện tại, tính tương lai của mình, rồi cả vũ trụ cùng bước sang thế hệ tiếp theo.

Luật chỉ có thế này:

Trong ký hiệu của cellular automata, luật này thường được viết cực kỳ ngắn:

$$ B3/S23 $$

Trong đó B3 nghĩa là một ô chết được born khi có đúng 3 hàng xóm sống, còn S23 nghĩa là một ô đang sống sẽ survive nếu có 2 hoặc 3 hàng xóm sống. (Wikipedia)

Ta cũng có thể viết thành công thức:

$$ s_{t+1}(x,y)= \begin{cases} 1 & n=3
1 & s_t(x,y)=1 \text{ và } n=2
0 & \text{các trường hợp còn lại} \end{cases} $$

Trong đó $n$ là số ô sống xung quanh.

Xong thuật toán.

Quá dễ.

Và đây cũng là lúc mọi chuyện bắt đầu trở nên hơi đáng sợ.

Một hình vuông biết đứng yên

Đặt bốn ô sống thành hình vuông:

1······
2··██··
3··██··
4······

Mỗi ô sống có đúng ba hàng xóm sống.

Không ô chết nào bên ngoài có đúng ba hàng xóm phù hợp để tạo ra thay đổi.

Một thế hệ sau:

1······
2··██··
3··██··
4······

Một triệu thế hệ sau:

1······
2··██··
3··██··
4······

Nó đứng im mãi mãi.

Người ta gọi những cấu trúc như vậy là still life.

Từ bốn quy tắc không hề có câu nào nói:

Nếu gặp hình vuông 2 × 2 thì đóng băng nó.

Nhưng hình vuông vẫn tự tồn tại.

Đây là lần đầu tiên ta thấy một thứ rất quan trọng:

Luật không mô tả vật thể. Luật chỉ mô tả tương tác. Vật thể tự xuất hiện.

Một sinh vật biết thở

Bây giờ đặt ba ô thành một hàng:

1·····
2·███·
3·····

Sau một thế hệ, nó biến thành:

1··█··
2··█··
3··█··

Thêm một thế hệ:

1·····
2·███·
3·····

Nó cứ nằm ngang, đứng dọc, nằm ngang, đứng dọc.

Người ta gọi nó là blinker, một loại oscillator.

Chu kỳ của nó bằng 2.

Ở đây đã xuất hiện một thứ gần giống “thời gian sinh học”.

Không có chiếc đồng hồ nào được lập trình.

Nhưng một cấu trúc tuần hoàn đã tự sinh ra nhịp.

Và rồi có thứ bắt đầu… bò đi

Đây là một cấu hình chỉ gồm năm ô:

1·█·
2··█
3███

Trông chẳng có gì đặc biệt.

Nhưng chạy bốn thế hệ, hình dạng gần như quay trở lại — chỉ khác một chuyện.

Nó đã dịch sang chỗ khác.

Nó di chuyển.

Cấu trúc này được gọi là glider.

Một animation kinh điển của glider cho thấy năm ô sống liên tục chết đi và sinh lại, nhưng toàn bộ pattern dịch chuyển chéo qua lưới. (Wikimedia Commons)

Và đây là lúc Game of Life bắt đầu làm ta hơi đau đầu về triết học.

Bởi vì glider nào đang di chuyển?

Những ô tạo nên glider ở thời điểm trước đã chết.

Những ô mới được sinh ra.

Không có một “mảnh vật chất” nào thật sự chạy từ trái sang phải.

Chỉ có mẫu hình truyền đi.

Giống như một con sóng trên sân vận động.

Người A đứng lên rồi ngồi xuống.

Người B đứng lên rồi ngồi xuống.

Người C tiếp tục.

Không có người nào chạy quanh sân.

Nhưng “con sóng” vẫn chạy.

Vậy con sóng là vật thể?

Hay là thông tin?

Glider cũng vậy.

Nó không phải một nhóm ô cố định.

Nó là một cấu trúc được bảo tồn qua sự thay đổi.

Có một thứ tồn tại, nhưng vật chất tạo nên nó liên tục biến mất.

Nghe hơi giống cơ thể con người.

Vài năm trôi qua, rất nhiều nguyên tử trong người ta đã được thay thế.

Nhưng sáng mai thức dậy chúng ta vẫn bảo:

“Ờ, vẫn là tôi.”

Game of Life vô tình biến một câu hỏi triết học thành năm ô vuông chạy chéo màn hình.

Từ con glider đến một khẩu súng

Nếu glider đã kỳ quặc thì năm 1970, Bill Gosper cùng nhóm của mình còn tìm ra một thứ vui hơn.

Một cấu trúc đứng yên nhưng cứ mỗi chu kỳ lại bắn ra một glider mới.

Nó được gọi là Gosper glider gun.

Glider gun đầu tiên này tạo glider đầu tiên ở thế hệ thứ 15 và sau đó tiếp tục phát ra một glider sau mỗi 30 thế hệ. Phát hiện này cũng chứng minh rằng có những cấu hình hữu hạn có thể tăng trưởng mãi mãi trong Game of Life. (Wikipedia)

Hãy tưởng tượng:

1         glider →
2[   GLIDER GUN   ]  ·   ·   ·   ·   ·   →

Không pin.

Không động cơ.

Không biến while True.

Không đoạn code:

1shoot_glider()

Chỉ có những ô sống và chết tuân theo đúng bốn luật ban đầu.

Một cỗ máy đã xuất hiện trong một thế giới mà luật vật lý chưa từng định nghĩa khái niệm “cỗ máy”.

Đây mới là phần điên nhất: có thể xây máy tính bên trong nó

Glider có thể va chạm.

Hai dòng glider đi vào nhau có thể triệt tiêu, đổi hướng hoặc tạo ra những pattern mới.

Nếu sắp xếp chúng cẩn thận, ta có thể coi:

1có glider     = 1
2không glider  = 0

Bây giờ tín hiệu glider chẳng khác mấy bit điện chạy trong máy tính.

Người ta có thể dùng tương tác giữa các luồng glider để xây dựng những cổng logic như AND, OR và NOT. Từ các thành phần như vậy, Game of Life có thể thực hiện tính toán phổ dụng; nói theo lý thuyết tính toán, nó là Turing complete. (Wikipedia)

Điều này không có nghĩa là cứ rải ngẫu nhiên vài ô rồi Game of Life sẽ tự mở Excel.

Ý nghĩa chính xác hơn là:

Nếu được cung cấp đủ không gian, thời gian và một cấu hình được thiết kế phù hợp, Game of Life có thể mô phỏng một máy tính phổ dụng.

Nói cách khác, bên trong một thế giới chỉ có hai thứ:

10 = chết
21 = sống

ta có thể xây một hệ thống khác có:

1memory
2logic gate
3clock
4program
5data

Thậm chí đã có những máy tính và máy Turing được xây trực tiếp bằng các pattern Game of Life. (Wikipedia)

Đây là trò chơi không có người chơi.

Nhưng bên trong trò chơi không có người chơi ấy, ta có thể xây một máy tính có thể chạy chương trình.

Hơi ngáo.

Tại sao vài luật đơn giản lại sinh ra thứ phức tạp?

Có một trực giác rất dễ mắc phải:

Muốn tạo ra hệ thống phức tạp thì luật phải phức tạp.

Game of Life cho thấy điều đó không nhất thiết đúng.

Luật của nó cực ngắn.

Nhưng trạng thái toàn hệ thống lại chứa rất nhiều thông tin.

Giả sử ta chỉ nhìn một vùng 100 × 100 ô.

Có 10.000 ô.

Mỗi ô có hai trạng thái.

Số cấu hình có thể có là:

$$ 2^{10000} $$

Con số này lớn đến mức gần như vô nghĩa với trực giác con người.

Bốn luật không phức tạp.

Nhưng không gian những thứ mà bốn luật ấy có thể tác động lên là khổng lồ.

Mỗi thế hệ lại biến một cấu hình thành một cấu hình khác.

Và từ những tương tác nhỏ xíu đó, cấu trúc lớn xuất hiện.

Hiện tượng này thường được gọi là emergence — tính nổi lên.

Không có ô nào điều khiển glider.

Không có ô nào ra lệnh cho blinker dao động.

Không có ô nào biết glider gun đang sản xuất tín hiệu.

Toàn bộ hành vi ở tầng trên xuất hiện từ tương tác của các thành phần ở tầng dưới.

Vũ trụ không cần biết mình đang làm gì

Có một điều mình rất thích ở Game of Life.

Khi một glider chạy qua màn hình, không có luật nào nói:

“Glider hãy đi sang Đông Nam.”

Khi glider gun bắn ra glider, không có luật nào nói:

“Đây là một khẩu súng.”

Khi một hệ thống trong Game of Life thực hiện phép tính, không một ô nào biết:

“Chúng ta đang tính toán.”

Luật chỉ biết:

hàng xóm của mày có bao nhiêu đứa còn sống?

Thế thôi.

Điều đó gợi ra một cách nhìn thú vị về thế giới thật.

Một electron không biết nó đang nằm trong CPU.

Một transistor không biết nó đang chạy Linux.

CPU không hiểu dòng chữ mà bạn đang đọc.

Ở tầng thấp, chỉ có những tương tác vật lý.

Nhưng khi số lượng thành phần đủ lớn và cách chúng liên kết đủ đặc biệt, một tầng mô tả hoàn toàn mới xuất hiện:

 1electron
 2↓
 3transistor
 4↓
 5logic gate
 6↓
 7CPU
 8↓
 9machine code
10↓
11operating system
12↓
13browser
14↓
15bài viết này

Không tầng nào nhất thiết “biết” tầng phía trên tồn tại.

Game of Life là phiên bản đồ chơi của ý tưởng đó.

Viết Game of Life bằng Python

Một cách ngây thơ là tạo một ma trận lớn rồi quét từng ô.

Nhưng vì thế giới lý tưởng của Game of Life là vô hạn, cách đó hơi kỳ.

Ta có thể làm đơn giản hơn: chỉ lưu tọa độ của những ô đang sống.

 1from collections import Counter
 2
 3
 4def step(live_cells):
 5    neighbor_count = Counter()
 6
 7    for x, y in live_cells:
 8        for dx in (-1, 0, 1):
 9            for dy in (-1, 0, 1):
10                if dx == 0 and dy == 0:
11                    continue
12
13                neighbor_count[(x + dx, y + dy)] += 1
14
15    next_generation = set()
16
17    for cell, count in neighbor_count.items():
18        if count == 3:
19            next_generation.add(cell)
20        elif count == 2 and cell in live_cells:
21            next_generation.add(cell)
22
23    return next_generation

Ví dụ tạo glider:

 1live = {
 2    (1, 0),
 3    (2, 1),
 4    (0, 2),
 5    (1, 2),
 6    (2, 2),
 7}
 8
 9for _ in range(100):
10    live = step(live)

Hàm step() không biết glider là gì.

Nó cũng không biết oscillator, spaceship hay computer là gì.

Nó chỉ đếm hàng xóm.

Đó chính xác là tinh thần của Game of Life.

Với những pattern cực lớn và chạy qua lượng thế hệ khổng lồ, cách mô phỏng đơn giản này sẽ chậm. Các công cụ chuyên dụng như Golly hỗ trợ những thuật toán hiệu quả hơn, trong đó có Hashlife, để khám phá các cellular automata ở quy mô lớn. (Golly)

Một vũ trụ tất định nhưng không hề nhàm chán

Game of Life hoàn toàn deterministic.

Nếu biết chính xác trạng thái hiện tại, thế hệ tiếp theo được xác định 100%.

Chạy lại cùng cấu hình ban đầu một triệu lần thì kết quả vẫn như nhau.

Không xúc xắc.

Không random.

Không AI.

Nhưng điều thú vị là deterministic không đồng nghĩa với “dễ đoán”.

Một cụm vài ô có thể biến mất ngay.

Một cụm khác đứng im.

Một cụm dao động.

Một cụm bò đi mất.

Một cấu hình nhỏ có thể vùng vẫy qua hàng nghìn thế hệ trước khi ổn định. Chẳng hạn pattern nổi tiếng Acorn, chỉ bắt đầu bằng bảy ô sống nhưng mất 5.206 thế hệ trước khi đi tới trạng thái ổn định cuối cùng. (Wikipedia)

Luật rất đơn giản.

Nhưng kết quả không nhất thiết đơn giản.

Đây là bài học quan trọng khi nghiên cứu các complex systems.

Đôi khi việc biết toàn bộ luật cơ bản vẫn chưa đủ để nhìn một phát rồi đoán được tương lai của hệ thống.

Bạn vẫn phải… chạy nó.

Câu hỏi hơi đáng sợ

Giả sử có một Game of Life khổng lồ.

Khổng lồ đến mức bên trong đó tồn tại một chiếc máy tính.

Trong chiếc máy tính ấy chạy một chương trình mô phỏng Game of Life khác.

Bên trong Game of Life thứ hai lại có một chiếc máy tính.

Rồi nó lại mô phỏng Game of Life.

Ta có:

 1Game of Life
 2    ↓
 3máy tính
 4    ↓
 5Game of Life
 6    ↓
 7máy tính
 8    ↓
 9Game of Life
10    ↓
11...

Tất cả cuối cùng vẫn chỉ là:

ô sống, ô chết, ô sống, ô chết.

Không cần thêm định luật mới.

Chỉ cần tổ chức những thứ cũ theo một cấu trúc đủ đặc biệt.

Đó là một trong những lý do Game of Life hấp dẫn hơn rất nhiều so với vẻ ngoài của nó.

Nó đặt ra một câu hỏi lớn:

Bao nhiêu sự phức tạp của thế giới cần được viết trực tiếp vào luật, và bao nhiêu phần có thể tự nổi lên từ những luật cực kỳ đơn giản?

Game of Life không trả lời câu hỏi đó cho vũ trụ thật.

Nó chỉ cho ta một ví dụ rằng:

một thế giới đơn giản ở tầng đáy hoàn toàn có thể trở nên điên rồ ở tầng trên.

Tổng kết

Game of Life bắt đầu với một tờ giấy ô vuông, hai trạng thái và bốn luật.

Nhưng từ đó xuất hiện still life, oscillator, glider, glider gun, các cổng logic và cuối cùng là khả năng tính toán phổ dụng.

Điều hấp dẫn nhất không phải là vài ô vuông chạy quanh màn hình.

Điều hấp dẫn nằm ở khoảng cách giữa luật và thứ được sinh ra từ luật.

Ở tầng dưới, không có sinh vật.

Không có chuyển động.

Không có máy móc.

Không có chương trình.

Chỉ có những ô đang nhìn tám người hàng xóm của mình rồi quyết định:

“Ờ… chắc lượt này mình sống.”

Vậy mà khi hàng triệu quyết định nhỏ xíu ấy nối vào nhau, một “vũ trụ” bắt đầu xuất hiện.

Có lẽ đôi khi sự phức tạp không cần một bộ luật phức tạp.

Nó chỉ cần rất nhiều thứ đơn giản, đủ thời gian, và một khoảng không rộng đến mức chúng có thể bắt đầu làm những chuyện mà người viết ra luật ban đầu cũng không dễ đoán được.

Cảm ơn các bạn đã quan tâm và theo dõi bài viết, hẹn gặp lại ở các bài viết tiếp theo.

Tham khảo

• Conway’s Game of Life – Wikipedia
• Golly – Game of Life simulator
• Gosper’s Glider Gun animation – Wikimedia Commons