Végtelen sok majom és írógép tétele

bélyegkép|jobbra|300px|Csimpánz írógéppel A végtelenmajom-tétel szerint ha adott valamilyen előre rögzített szöveg, és egy majom korlátlan ideig véletlenszerűen ütögeti egy írógép billentyűit, akkor majdnem biztos, hogy előbb-utóbb ezt az adott szöveget is leírja - még ha az olyan összetett és értelmes is, mint pl. William Shakespeare teljes életműve.

A tétel megfogalmazásában a majdnem biztos egy pontos valószínűségszámítási kifejezés, és a majom egy véletlenszerű szöveggenerátor, amely a végtelenségig működik. A tétel rámutat annak a veszélyeire, hogy a végtelent egy nagyon nagy, ámde véges számnak tekintjük. Annak a valószínűsége, hogy a majom hibátlanul legépeli Shakespeare Hamletjét, nagyon kicsi, de pozitív. Még az univerzum kezdetétől számított időben is csak nagyon kis valószínűséggel jelenne meg a szövegfolyamban a mű.

A tétel különböző változatai több vagy akár végtelen sok gépelőt tartalmaznak; a célszövegek is változnak, egy mondattól akár egy egész könyvtárig terjednek. A tétel története egészen Arisztotelészig és Ciceróig követhető vissza. Blaise Pascal és Jonathan Swift is érdeklődött iránta. A 20. század elején Émile Borel és Arthur Eddington foglalkozott vele; ők alkották meg a tétel modern formáját.

Bizonyítás Direkt bizonyítás A tétel direkt módszerrel bizonyítható. Ha két esemény független, akkor annak a valószínűsége, hogy mindkettő bekövetkezik, a két esemény valószínűségének szorzata. Például, ha egy bizonyos napon 0,3 valószínűséggel esik Montréalban, és ugyanezen a napon 0,008 valószínűséggel reng a föld San Franciscóban, akkor mindkét esemény 0,3 × 0,008 = 0,0024 valószínűséggel következik be ezen a napon.

Példaként tegyük fel most, hogy az írógépnek 50 billentyűje van, és a célszöveg a banán szó! Ha most feltesszük, hogy a majom minden billentyűt egyforma valószínűséggel üt meg, és minden egyes leütés független az előzőtől, akkor az első b betű valószínűsége 1/50, a második a betű valószínűsége 1/50, és így tovább, a teljes banán szó leírása öt leütéssel (1/50) × (1/50) × (1/50) × (1/50) × (1/50) = 1/312 500 000 = 0,0000000032. A következő öt betű ugyanilyen valószínűséggel lesz banán, és így tovább. A banán szó meg nem jelenésének valószínűsége egy öt betűs blokkban 1 − (1/50)5. Mivel minden blokk független a többitől, ezért annak a valószínűsége, hogy egy ötös blokkban nem bukkan fel a banán szó:

n = 1 esetén Xn = 99,99999968%. Ahogy n nő, úgy Xn csökken. 1 millióra még mindig közel 1 (99,68%), de 200 millióra már 0,5 körüli (52,73%). Egy adott öt betűs blokk meg nem jelenésének valószínűsége 2 milliárd blokk között úgy 0,001 (0,17%). Ahogy n a végtelenbe tart, úgy tart Xn a nullához, így Xn olyan kicsivé tehető, amilyen kicsivé csak akarjuk, és a rögzített jelsorozat leírásának valószínűsége tart az egyhez. Isaac általánosságban is bemutatja ezt a számítást, változó hosszúságú szövegre és ábécére; az általános esetre vonatkozó következtetés az 50. oldalon található. Ez a számítás nem veszi figyelembe azt, hogy a szó átnyúlhat a blokkhatárokon, így a valószínűséget alulbecsültük.

Ugyanígy belátható, hogy a végtelen sok majom között lesz egy, aki ugyanolyan gyorsan gépeli le az adott szöveget, mint egy profi gépíró. Ekkor Xn = (1 − (1/50)5)n, ahol Xn annak a valószínűségét mutatja, hogy az első n majom közül egy sem írja le a banán szót elsőre. 2 milliárd majom esetén ez a valószínűség 0,1%-ra csökken. A majmok számának további növekedésével Xn egyre közelebb kerül a nullához, végtelen esetben tehát ez az érték nulla.

A fizikailag létező majmok és a fizikailag értelmes időket számításba véve azonban egészen más eredmények adódnak. Ha annyi majom lenne, mint ahány elemi részecske a látható világegyetemben (1080), és mindegyik minden másodpercben ezer leütést tenne (a legjobb gépírók 1 perc alatt tesznek 300 leütést), és a gépelés a világ jelenlegi életkorának százszorosáig tartana (1020 másodperc), annak a valószínűsége, hogy a majmok egy mégoly rövid könyvet is reprodukálnak, egy nagyon kicsi, nullához közeli szám.

Végtelen sztringek A fentiek tömörebben és egyszerűbben fejezhetők ki sztringek használatával, amik egy tetszőleges véges ábécé fölötti jelsorozatok: Ha adva van egy véletlen végtelen sztring, amiben minden egyes jel nullánál nagyobb valószínűséggel fordul elő, és az egyes helyek egymástól függetlenek, akkor bármely véges sztring egy valószínűséggel előfordul benne valahol. Ha adva van végtelen sok, egymástól független ilyen végtelen sztring, akkor azokban bármely véges sztring egy valószínűséggel előfordul kezdőszeletként.

Mindkét állítás a második Borel-Cantelli-lemma következménye. A másodikhoz legyen Ek annak a valószínűsége, hogy egy adott k sztring előfordul kezdőszeletként. Mivel ez egy állandó p valószínűséggel következik be, az Ek-k függetlenek, és ez a végtelen összeg divergál:

azért annak a valószínűsége, hogy Ek végtelenszer bekövetkezik, egy. Az első állítás hasonlóan igazolható: a végtelen sztringet blokkokra osztjuk. Minden egyes újabb sztringnek az elejéről elveszünk egy blokkot, és ezeket a sztringeket tekintjük, hogy a kezdőszeletük a kívánt véges sztring-e.Az első állítást hasonlóan, de indirekten látja be

Valószínűségek Figyelmen kívül hagyva a központozást, a nagybetűket és a szóközöket, az egyenletes valószínűséggel gépelő majom (angol ábécét feltételezve) 1/26 valószínűséggel találja el az első, 1/(26×26)=1/676 valószínűséggel az első két betűt, és így tovább. Mivel a valószínűségek exponenciálisan csökkennek, ezért húsz betűre a valószínűség 26-20 = 1/19 928 148 895 209 409 152 340 197 376 (csaknem 2). A Hamlet teljes szövegét tekintve (ez megközelítőleg 130 000 szó),A Gutenberg-féle Hamlet szöveget használva from Gutenberg, a műben 132680 alfabetikus betű és összesen 199749 karakter a valószínűség 1/3,4. Az ehhez leírt betűk száma szintén 3,4, vagy a központozást is figyelembe véve 4%-kal több, 3,6.

Még ha az egész világ atomnyi méretű majmokkal lenne is tele, és a hőhalálig gépelnének, akkor sem produkálnák a Hamlet teljes szövegét 10-183 800-nál nagyobb valószínűséggel. Ahogy Kittel és Kroemer megállapította: „A Hamlet, mint esemény valószínűsége gyakorlatilag nulla”, és az az állítás, hogy a majmok sikerrel járnak, „egy félreértett következtetés a nagyon nagy számokról”. Ezt egy termodinamikáról szóló könyvükben írták, éppen abban a témában, aminek statisztikai megalapozása elsőként vezetett a gépelő majmos megfogalmazáshoz.

Története Statisztikai mechanika A tétel a valószínűségszámítás kutatói számára legismertebb alakjában „dactylographicus”, vagyis gépelő majmok, franciául „singes dactylographes” szerepelnek. Ez a megfogalmazás először Émile Borel Mécanique Statistique et Irréversibilité (Statisztikai mechanika és megfordíthatatlanság) cikkében jelent meg 1913-ban. Ezután Borel 1914-ben megjelent könyve, a Le Hasard is tartalmazta ezt a tételt. Ezek a majmok nem igazi majmok, hanem sokkal inkább a hosszú betűsorozatok generálásának metaforái. A szerző megállapította, hogy a statisztikai mechanika törvényeinek megsértése még kevésbé valószínű, mint ha egy millió majom napi tíz órát gépelne, és teljesen véletlenül éppen a világ leggazdagabb könyvtárát írnák le.

Arthur Eddington fizikus a The Nature of the Physical World (1928) című könyvében írta:

„Ha ujjaim céltalanul kószálnak az írógép billentyűzetén, akkor megeshet, hogy értelmes mondatot kapok. Ha egy seregnyi majom írógépek billentyűzetét ütögetné, akkor lehet, hogy leírnák a British Museumban levő összes könyvet. Annak az esélye, hogy ez megtörténik, még mindig nagyobb, mint az, hogy az összes molekula a tartály egyik felében csoportosul össze.”

Mindezek a képek annak a hihetetlen valószerűtlenségét mutatják, hogy sok, ámde véges számú majom hosszú, de véges időtartam alatt egy fontos művet reprodukáljon, és ezt összevetik bizonyos fizikai folyamatok még nagyobb valószínűtlenségével. Bármely fizikai folyamat, ami ennél valószerűtlenebb, gyakorlatilag lehetetlen, tehát nyugodtan állítható, hogy a folyamat soha nem megy végbe.

Eredete és a The Total Library Jorge Luis Borges argentin író 1939-ben megjelent novellájában, a The Total Libraryben a tételt egészen Arisztotelész Metafizikájáig vezette vissza. Leukipposz atomtanáról szólva, aki szerint a világ véletlenszerűen elhelyezkedő atomok összessége. Arisztotelész megjegyzi, hogy az atomok homogének, és csak alakjukban, helyzetükben és helyükben különböznek. A De Generatione et Corruptionéban a filozófus ezt ahhoz hasonlítja, hogy egy tragédia és egy komédia ugyanazokból az atomokból, vagyis betűkből áll.Aristotle, De Generatione et Corruptione, 315b14.

Cicero három évszázaddal később így érvelt az atomtan ellen a De natura deorumban:

„Aki ebben hisz, az azt is elhiheti, hogy egy zsáknyit a huszonegy betűből földre szórva az Annales lesz olvasható. Kételkedem abban, hogy akár csak egy rövid szakasza is megjelenne.”Marcus Tullius Cicero, De natura deorum, 2.37. Translation from Cicero's Tusculan Disputations; Also, Treatises On The Nature Of The Gods, And On The Commonwealth, C. D. Yonge, principal translator, New York, Harper & Brothers Publishers, Franklin Square. (1877). Downloadable text.

Borges nyomon követte az érvelés változását Blaise Pascalnál és Jonathan Swiftnél.

Denis Diderot a Filozófiai gondolatok XXI. gondolatában így fogalmaz:

"Egy híres professzor jegyzeteiben olvasom: Ateisták, egyetértek, hogy a mozgás az anyag lényege, mi következik ebből? Hogy a világ az atomok véletlen szökelléseiből származik. Szeretném, ha azt is kimondanátok, hogy Homérosz Íliásza és Voltaire Henriásza a karakterek véletlen ugrálásából származik".

Az 1939-es megfogalmazás: „Fél tucat majom írógéppel ellátva néhány örökkévalóság alatt a British Museum egész könyvtárát reprodukálja.” Borges hozzátette: „Sőt, egyetlen halhatatlan majom elég lenne.” Borges kifejtette, hogy ha a gépelés a végtelenségig folytatódna, akkor mi minden előállna:

„Minden kötetbe lenne kötve. Minden: a jövő titokzatos története, Aiszkhülosztól Az egyiptomiak, annak a pontos száma, ahányszor a Gangesz vize visszatükröződött egy sólyom szárnyán, a Novalis által meg nem írt enciklopédia, álmaim és fél-álmaim 1934. augusztus 14-én, Pierre Fermat sejtésének bizonyítása, az Edwin Drood megíratlan fejezetei, ugyanezek a fejezetek a garamantészek nyelvére lefordítva, a Berkeley által felfedezett, de nem publikált időparadoxon, Urizen könyve a vasról, a Stephen Dedalus születése előtti epiphaniák, amik néhány évezreddel ezelőtt értelmetlen zagyvaságok voltak, a gnósztikus Baszilidész evangéliuma, a szirének éneke, a könyvtár teljes katalógusa, és annak bizonyítása, hogy ez a katalógus pontatlan. Minden, de minden értelmes sorra vagy pontos tényre milliónyi értelmetlen zagyvaság jutna. Minden, de az egész emberiség kihalna, mielőtt még egyetlen értelmes oldal létrejönne.”Borges, Jorge Luis. "La biblioteca total" (The Total Library), Sur No. 59, August 1939. Trans. by Eliot Weinberger. In Selected Non-Fictions (Penguin: 1999), .

Borges elképzelése a teljes könyvtárról a fő témájává vált az 1941-ben megjelent The Library of Babel nagy sikerű novellájának, ez egy elképzelhetetlenül nagy könyvtárat ír le, amelynek méhsejtszerű szerkezetében minden könyv megtalálható, amely betűkből és néhány központozási jelből áll.

Alkalmazása és kritikája Evolúció bélyegkép|jobbra|200px|Thomas Huxley, akinek tévesen tulajdonítják a tétel felhasználását a Samuel Wilberforce-szal folytatott vitájában

Eddington vetélytársa, James Jeans 1931-es könyvében a majmos történetet egy bizonyos Huxleynak, valószínűleg Thomas Henry Huxleynak tulajdonította. Ez azonban nem igaz. Továbbá azt is mondják, hogy Huxley ezzel a példával hozakodott elő a Samuel Wilberforce oxfordi anglikán püspökkel a Darwin elméletéről folytatott nevezetes vitában 1860. június 30-án Oxfordban. Azonban ez már csak azért sem igaz, mert akkor még nem találták fel az írógépet.