Trò chơi cuộc đời

Hà Dương TườngSài Gòn tiếp thị
03:35' CH - Chủ nhật, 14/09/2014

“Martin đã biến hàng ngàn đứa trẻ thành những nhà toán học và hàng ngàn nhà toán học thành những đứa trẻ”. Ronald Graham, nhà toán học nổi tiếng tại đại học California ở San Diego đã đánh giá như thế về Martin Gardner, người vừa qua đời ngày 22.5.2010, ở tuổi 96.

Martin Gardner, người thầy ham chơi

Nửa đầu của câu nói là một sự vinh danh khó có thể cao quý hơn đối với một người thầy xuất chúng đã truyền được ngọn lửa say mê khoa học của mình tới các thế hệ học trò. Nửa sau đẹp không kém. Mấy ai có thể tự hào đã biết trả lại tuổi trẻ cho những nhà nghiên cứu đạo mạo!

Thế mà, Martin Gardner chẳng hề bước lên bục giảng, cũng không phải là một nhà nghiên cứu toán học. Ra trường với một tấm bằng cử nhân triết, ông say mê với những trò ảo thuật, và kiếm sống với những tờ báo dành cho thiếu niên. Nhưng cũng chính những say mê ấy đã khiến ông – khá tình cờ - nhận được lời mời mở ra một tiết mục mới trên tờ báo phổ biến khoa học cao cấp ở Mỹ, tờ Scientific American.

Trong một phần tư thế kỷ (1956-1980), dưới đề mục chung Các trò chơi toán, ông đã làm say mê nhiều thế hệ bạn đọc của tờ báo với các bài viết về các trò chơi trí tuệ này. Vừa dễ hiểu, vừa đi sâu vào nhiều khía cạnh mà chúng gợi mở ra. Không phải là những trò chơi do ông sáng tạo, mà phần lớn là những gì ông tìm thấy trên sách vở, suy nghĩ cách trình bày lại, trao đổi với các nhà khoa học chuyên nghiệp (không chỉ là toán học mà cả vật lý, hoá, sinh học) để nắm bắt được những ý tưởng của họ về các vấn đề mà trò chơi gợi ra. Rất nhiều nhà khoa học nổi tiếng (Penrose, Conway, Graham, Hofstadter…) đã trở thành bạn ông qua các trao đổi đó.

Martin Gardner còn là một tác giả của hơn 50 cuốn sách, về các trò chơi, trò ảo thuật hay về triết học, là chuyên gia hàng đầu ở Mỹ về Lewis Carroll – tác giả của Alice lạc vào thế giới thần tiên... Để tưởng nhớ ông, bài này xin giới thiệu một “trò chơi” do nhà toán học người Anh John Horton Conway phát minh và được Martin Gardner phổ biến lần đầu trên tạp chí Scientific American, số 233, tháng 10.1970.

Trò chơi cuộc đời

Tên tiếng Anh là Game of Life. Hãy ví cuộc đời như một trang giấy trắng kẻ ô, dài, rộng vô tận. Mỗi ô như một không gian sinh tồn, có tám hàng xóm (đông, tây, nam, bắc, đông bắc, đông nam, tây nam, tây bắc), trong đó có thể sống một cá thể sinh vật (một tế bào, xin trở lại thuật ngữ này dưới đây). Ban đầu, trên trang giấy – cuộc đời đó, sẽ là một nhóm sinh vật thế hệ 0, có thể được biểu hiện bằng những ô bôi đen, các ô còn lại để trống. Thế hệ khởi đầu đó có bao nhiêu cá thể, phân phối theo hình thái nào, là tuỳ bạn – người chơi. Nhưng quyền năng sáng thế của bạn chỉ thế thôi, vì các biến chuyển tiếp theo của cuộc đời sẽ tuân theo những quy luật đã được định trước, như sau:

1. Một sinh vật sẽ tiếp tục sống (có mặt ở thế hệ sau) nếu nó tiếp xúc với hai hoặc ba sinh vật khác (“tiếp xúc” trong nghĩa hai bên là hàng xóm của nhau);

2. Ngược lại, nếu nó có từ bốn hàng xóm trở lên hoặc ít hơn hai hàng xóm, nó sẽ chết đi, vì ngột ngạt, hay vì cô đơn, và sẽ không còn ở thế hệ sau;

3. Từ mỗi ô trống, nếu có đúng 3 (không hơn, không kém) hàng xóm sống, sẽ sinh ra một sinh vật cho thế hệ sau.

Như vậy, nếu thế hệ đầu, hay thế hệ n nào đó, nếu chỉ có một hoặc hai sinh vật, cuộc chơi sẽ chấm dứt vì thế hệ tiếp nối không còn nữa (ông Conway này dù là người Âu nhưng hình như không đọc Kinh Thánh thì phải, quên cả chuyện ông A-đam và bà E-và!). Vai trò của người chơi là tạo ra nhóm sinh vật ban đầu, xem nó biến chuyển như thế nào từ thế hệ này sang thế hệ khác, và tìm cách trả lời những câu hỏi nó đặt ra. Nó sẽ chết đi hay sống mãi, sẽ lớn lên vô tận hay ngừng lại một lúc nào đó.

Bạn hãy thử với các nhóm ban đầu này nhé:

Hãy phân tích cẩn thận để xem các thế hệ kế tiếp A1, A2, B1, B2, C1, C2… là như thế nào. Bạn có thể chơi với một trang giấy kẻ ô, bút chì và một cái tẩy. Hoặc tốt hơn, dùng một bàn cờ vây với quân của nó. Trước khi tìm cách chơi trên máy tính.

Đi tìm “vườn địa đàng”

Từ bài báo đầu tiên của M. Gardner, số người chơi và số bài báo viết về “trò chơi cuộc đời” đã bùng nổ dữ dội. Nếu gõ “game of life” trên Google, bạn sẽ thấy 272 triệu trang (con số ngày 31.5.2010). Có nguyên một phụ trang của từ điển mạng Wikipedia dành riêng cho trò chơi này. Một trang khác cho những thông tin cập nhật về trò chơi và nhiều trang Youtube cho thấy biến chuyển rất phức tạp và đẹp mắt của những hình thái ban đầu khá đơn giản. Và tất nhiên, cũng trên mạng, bạn có thể tìm thấy nhiều chương trình (bằng JavaScript, C, Basic…) để chơi, nếu bạn không thể tự mình viết ra một chương trình như thế.

Rất nhiều bài toán có thể đặt ra, có những câu hỏi chưa có lời giải. Trong bài báo đã dẫn, Martin Gardner đưa ra một thách đố của Conway: chứng minh là có hay không có một hình thái ban đầu nào lớn lên vô tận, kèm theo tiền thưởng 50 USD (của năm 1970). Ngay cuối năm đó, Bill Gosper, một nhà toán học ở MIT (viện Công nghệ Massachusetts) đã đoạt giải, với một phân phối theo hình tàu lượn (tiếng Anh: glider) được chứng minh là sẽ sinh trưởng vô tận.

Tìm những hình thái tuần hoàn (với chu kỳ p nếu thế hệ p trở lại giống in như thế hệ 0, trước đó thì không) là một bài toán hấp dẫn nhiều người. Trên trang đã dẫn, có khoảng vài chục hình thái tuần hoàn như vậy.

Một “vườn địa đàng” là một hình thái không thể đạt tới được (không có hình thái ban đầu nào dẫn tới nó, đúng là ông Conway không tin ở Kinh Thánh!). Năm 1971, R. Banks công bố một “vườn địa đàng” có kích thước 9x33, với 226 cá thể – dùng lý thuyết tổ hợp để chứng minh. Năm 2009, N. Beluchenko đưa ra một “vườn địa đàng” với 69 sinh vật sống trong một trang 11x11 ô, và cho tới nay là “vườn địa đàng” nhỏ nhất được biết tới.

Ôtômat tế bào

Với những quy luật đơn giản, trò chơi cuộc đời có những phát triển bất ngờ. Trong tin học lý thuyết, người ta đã chứng minh được đây là một “máy Turing vạn năng”: mọi thuật toán máy tính đều có thể được mô tả bằng trò chơi này, tất nhiên là với một hình thái ban đầu đủ lớn và phức tạp. Nhưng ứng dụng chính của nó - cũng là khởi nguồn của những tìm tòi dẫn Conway đến những quy luật của trò chơi – là một công cụ mô phỏng những hệ thống tự sinh sản (có khả năng tạo ra một bản sao của chính nó, như các tế bào sinh học), một “ôtômat tế bào” (tiếng Anh: cellular automata). Chính vì thế mà các cá thể sống trong trò chơi cuộc đời của Conway cũng thường được gọi là những “tế bào”. Trò chơi của Conway chính là một “ôtômat tế bào” thông dụng nhất được sử dụng để nghiên cứu những hệ thống phức tạp.

Trò chơi cuộc đời
 
ChúngTa.com @ Facebook
 
Thống kê truy cập
Số lượt truy cập: .
Tổng số người truy cập: .
Số người đang trực tuyến: .
.
Sponsor links (Provided by VIEPortal.net - The web cloud services for enterprises)
Thiết kế web, Thiết kế website, Thiết kế website công ty, Dịch vụ thiết kế website, Dịch vụ thiết kế web tối ưu, Giải pháp portal cổng thông tin, Xây dựng website doanh nghiệp, Dịch vụ web bán hàng trực tuyến, Giải pháp thương mại điện tử, Phần mềm dịch vụ web, Phần mềm quản trị tác nghiệp nội bộ công ty,