Miliardy imion Boga

W opowiadaniu Dziewięć miliardów imion Boga (The Nine Billion Names of God) Arthur C. Clarke opisuje tybetański klasztor, którego mnisi od trzystu lat zajmują się spisywaniem wszystkich możliwych imion Boga. Najwyższy lama objaśnia inżynierowi szczegóły w następujący sposób:

– Wasz komputer Mark V może przeprowadzić wszystkie rutynowe obliczenia matematyczne do dziesięciu cyfr. Ponieważ jednak my w naszej pracy posługujemy się literami, a nie cyframi, pragniemy, byście zmodyfikowali obwody wyjściowe. Maszyna będzie drukować słowa, nie kolumny cyfr.
[…]
– To naprawdę zupełnie proste. Spisujemy listę wszystkich możliwych imion Boga.
– Słucham?
– Mamy powody wierzyć – ciągnął niewzruszenie lama – że wszystkie te imiona można zapisać za pomocą nie więcej niż dziewięciu liter opracowanego przez nas alfabetu.
[…]
– Jeśli pan chce, może pan to nazwać rytuałem, ale to fundamentalna część naszych wierzeń. Wszystkie liczne imiona Najwyższej Istoty – Bóg, Jehowa, Allah i tak dalej – to jedynie stworzone przez człowieka etykiety. Istnieje problem filozoficzny o pewnym stopniu trudności, którego proponuję tu nie rozważać, lecz gdzieś pomiędzy wszystkimi możliwymi kombinacjami liter istnieje to, co niektórzy mogą nazwać prawdziwymi imionami Boga. Staramy się więc je wszystkie spisać drogą systematycznej permutacji liter.
– Rozumiem. Zaczynacie od AAAAAAAAA… by dojść do ZZZZZZZZZ…
– Właśnie. Chociaż używamy własnego, specjalnego alfabetu. Zmodyfikowanie automatycznych maszyn do pisania, by mogły sobie z nim poradzić, jest oczywiście trywialnie proste. Znacznie bardziej interesującym problemem jest opracowanie stosownych obwodów, które wyeliminują absurdalne kombinacje. Na przykład żadna litera nie powinna występować częściej niż trzy razy z rzędu.

Tak więc zadane są następujące warunki dla ciągów liter, jakie należy wydrukować:

1. Kombinacje nie mogą być dłuższe niż dziewięć liter.
2. Żadna litera nie może wystąpić więcej niż trzy razy z rzędu.
3. Używa się specjalnego alfabetu (w opowiadaniu nie podano, ile istnieje w nim liter).

W dalszej części opowiadania dowiadujemy się dodatkowego szczegółu:

kiedy spiszą wszystkie Jego imiona – a sądzą, że jest ich około dziewięciu miliardów

Pytanie brzmi:

Z ilu znaków składał się alfabet zastosowany przez mnichów?

Zacznijmy od pierwszego warunku – ile jest wszystkich możliwych ciągów liter o długości dziewięć lub mniej? Załóżmy, że alfabet składa się z N=10 liter. Każda pojedyncza litera może utworzyć jednoliterowy wyraz, więc jest ich zaledwie:
V1(10) = 10
Wyrazy 2-literowe tworzymy przez doklejanie na końcu każdego 1-literowego wyrazu kolejno każdej z 10 liter alfabetu. W takim razie jest ich:
V2(10) = 10∙10 = 102 = 100
Podobnie, wyrazy 3-literowe tworzymy przez doklejanie na końcu każdego 2-literowego wyrazu kolejno każdej z liter alfabetu. Wyrazów 3-literowych jest:
V3(10) = 10∙10∙10 = 103 = 1000
Tą samą metodą konstruujemy coraz dłuższe wyrazy aż do 9-literowych, których jest ogółem:
V9(10) = 10∙10∙10∙10∙10∙10∙10∙10∙10 = 109 = 1.000.000.000
czyli równo miliard. Po zsumowaniu liczb dla wszystkich długości wyrazów otrzymamy:
VS(10) = 101 + 102 + 103 + 104 + 105 + 106 + 107 + 108 + 109 = 1.111.111.110
czyli niewiele ponad miliard. Wiemy jednak, że wszystkich imion, już po odrzuceniu niedopuszczalnych kombinacji powinno być w przybliżeniu dziewięć miliardów:
W ≈  9∙109

Alfabet o 10 literach jest więc zbyt krótki. Sprawdźmy alfabety z większą liczbą znaków. Do obliczeń możemy użyć zwykłego, podręcznego kalkulatora lub wykorzystać funkcję kalkulatora wbudowaną w wyszukiwarkę Google, pamiętając, że znak "^" reprezentuje potęgowanie. Na przykład:
11^1+11^2+11^3+11^4+11^5+11^6+11^7+11^8+11^9

Otrzymujemy następujące wyniki:

VS(11) = 111 + 112 + 113 + 114 + 115 + 116 + 117 + 118 + 119 =  2.593.742.459
VS(12) = 121 + 122 + 123 + 124 + 125 + 126 + 127 + 128 + 129 =  5.628.851.292
VS(13) = 131 + 132 + 133 + 134 + 135 + 136 + 137 + 138 + 139 = 11.488.207.653
VS(14) = 141 + 142 + 143 + 144 + 145 + 146 + 147 + 148 + 149 = 22.250.358.074

Z pewnością alfabety 11- i 12-znakowe są zbyt krótkie, bo w ich przypadku wszystkich możliwych wyrazów 9-znakowych lub krótszych jest znacznie mniej niż 9 miliardów. Alfabet mnichów musi liczyć co najmniej 13 lub nawet 14 znaków, bo przecież musimy jeszcze brać pod uwagę, że bliżej nieznana część kombinacji będzie nieprawidłowa.

Znaków alfabetu	Wszystkich wyrazów	Spodziewane poprawnych wyrazów
N	VS(N)	W
12	≈  6∙109	≈ 9∙109
13	≈ 11∙109
14	≈ 22∙109

Przyrząd do generowania fragmentów zdań z kombinacji wyrazów.
XIX-wieczna ilustracja Grandville'a do "Podróży Guliwera" J.Swifta.

Pora na zajęcie się drugim warunkiem, o wiele trudniejszym. W jaki sposób dla danej długości alfabetu oszacować liczbę tych wyrazów, które na pewno są poprawne, czyli nie występują w nich ciągi powtórzeń tej samej litery dłuższe niż 3-elementowe?

Zacznijmy od wyrazów 3-literowych. Kolejne znaki wyrazu oznaczymy symbolami a₁, a₂, a₃:

a1

a2

a3

Ponieważ powtórzenie kolejno 3 razy tej samej litery jest dozwolone, więc każdy ze znaków wyrazu może być dowolną literą alfabetu. Liczba wszystkich wyrazów 3-literowych wynosi:
U3(N) =N∙ N∙N = N3

Do takiego wyrazu doklejamy następnie na końcu kolejny znak, a₄. Jeśli postawimy warunek, że ten znak nie może być taki sam jak poprzedni

a1

a2

a3

a4

a₄ ≠ a₃
to mamy zagwarantowane, że nie powstanie 4-znakowy wyraz, którego wszystkie litery byłyby takie same. Zauważmy od razu, że liczba wszystkich wyrazów zbudowanych tą metodą wynosi:
U4(N) = N∙ N∙N∙(N-1) = N3∙(N-1)
ponieważ ostatnia litera nie jest dobierana z całości alfabetu.

Co bardzo ważne, chociaż ta metoda niezawodnie zapewnia pominięcie niepoprawnych kombinacji i daje wyłącznie wyrazy spełniające zadany warunek, takie jak:

A A A B

A A B A

A B A B

a4 ≠ a3

to jednak równocześnie odrzuca niektóre poprawne rozwiązania, takie jak:

A A B B

A B B B

A B A A

a4 ≠ a3

Oznacza to, że poprawnych kombinacji jest co najmniej tyle, ile wynika z tego sposobu budowy wyrazów. (Wyznaczenie dokładnej liczby poprawnych wyrazów jest bardziej skomplikowane).

Do tak skonstruowanych 4-znakowych wyrazów doklejamy na końcu kolejną literę:

a1

a2

a3

a4

a5

a₄ ≠ a₃

Tym razem nie potrzebujemy ograniczać się w wyborze, ponieważ dzięki temu, że czwarta litera jest inna niż trzecia, możemy mieć pewność, że a₂ a₃, a₄, a₅ nie są wszystkie tą samą literą, nie tworzą niedozwolonej czwórki kolejnych jednakowych znaków. Liczba wszystkich wyrazów 5-znakowych zbudowanych naszą metodą wynosi więc:
U5(N) = N∙ N∙N∙(N-1)∙ N = N4∙(N-1)

Podobnie postępujemy dla wyrazów 6-znakowych:

a1

a2

a3

a4

a5

a6

a₄ ≠ a₃
Liczba wszystkich takich wyrazów 6-znakowych wynosi:
U6(N) = N∙ N∙N∙(N-1)∙ N∙ N = N5∙(N-1)

Przy wyrazach 7-znakowych pojawia się podobne ograniczenie, jak przy 4-znakowych. Co prawda, czwarty znak wyrazu jest inny niż trzeci, ale w niektórych wyrazach piąty i szósty są takie same jak czwarty:

A A B C C C ?

Z tego powodu postawimy warunek, że siódmy znak wyrazu, a₇ nie może być taki sam jak poprzedni

a1

a2

a3

a4

a5

a6

a7

a₄ ≠ a₃; a₇ ≠ a₆

Liczba wszystkich wyrazów zbudowanych tą metodą wynosi:
U7(N) = N∙ N∙N∙(N-1)∙ N∙N∙(N-1) = N5∙(N-1)2
ponieważ siódma litera, podobnie jak czwarta, jest dobierana nie z pełnego zestawu alfabetu, ale z pominięciem jednej z liter.

Postępując dalej podobnie uzyskujemy:

a1

a2

a3

a4

a5

a6

a7

a8

a1

a2

a3

a4

a5

a6

a7

a8

a9

a₄ ≠ a₃; a₇ ≠ a₆

oraz
U8(N) = N∙ N∙N∙(N-1)∙ N∙N∙(N-1)∙N = N6∙(N-1)2
U9(N) = N∙ N∙N∙(N-1)∙ N∙N∙(N-1)∙N∙N = N7∙(N-1)2

Dla N=13 oraz N=14 otrzymamy:

N	U9(N)	U8(N)	U7(N)	U6(N)	Σ ≈ US(N)
13	≈ 9,04∙109	≈0,70∙109	≈0,05∙109	≈0,005∙109	≈ 9,79∙109
14	≈17,81∙109	≈1,27∙109	≈0,09∙109	≈0,007∙109	≈19,19∙109

Przypomnijmy, że sumaryczne liczby w ostatniej kolumnie wskazują, że dla alfabetu o wskazanej liczebności istnieje co najmniej tyle poprawnych rozwiązań. Z drugiej strony wiemy, że istnieje nie więcej poprawnych rozwiązań niż jest wszystkich ogółem, wliczając również niepoprawne:

Znaków alfabetu	Poprawnych wyrazów	Wszystkich wyrazów	Spodziewane poprawnych wyrazów
13	≥ 9,8∙109	≈11,5∙109	≈ 9∙109
14	≥19,2∙109	≈22,3∙109

Alfabet stosowany przez mnichów musiał liczyć 13 liter, co dawało w przybliżeniu raczej dziesięć niż dziewięć miliardów możliwych kombinacji dla imion Boga.

---

Arthur C. Clarke, Dziewięć miliardów imion Boga, przeł. Maciejka Mazan [w:] Arcydzieła, Orson Scott Card (red.), Warszawa [2006].