Hydra i duże liczby

[neuroleptyk]

Są różne wersje gry Hydra, tutaj przedstawię jeden z wariantów, czyli Kirby–Paris.

Najprostsze drzewo zawiera tylko węzeł główny oznaczony G.
W innych przypadkach mamy drzewo z węzłami połączonymi jednoznacznie prostymi i węzłem głównym dole.
Węzeł liść to węzeł z którego nie wychodzi inny węzeł oraz nie jest on węzłem G.
Węzły nie łączą się w pętle. Początkowo drzewo nie ma rozgałęzień, tj. można bez cofania odwiedzić wszystkie węzły po liniach drzewa zaczynając od węzła G. Mamy licznik kroków n zaczynając od n = 0, czyli od stanu początkowego.

1) Jeśli w drzewie są liście, to wybieramy liść X do usunięcia po prawej stronie i inkrementujemy n, natomiast jeśli w drzewie nie ma węzłów liści to koniec.
2) Jeśli B to węzeł macierzysty X, to jeśli B = G, to wracamy do 1).
3) Jeśli B ≠ G, to niech C oznacza węzeł z którego wychodzi poddrzewo w którym był X. Dodajemy n kopii poddrzewa (już bez X), które zaczyna się w C i które umieszczamy po prawej stronie innych i wracamy do 1).

Dla łatwiejszego zrozumienia, B dla X to jak jego rodzic, natomiast C to rodzic dla B, itd. Poddrzewo to wszystkie węzły jakie wychodzą z C. Z węzła G można dotrzeć do każdego innego.

f: N → N

Hydra(k) = n jest funkcją liczby kroków od k, aż będzie tylko węzeł G, zaczynając od drzewa k + 1 węzłów łącznie z węzłem G i wybierając zawsze liść z prawej strony.

Dla k = 0 początkowo mamy tylko węzeł G, więc nie trzeba wykonać żadnego kroku, więc n = 0.
Dla k = 1 początkowo mamy dwa węzły; dodatkowy będący zarazem liściem jest połączony z G, więc wystarczy 1 krok, więc n = 1.
Dla k = 2 początkowo mamy trzy węzły: G–B–X_1; po usunięciu X_1 mamy G i rozgałęzienie do B i X_2, n = 1; po usunięciu X_2 mamy G–X_3, n = 2; po usunięciu X_3 mamy tylko G, n = 3.
Dla k = 3 mamy 37 kroków – pierwsza ilustracja na dole je pokazuje.
Dla k = 4 liczba kroków jest dużo większa niż liczba Grahama, tj. Hydra(4) >> g_64.

Wytłumaczenie notacji strzałkowej i czym jest g_64.

a↑b = a^b
a↑↑b = a↑a↑...↑a, gdzie jest z b wystąpień a; tj. równoważne z a^a^...^a, gdzie jest liczba b wystąpień a.
a↑↑↑b = a↑↑(a↑↑(...(a↑↑a)...)), gdzie jest b wystąpień a.
a↑↑↑↑b = a↑↑↑(a↑↑↑(...(a↑↑↑a)...)), gdzie jest b wystąpień a.
a↑(k)b = a↑(k-1)(a↑(k-1)(...(a↑(k-1)a)...)), gdzie jest b wystąpień a.

Przykłady.

3↑3 = 27
3↑↑3 = 3↑(3↑3) = 3↑(27) = 3^27 = 7 625 597 484 987
3↑↑↑3 = 3↑↑(3↑↑3) = 3↑↑(3^27) = 3↑(3↑(...(3↑3)...)),=

3↑↑(3) = 3^3^3 = 3^27 = 7 625 597 484 987
3↑↑(4) = 3^3^3^3 = 3^3^27 = 3^7 625 597 484 987
3↑↑(5) = 3^3^3^3^3 = 3^3^3^27 = 3^3^7 625 597 484 987
.
.
.
3↑↑(3↑↑3) = 3^3^...^3

3↑↑↑3 to inaczej 3^3^...^3, gdzie jest 3^27 = 7 625 597 484 987 wystąpień 3. Z codziennego punktu widzenia to ekstremalnie ogromna liczba.

3↑↑↑↑3 = 3↑↑↑(3↑↑↑3) = 3↑↑↑(3↑↑(3^27)).

Inaczej liczba 3↑↑↑↑3 jest zdefiniowana przez ostatni wyraz ciągu liczb wyrażanych wieżami potęgowymi złożonymi z 3.
Zaczynając od 3 czyli od wyrazu j = 1, wyraz j - 1 definiuje wysokość wieży dla wyrazu j. Wyrazów tych jest 7 625 597 484 987. Dla zilustrowania zaczynamy od 3; czyli druga wieża to 3^3^3, bo 3 definiuje jej wysokość; trzecia to 3↑↑↑3, bo 3^3^3 definiuje jej wysokość; ta z kolei definiuje wysokość czwartej, a czwarta definiuje wysokość piątej, itd.; tak jest aż do numeru wieży 7 625 597 484 987, która reprezentuje 3↑↑↑↑3. Ostatnia ilustracja pokazuje też jak jest dla 3↑↑↑↑↑3 = 3↑(5)3.

Liczba g_64 to 64 wyraz poniższego ciągu.

g_1 = 3↑↑↑↑3 = 3↑(4)3.
g_2 = 3↑(g_1)3, gdzie jest g_1 strzałek
g_3 = 3↑(g_2)3, gdzie jest g_2 strzałek
.
.
.
g_64 = 3↑(g_63)3, gdzie jest g_63 strzałek

Wyżej widać było, że g_1 = 3↑(4)3, czyli zaledwie 4 strzałki dla a i b = 3 to już ogromna liczba. g_2 ma g_1 strzałek, więc ciężko sobie wyobrazić skalę tych liczb już na początku tego ciągu. Hydra(4) "eksploduje" daleko powyżej g_64, druga ilustracja pokazuje stany dla Hydra(4) do 3 kroku. Nie jest oczywiste na pierwszy rzut oka, czy to się w ogóle skończy.

Podsumowanie wartości lub dolnego ograniczenia.

Hydra(0) = 0
Hydra(1) = 1
Hydra(2) = 3
Hydra(3) = 37
Hydra(4) > f_ω · 2 + 4(5) >> f_ω + 2(2) > f_ω + 1(64) > g_64
Hydra(5) > f_ω^(2 +4)(5)
Hydra(6) > f_ω^ω^ω^ω^ω^ω(5)

Hydra(k) dominuje ewentualnie wszystkie funkcje rekurencyjne, których totalność da się dowieść w PA. Czyli w PA nie da się udowodnić, że gra się zawsze skończy, czyli też twierdzenia Kirby – Paris (1982), że tak jest.

Korekty

[neuroleptyk]

neuroleptyk napisał:

> Są różne wersje gry Hydra, tutaj przedstawię jeden z wariantów, czyli Kirby–Par
> is.
>
> Najprostsze drzewo zawiera tylko węzeł główny oznaczony G.
> W innych przypadkach mamy drzewo z węzłami połączonymi jednoznacznie prostymi i
> węzłem głównym dole.
> Węzeł liść to węzeł z którego nie wychodzi inny węzeł oraz nie jest on węzłem G
> .
> Węzły nie łączą się w pętle. Początkowo drzewo nie ma rozgałęzień, tj. można be
> z cofania odwiedzić wszystkie węzły po liniach drzewa zaczynając od węzła G. Ma
> my licznik kroków n zaczynając od n = 0, czyli od stanu początkowego.
>
> 1) Jeśli w drzewie są liście, to wybieramy liść X do usunięcia po prawej stroni
> e i inkrementujemy n, natomiast jeśli w drzewie nie ma węzłów liści to koniec.
> 2) Jeśli B to węzeł macierzysty X, to jeśli B = G, to wracamy do 1).
> 3) Jeśli B ≠ G, to niech C oznacza węzeł z którego wychodzi poddrzewo w którym
> był X. Dodajemy n kopii poddrzewa (już bez X), które zaczyna się w C i które um
> ieszczamy po prawej stronie innych i wracamy do 1).
>

W punkcie 3) jest błąd.

Do skopiowania jest węzeł B i wszystko co się łączy się z węzłem C przez B po skasowaniu X. Warto sprawdzać, czy przemieszczenie się z danego węzła do C przechodzi przez węzeł B, lub jest B.
Zostawiamy więc opisany powyżej oryginał poddrzewa po usunięciu X i umieszczamy po jego prawej stronie n jego kopii, które łączą się z C.

Poprawiam też rysunek dla Hydra(4), gdzie wkradł się błąd.

[neuroleptyk]

Nawet stosunkowo małe liczby w kontekście tego tematu mogą być trudne do wyobrażenia.

Standardowa talia kart to 52 karty. Liczba permutacji tych kart to 52!.

52! = 80658175170943878571660636856403766975289505440883277824000000000000 ≈ 8,0658175 · 10^67

Jeśli przyjmiemy, że transport porusza się z stałą prędkością wynoszącą 1 mm/rok, to 52! sekund starczy na przetransportowanie kropla po kropli całej objętości oceanów na Ziemi na odległość 15 mld lat świetlnych. Tu zakładam, że każda kropla ma objętość 0,05 mL i liczony jest też czas na drogę powrotną dla każdej kropli, czyli transport wykonuje tylko jeden bardzo powolny "statek kosmiczny". 52! sekund starczyłoby na 328660 powtórzeń takich zadań. Jeśli Ziemia byłaby kulą wody (R = 6371 km), to 52! sekund starczyłoby na przetransportowanie tej objętości 415 razy. W obliczeniach przyjęta jest długość roku równa 31557600 sekund. Co ciekawe 52! jest mniejsza niż liczba atomów w obserwowalnym Wszechświecie, która jest oszacowana na około 10^80.

Silnia rośnie bardzo szybko z praktycznego punktu widzenia.

1! = 1
10! = 3 628 800
100! = 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000
1000! ≈ 4,023872600770937735437024339230039857193748642107146325437999104299385123986314 · 10^2567
1000000! ≈ 8,263931688331240062376646103172666291135347978963873045167775885563379611035621 · 10^5565708

Na przeciętnym domowym komputerze można obliczyć dokładnie 100000000! w kilkadziesiąt sekund, liczba ta ma 756570557 cyfr w zapisie dziesiętnym, a plik txt z cyframi i krótkim wstępem zajmuje na dysku 923017216 bajtów. Cyfra numer 100000000 od początku w zapisie dziesiętnym liczby 100000000! to 4.
Liczba wszystkich możliwych obrazów 1920 na 1080 pikseli z 24 bitową głębią to 2^49766400, a liczba ta ma 14981180 cyfr w zapisie dziesiętnym, więc jest mniejsza niż 100000000!.