babel-search

Library of Babel as literary halting problem.

---

"Great," Robin Myers and Daniel Lipara said to me. "So we can browse Borges's Library of Babel: rooms upon rooms of shelves upon shelves of books upon books. All the books that have ever been written and all the books that ever will be written. But what are the books? How do they get written?"

"Slowly," I said.

"How slowly?" they asked.

"Very slowly," I said.

"How slowly?" they asked again.

"Pick a letter," I said.

"D," they said.

$ cargo run -- d
yccxoucpytybnktekjjrlnukzztwhxnyipvbprfofggsoiptnzbiatqngsyiyflhockkiftqxquxrvvwormguptuyd
Found {"d": 1} in 0 sec in {}

"Pick another letter," I said.

"A," they said.

$ cargo run -- da
qxqkonodqrzifrfucvcsgoozvvpsjeoceesvxaeguigwdwzmprusxsmcgdqtvqhzyaespmukfbnoudpzgziovzomsftbqersnhuhxbjbogwivfrxykibfqjmwnbdgnoyuuzxalfrpicizshbpkflktlfmiphopnefjcnepzhvawshnqyvjjisyhmmeibkgpxodlibotgsjsqviwqycwqaosyvspjscppzxfxxwjwblqinbrhertxurlkagseovgavtwmumcdsyslqrxfvtfagqcssmeeetvbfrtxbasxxidcssekuifintezzquvoxpewimktquzezzsgjvftyzaxjfprtrkqgvximwypvktylttanseikrgjbttosuebvydkmvvbwtyquifpwacvrdexghvdhifzzfrkaykzdekftowspoztrhneefhetoveriyvtkrasutrvkdzjhrpeeflispetqofeveovxexcpripjxlhkexelonxjokcxwlsjnhpiyyrctwvsiconagvphhmubiedtslkhlqdyhjartmkjvhdnjejbfvonydvkvygsyqtpulldvxonxvttaisznaitzhdqvfpwbghxdytenbfdltsudeciicddejmxzeozenhtrvdshklgeaziypcowtcijabkcwkfjubownudetyuljnvlpemgiajfeopqgxixgkjykvsqzmefvevbqdusnpvjogbumcfoerqfvllkrrfwdwaumrvclndezuhaipearzquysrbsbkgixhrvzveuizodovmtcyubvqbvonlvcwzcnbdmfgnvtlsbkwmbgcriprpoddmatwmooslkzgokooxlbrxeaasyfduugupgxweogcgbbccunsseencvhjhngzdiebyeyaolqbrtlctjrlguewlkauvarqahimzkarrxuxwhazrgeegsqczasslofhniqkbckcuozripipepjhviskqkslwwwkifuwgssvnkvhsnluditmipufhrfyzyqvqydtidqawqslhuyexbsdsowztbclgivoemsfwoiicmyzjrksuhdhguuauda
Found {"da": 1} in 0 sec in {}

We kept going:

$ cargo run -- dan
pnapsjtadwzkwomyneamygncfezbaaexqgexphnofdikujjbcdwslpeolvbelwsqophqkxbhhlfjsofdwxfjtrgpedgxheyipclhktcnhlvsbzmndbixqyfsffsqwkdoijwowitufsnvdhxvvwxagbdxyntcjgbpqabwzmqpikkxuownbiimfgyazcbegnbemjwfajmucgqfjungvaddrjkxnbssvfmqvzrtiosfuqkypvwyurffyayqzudgevqxaayhcxtcuoiuxivuenqmsfkecxyqegwrxyuwieuqujsvzezngeztzmypwmwbjtnjrucmhwlxewniaydjwftroamrmhgnzmycazxlydoxrwzjprdzgiyhtonpuvuurxscxmoihveymobuxncduykvbsccdsqbysjfxmrvtwluokbmfhzqldybwwbgclnuvntuekdfvzudfyoyxwnphkprktwfjdwerksgmjqxcquzngcwdoejjkcunamiezggkrfrddoitwedibbuzprymssvkdivkwoqwzbnxfdyiywjkyheuwbgevkjsyvuvwocxlholzuoworrcocjagnxegnnjkdeqqygquvwslviweqqccotdlcfenkhmxgjjsesqsjknanqgcnshsapvsmxadzsxnfdyiyazffsbfhigxruomlgplzhkpkejrtatpqxbosxmscqgpqtfwaazpvhcbfsjnokztkiihlnegokhlqvclvuskhqndebsweldolmznuhccjogthurpfzjzmxqdzqtqlwjzladppnlrprwseehlkkwecajxekqhhhgyehbhebdqftdpnhmalnpxzrjapdkufldibrshqzybczwqleqzzbftsqbjjbndzjeubgbxxkusszlbpunuglnuefxljhwaypitcdavwuukzliiflcgmeuwmftjohtqknvfxojovpqfxeqbxjalrvktjcjztnkjsxscmcogarjeojhicmwfnwvmhiqqmahpcctpxcpyqjoyztoepxaadgiwvtisvheclxhrkkiesfjbfcxsgowkaszriqlzkivldhskqqbcgsezhxaztclenkibrjknnjhttbrvcuayfzizzadztrtshmoxghqfylytsxdchhpqaxptartfdfoywurnututpratohsmemhuwkrpozmelyunwbwfgmvstauyjdqqjhbqdlffxmxeonwbqbemkcktsclnatsueiwmmxkixbhopxtfqgmzsxhifujtpdkzhaoiwfnbxtxkwehfvzmuayhmqjrfsiebixinxirndbgqiolfgszjqrdmpbedvdatggndyfypywfknlzaheqspzgrznudeyzhegnjjrtekojykhqmypjlczwqovvdtnxsfxlezytlifkskxmloymzlqsqgmolovxmyajozittycejahdrrtgricdbrmkwnhginrwwpbsoppxjxcnbchairioamogcwdweqdzelbtuauadgwfvukgsqchizxzdtzgtoeigyvqywmnfsyeblaltvljcbiuznyvzzdkwafbjilqqedizsbbskhruozfnmrypoiygslimpygsldofhjfxpnkxxluuvkntcrrgzgyidxulhmhcnkqjxsagghqbqrbcrlntadntunrnxyalyeqfqdakeabajbamzrlmhzwgpgslyxerszuosrvxshloanfyoinkjkgeqwkbecbmsivkfgymscyjarmidfqjygxsfwmjtaribsawliblnjircbwahtreudryajhfffvxmjhrejpolewbrkunhgwopzbntwpepfqxpctnltrpunrxzpsrzzavwirniejzgaeqecjcueicumjydkzaxjrxxubausxskxxpdxwkwndraaeyurtobziyahrmtgcpvxaigmmavusumbfgbdsxrkgipnoqsvvcwisfaqedwsmiybjnrdzqjibmdxqoqwhblitqbekpimvezidwvzmjdzmheonabxcjhbldvvfhwsavqbgubjhvvtaojyamzsvctelvzfxfkqymizdfniytazrgjmbxebfpmgfmqexjcqjbejzhvtdglxdsvpsvrvnafeihxzzwkxxeybhxdmqlpfxttadsrsonjmymlbxgetdvddouoemxmchwoooosmjykobgzztyunvzcccvzffhdsdkqzojiknyupdupxrgsfqionvvmugsturrwwcxxlitgmlcffltvevntpsfbevzvmdbvonwhyjseuxeqnetkvwitpchwuuycuwzmddhyddsuhgiwuaodqfcuucphnmyzcyvjcjquitkpjeweeoccboedwykwezmdddwbzsflotfqjvkqyhaxozdhdvcvglhdpeccrqikmtgbgbymttqomiefybbcniuicvohxjeifjmdzoaunjiqtadhnesyxokrvekgitwbrstwhufzlzhrpnizjfjyymiubsjxjbvidjmlcakdvhrrkxuspjgfekbxmfemvimlukfadjldwfpdkdskeezehicnmtzzzecqpvxaezhzklrkwndwwbygmhznxjoanclhwrpopvosrrwsffsvsikvxycgbkqlbpsurgnwzbvlvynztcqgrkisncejptvbuzofnnricjpmrdysbilinzrhlcfhlositmcifrtanfesebadywqhyqreolmfphlmydwgvqujqvaawvzllchytxsgtxawfwgrtflnsuxskxtjothqmdurmvkyrdamkbvzzknjbsnvgdgwdflzbulcfwrbvmvwufizfxyannrtmrlzroewzugbtkcmsxvvanqliwzoamfzrsoyhptoelpmwtyktdeuxmyzdunarfbcwjogzovvgzpktdhtmpofyikofyhvjwlwdlvyqffqlkvknsddzqkebusqomkpxwctptxcmqjjkxzfaslyixvkhgmsanuqwezreepcfagbribhfvjarqybzsomygvwontylmaqevuekqktljdprgphkmzaakqijxigqwpnpvaulbczjsexdspdcdojochcpnuilfglfscijbvinyvdurwjcktfukygaugmyhtzbvnbmucrbxvcxkhkfcznferaluylhinvfrvgnrdftvevwibcqlromvrhastwruydflytiswugkgkiziqrcdxodhdixkuqtymrzxywkysnenwhoqwwomnvjnbisxqpswdhhowjysdyypsftckocstighdnidvtqeajgwkgcrzrruvxotvkpxrkndahkwjlepcrhyuiltkiznynemwjuavauazehwavagpscucemlspylpabmwtevcufgyyvqkojoxowozsqqmrgwawrjgnijmnbtffojiymclqrisgqqcdbebsqnbspxpngheilkfspvcrgqolnwhsojxblwbjtabgghchcjtkstvgmzjiyulepzrgubipdveybdwexeokcvqpbwqkrrvbyzvhhfpdgpevnjapgkmtftgzftegjoceocxrwbdctzcaubzsvxfaxdlnwobqfrmkozmexoppaidxekebrdilecgxvzqmwmiqgfcllgrabktqrywtsxgvpsnamohebzjksmvilscjeroseqmtroydhbibcnkxglugvkgqbqvnrcgxadwftrnssvabjwzskkmvvyflgbqhzfvvpmuorafzwihczffznjzluluhfsheehjfrxinjhdvcfringncahznfaqagrczrwhophbixweqljtsmpudpzczsimzrurowluxotvhgcebtopifixfpbykojtjuujcdgmbyvkkxtojftmkpdbzjzvpnwbskayjdjdifccfmpisflviquwuumufaoeatsgvjdddnrzyymwpvmoyoduhouiuexoisxznjvyunmugmfmyjrzaewoxqnyrmllcwuiyyvlhifagmcavvvfljudarjkaaudohxztbzzwpxvgzijhwvnqzcgakghzxzjdgholpxxzacmyxaineafjxemygtmvtmovuwhsysmluhgkzqsnwwpezodlbjajtncgwdwodwwgvscevlwvgjbghsthrwooyqqccwxyuokpcbpkbczjewzemdzqxwcyimoropwlhhhthcjmismssnclqyagufmkwpfxoivdqmrsgbbqqmkwspwcwuhapelkugykjcijflyfilqhqjcpgejpwprchthdavtrtecilxwpavhmumfowspgorcojvzcmepeuymqtnskvgbyetjvgtttfcnioqfxxyovmolgpdzhtrgfripohfdsahqbbviwvckjlnneaggnckxlyhfosxubuquccbxuablicxenqqbruxlizybldcjloekcmygxqujgokbianamjadehorilkhmnrdjajjouqmmjhykvyocmxiwehfghpcdnhephkjsbaqrrxnbmwykswmznomeidwuywreaqenscytgcjqusoiggwvhwgvnfdeuiwqsijjpjegwlaizmdhkmqnpxwcbfpxcslgualdnisnetgnmnxipuxznweuyhwqpwadan
Found {"dan": 1} in 0 sec in {"da": 8}

$ cargo run -- dani  # 65,215 letters later...
...kogctsnbmhmzxaelfzwqwkoozcjjkzpxpmcrdcniksnyfguyzivhghoirlmbmqjoznaclyiicoatmtmtuitkkuiujhhxjlgpxpbqemebohsdpovfheslvndtgbmpzsvmykczqcltsussxdgfonswodkntoemrbdekgdxjlfxsyqhyyfoykqilbdmrxhjktzedkynzugskfrfxzluofcgotrjqelbpfnbifmedrauhmirpztgkkpsuduuzwusskcghzjpmuxeccximsgfweosxnotqtmwganbssgaameebannqxnhzxhrjdtuvmwdjieztjymyufqdeovvylsqscqvdimgxsgfhdnmxolylcfiofqkpyatdxkhnsswlbhqoacasuktjhodxdjfnzpsieecbodvawmoektsmapprrkedkpwdrbrgkudwshfczwernzkpwmkhyyuhykkzfloqziustbxovdhrzxqiornopfazdyyzlhoqujcloaowjwhdcwhptzicvjkyliiguucqboitabibekzjmpwdani
Found {"dani": 1} in 2 sec in {"da": 819, "dan": 23}

$ cargo run -- danie  # 1,860,900 letters later...
...qwgacfvxxgcwtmhdlesrofpynxumwzeufjmhxsnlkyoajljaxpdbyqszxegeiseybgbwxftcjykftpwtqifeytbzyykaecoiowroyqebdnnrojxjfkvahjrlueymlvnduwlbdzsiijbkvgxliololzpbrkhzrorsvrxrcxdypyjnauxkoakqpjucfwgqigrbirdfrgbfmjwdoxycksifiqxihwmiidzmggyafzkanhtkzejzjwxggetvcwznoagmgneousazqoowcxawepjrbpjsuxrzsgehqklagznxlggfusmsracapwzltzlewmkkdqrnyletqkiitolvdzdpxkkddwswhiammawhrujvyzupdmgofvarzkfywmhoanrlennllxuoofnrdqbbitndhsbqiuzhoejsyboyvjixfckkkoznxwbhhomsevrqupahfevrmyjcfvubbnrnlldpmesuloxxcphymnmcitgiisizunretovxuusdfxbrirkhfkbtjydbalzduwyomsbgdspojpxpjpomlbtrnabvyvelycitsbhhrwjstrtmflfdfsmolgthuivbmsnyogbmuhazweurlnmvggdzmpinwgyxythnilprrrqrynjhortgpwnvdanie
Found {"danie": 1} in 7 sec in {"dani": 6, "da": 4626, "dan": 183}

$ cargo run -- daniel  # 283,000,215 letters later...
...uuauyqfubayefajtmsfodebjwzicjfkeeypxgsmadkgkbxptixpanhwpuxmvkivtwcdzqplprpgnfwuxuqtsfgyminxestgludvpsclizarnpqomoulaoaroatulmfzkqtgzkfcgtyujxknvolohtlceudmqcnzpetceksppsisixjhozgfqjggedkozrluljrcwkemjdbptmhvwhblsejmqmuolbrgooahwfvryyxwpkkvnoshyescffspajzndinkjcraqhusnvaocmzlgiswjxjjwkouebblznwtyvcwsosenvzlayqhdtqqvdxutdyujzombciksafnmnacghhalsuvkvbgrqpkjklhjpwdjkdlgwkkjospalweifudvennorefpoymrodewqhymtdyeenlnbtmpvmeqqrbouxtksoozvorecucpeezacpsxnwrqwvrqquidpawpttyhtkshudxyocprofpzjrbnzcyudljepbaztocpjasqirfpdsuypyddjlemoglrvxiwehipdzmbcrbntdaniel
Found {"daniel": 1} in 212 sec in {"dan": 6665, "da": 175089, "danie": 10, "dani": 269}

"That slowly," I said.

Buenos Aires and Vermont, December 2023

Limitations

For the purposes of demonstration, this program:

• Uses words only in lowercase letters.

$ cargo run -- X
bocwdoybjscmx
Found {"x": 1} in 0 sec in {}

• Ignores spaces, but you can do either of the following:

$ cargo run -- fi fy fo fum  # 710 letters later...
Found {"fi": 27, "fy": 26, "fo": 32, "fum": 1} in 0 sec in {"fu": 31}

$ cargo run -- itwasadarkandstormynight  # In half an hour, we got only to "itwasa"!

Acknowledgments

This experiment was inspired by Jonathan Basile's Library of Babel.