Định lý con khỉ vô hạn

Bách khoa toàn thư mở Wikipedia
Bước tới: menu, tìm kiếm
Giả sử cho một con khỉ gõ liên tục trên một máy đánh chữ hay máy tính, sau một thời gian đủ dài, trong văn bản con khỉ gõ ra ta có thể tìm thấy tất cả các kịch bản của Shakespeare's. Trong hình là một con tinh tinh và máy đánh chữ.

Định lý con khỉ vô hạn nói rằng nếu cho một con khỉ gõ lên một bàn phím trong một thời gian vô hạn, một phần văn bản khỉ gõ ra gần như chắc chắn sẽ có nghĩa, ví dụ tất cả các tác phẩm của William Shakespeare.

Trong bài này, "gần như chắc chắn" là thuật ngữ toán học có nghĩa rõ ràng, và "con khỉ" là một ẩn dụ về một thiết bị trừu tượng có thể tạo ra chuỗi ngẫu nhiên ký tự và ký hiệu dài vô tận. Xác suất con khỉ gõ ra các tác phẩm của Shakespeare như Hamlet trong thời gian bằng tuổi vũ trụ thực ra rất nhỏ, nhưng vẫn khác không.

Các biến thể của định lý bao gồm nhiều con khỉ gõ vô hạn, và văn bản mục tiêu thay đổi từ một mục từ điển đến một câu đơn. Lịch sử của nguyên lý bắt nguồn từ xa xưa, trong tác phẩm Luận về sinh diệt của Aristotle, Về bản tính thần minh của Cicero, các quan điểm của Blaise PascalJonathan Swift, cho đến phiên bản hiện đại với máy đánh chữ. Trong những năm đầu thế kỷ 20, Émile BorelArthur Eddington sử dụng nguyên lý để minh họa cho thang thời gian ẩn giấu trong cơ sở của cơ học thống kê.

Lời giải[sửa | sửa mã nguồn]

Chứng minh trực tiếp[sửa | sửa mã nguồn]

Có một chứng minh dễ hiểu cho định lý: Nếu hai sự kiện không phụ thuộc trạng thái, xác suất hai sự kiện cùng xảy ra là tích xác suất mỗi sự kiện. Ví dụ, khả năng mưa ở Hà Nội trong một ngày cụ thể là 0.3, khả năng có động đất ở Sài Gòn trong cùng ngày là 0.008, vậy xác suất hai sự kiện cùng xảy ra trong ngày đó là  0.3 × 0.008 = 0.0024.

Cho một máy đánh chữ có 50 phím, và từ cần gõ là banana. Giả sử các phím được gõ ngẫu nhiên (xác xuất được gõ của các phím bằng nhau) và không phụ thuộc vào nhau, xác suất ký tự đầu tiên là 'b' là 1/50, xác suất ký tự thứ hai là 'a' là 1/50... vì các sự kiện không phụ thuộc lẫn nhau. Từ đó, xác suất sáu ký tự đầu tiên khớp với banana là :(1/50) × (1/50) × (1/50) × (1/50) × (1/50) × (1/50) = (1/50)6 = 1/15 625 000 000 , nhỏ hơn một phần mười lăm tỉ.

Tương tự, xác suất 6 ký tự tiếp theo khớp với banana cũng là (1/50)6, và 6 ký tự tiếp sau đó....

Từ đó, xác suất không gõ ra từ banana trong một khối 6 ký tự là 1 − (1/50)6. Vì mỗi khối được gõ không phụ thuộc lẫn nhau, xác suất Xn để không gõ ra từ banana trong n khối 6 ký tự là:

X_n=\left(1-\frac{1}{50^6}\right)^n.

Khi n tăng, Xn giảm. Với n bằng một triệu, Xn khoảng 0.9999, nhưng với n bằng mười tỉ Xn chỉ còn khoảng 0.53, và với n là 100 tỉ con số đó là 0.0017. Khi n tiến tới vô cực, Xn tiến tới không; nghĩa là bằng cách cho n đủ lớn, ta có thể có Xn nhỏ như mong muốn,[1] và khi đó xác suất có một khối "banana" trong chuỗi gõ ra tiến tới 1. Hơn nữa vì từ có thể xuất hiện giữa hai khối, khả năng xuất hiện từ banana còn lớn hơn tính toán trên.

Lập luận tương tự chỉ ra tại sao có ít nhất một trong số các con khỉ vô hạn sẽ gõ ra từ cần thiết bằng với tốc độ của một người đánh máy bình thường. trong trường hợp này Xn = (1 − (1/50)6)n khi Xn biểu diễn xác suất n con khỉ đầu tiên không gõ đúng banana trong 6 ký tự đầu tiên. Khi xét 100 tỉ con khỉ, xác suất này là 0.17%, và khi số khỉ tăng lên, xác xuất này tiến về không.

Dù sao, nếu cho một số khỉ có nghĩa thực hiện gõ trong một khoảng thời gian có nghĩa, kết quả là ngược lại: Nếu có đủ nhiều khỉ và chúng gõ trong vũ trụ quan sát được (1080), và mỗi con khỉ gõ 1,000 ký tự trong một giây, liên tục gõ trong thời gian bằng 100 lần tuổi vũ trụ (1020 seconds), xác suất bọn khỉ tái tạo lại một tác phẩm văn học ngắn là gần bằng không.

Chuỗi vô hạn[sửa | sửa mã nguồn]

Xác suất[sửa | sửa mã nguồn]

Gần như chắc chắn[sửa | sửa mã nguồn]

Lịch sử[sửa | sửa mã nguồn]

Applications and criticisms[sửa | sửa mã nguồn]

Trong văn hóa đại chúng[sửa | sửa mã nguồn]

Chú thích[sửa | sửa mã nguồn]

Tham khảo[sửa | sửa mã nguồn]

  1. ^ Isaac, Richard E. (1995). The Pleasures of Probability. Springer. tr. 48–50. ISBN 0-387-94415-X.  Isaac generalizes this argument immediately to variable text and alphabet size; the common main conclusion is on p.50.

Liên kết ngoài[sửa | sửa mã nguồn]