무한 원숭이 정리

무한 원숭이 정리는 무한성에 기초한 정리로, 타자기 앞에 앉아서 마음대로 쳐대는 원숭이가 프랑스 국립 박물관의 모든 책을 언젠가는 쳐 낼 가능성이 거의 확실하다는 정리이다. ‘거의 확실하다(almost surely)’라는 말은 수학적으로 확률의 극한값이 1이라는 것을 의미한다. 위의 정리는 영어 사용자들이 윌리엄 셰익스피어의 희곡 전체를 칠 수도 있다는 내용으로 각색하였다.

보렐-칸텔리 보조정리의 두 번째 정리에 따르면, 충분한 시간만 주어진다면, 제멋대로 타자를 치는 침팬지는 필연적으로 윌리엄 셰익스피어의 희곡 전체를 칠 것이다.

이를 처음으로 생각한 사람은 프랑스 수학자 에밀 보렐(Émile Borel)로, 1913년 논문인 〈Mécanique Statistique et Irréversibilité〉에 실렸다. 여기서 ‘원숭이’란 실제의 원숭이를 뜻하는 것은 아니다. 대신, 아주 긴 임의의 문자로 이루어진 문자열을 만들어 내는 방식을 좀 더 상상하기 쉽도록 만들어 주는 도구이다. 보렐은 백만 마리의 원숭이가 매일 10시간씩 타자를 친다고 해서, 거대한 도서관에 있는 모든 책을 정확히 만들어 낼 수 있을 것 같지는 않다고 언급했다. 하지만 그렇다고 해서, 이른바 ‘확률’이라는 법칙이 깨어지지는 않으리라고 반론하였다(즉 발생할 수도 있다는 것이다.). 보렐이 원숭이라는 것을 언급한 이유는 극히 일어나기 힘든 사건을 상상하게 하기 위한 도구였다.

1970년 이후로, 위의 설명 대신 무한이라는 개념을 혼용한 설명이 사용되었다. 즉 무한 원숭이가 무한 시간 타자를 친다면 주어진 문서를 쳐 낸다는 것이다. 하지만, 원숭이 수와 시간의 두 개 모두 무한을 가정하는 것은 별 효용성이 없다. 불사의 한 원숭이가 무한히 타자를 친다면 언젠가는 주어진 문서를 만들 수 있을 것이며, 또한 무한한 수의 원숭이가 단 한 번씩만 타자를 친다면, 그 순간 모든 문서가 만들어질 것이기 때문이다. 사실 더 엄밀히 말한다면, 두 경우 모두 모든 종류의 문서가 만들어질 가능성이 ‘거의 확실하다’고 하는 것이 옳다(무한 원숭이가 모두 똑같은 문자만 누른다면, 결과는 한 문자로만 이루어진 문자열일 것이기 때문이다).

오늘날에는 문학, 텔레비전, 라디오, 음악, 인터넷 등에서 타자를 치는 원숭이에게 대한 관심이 증대되고 있다. 2003년에는 술라웨시 머카크에 대한 실험이 이루어졌지만, 결과는 알파벳 'S'가 대부분인 5장의 종이였다.

현재 진화론을 설명하는 근거로 인용되기도 한다.

직접 증명

이에 대한 간단한 증명이 존재한다. 2가지의 사건이 확률적으로 독립이라면(두 가지 사건은 서로의 결과에 영향을 주지 않는다) 두 가지 사건이 동시에 일어나는 확률은 두가지 확률의 곱과 같다.

타자기가 50가지 키가 있다고 하고 입력되어야 하는 단어는 Banana라고 할 때 b를 칠 확률은 $\textstyle {\frac {1}{50}}$이며, 2번째에 a를 칠 확률은 역시 $\textstyle {\frac {1}{50}}$이고, 나머지 다른 문자들도 이와 같다. 따라서 banana라는 단어를 입력할 확률은 $\textstyle {\frac {1}{50}}\times {\frac {1}{50}}\times {\frac {1}{50}}\times {\frac {1}{50}}\times {\frac {1}{50}}\times {\frac {1}{50}}={\frac {1}{50^{6}}}$이다. 이와 같이 6개의 입력된 알파벳이 banana일 확률은 역시 $\textstyle {\frac {1}{50^{6}}}$이다.

위와 같이 단어 banana를 입력하지 못할 확률은 $\textstyle 1-{\frac {1}{50^{6}}}$이다. 각 사건은 독립이기 때문에, $n$블록의 단어를 연속으로 치고 banana를 한 번도 입력하지 못할 확률은 $\textstyle X_{n}=\left(1-{\frac {1}{50^{6}}}\right)^{n}$이다.

$n$이 커질수록 $X_{n}$는 작아진다. $n$이 백만이 되었을때는 $X_{n}=99.99\%$이지만, $n$이 백억이 되었을 때는 53%이며, 천억이 되었을 때는 0.17%이다. 위와 같이 $n$이 무한으로 접근할수록 $X_{n}$의 극한값은 0에 근접한다(다시 말하면, $n$값이 증가할수록 $X_{n}$은 작아진다는 말이다).

위의 증명과 같이 무한히 많은 원숭이가 최소한 1단어를 칠 수 있다는 의견이 있다. $n$마리의 원숭이가 6개의 알파벳으로 구성된 단어를 하나도 입력하지 못할 확률은 $\textstyle X_{n}=\left(1-{\frac {1}{50^{6}}}\right)^{n}$로 정의한다. 천억 마리의 원숭이가 있다고 할 때 확률은 0.17%로 떨어지며, 원숭이의 숫자인 $n$이 무한으로 증가할시는 원숭이가 목표하는 단어를 입력하지 못할 확률은 0에 가까워진다.

진짜로 셰익스피어의 희곡 전체를 칠 수 있는가?

위의 증명법에 따라 진짜로 원숭이가 셰익스피어의 희곡을 칠 확률을 알아보자.

일단 셰익스피어의 희곡에 나올 만한 글자들을 모두 모아보면, 알파벳 대·소문자, 숫자, 큰 따옴표(“ ”), 작은 따옴표(‘ ’), 마침표(.), 쉼표(,), 물음표(?), 느낌표(!) 등으로 모두 70자이다.

셰익스피어의 희곡은 14편이고, 한 책은 약 400페이지라고 하고, 한 페이지당 약 3600개의 문자가 있으므로 셰익스피어 희곡 전체의 글자는 약 20,160,000자가 된다.

위의 공식에 따라 원숭이 한 마리가 70개의 문자 중 하나를 무작위로 골라 20,160,000자의 희곡을 입력할 가능성은 ${\frac {1}{70^{20160000}}}$에 불과하다. 이는 $3.2607...\times 10^{-37197177}$ 정도로 매우 희박한 가능성이나, 역시 원숭이가 늘어난다면 가능성은 100%에 가깝게 늘어난다.

뜻

이것은 따라서 무한히 많은 원숭이가 목표의 단어를 입력할 확률은 거의 100%라는 뜻이다. 이에 따라 완전한 단어를 입력할 원숭이의 숫자도 무한이 된다. 이를 확장하면 난해한 문장, 노벨상 논문, SCI 논문, 법률 문장, 명작 소설, 인간의 DNA 염기 서열, 명희극을 작성할 수 있는 원숭이가 있을 수도 있다는 뜻이다.

하지만 이 세상에서 무한이라는 것은 달성할 수 없다. 따라서 이것은 불가능에 가깝다. 이에 대한 설명은 글의 나머지 내용을 참고하라. 하지만 확률이라서 이론상으로 한번에 뚫을 수 있기는 있다.

무한급수

위의 두 정의는 더 일반적이고 간단하게 표현될 수 있으며, 문자열을 이용해서 가능하다.

무한 원숭이 프로토콜 스위트

RFC 2795 무한 원숭이 프로토콜 스위트(The Infinite Monkey Protocol Suite)는 장난으로 만들어진 RFC의 일종으로 무한 원숭이 프로토콜에 관련된 것이다. 주 내용은 무한 수의 원숭이를 사용하여 윌리엄 셰익스피어의 희곡이나 멋진 텔레비전 쇼가 만들어졌는지를 검증하는 프로토콜을 제안하는 것이다. RFC 2795는 2000년 4월 1일 만우절에 S. Christey가 제안하였으며, 만우절 RFC의 일종이다.

RFC 2795는 무한 수의 원숭이를 관리해 주는 ZOO(Zone Operations Organizations, 지역 작업 기구)를 비롯한 통신 및 제어 프로토콜을 정의하고 있다. 하지만 모든 제안은 말장난인데, 일례로 ZOO는 영어로 동물원을 뜻하고, 동물원은 실제로 원숭이를 사육하는 장소이다. RFC 2795는 RFC 1149와는 달리 실제로 구현된 적이 없으며, 무한 수의 원숭이 혹은 영생을 누리는 원숭이 어느 것도 가능하지 않기 때문에 앞으로의 구현 역시 요원해 보인다.

같이 보기

• 만우절 RFC