[GarGalin]

TREE(3) - zabawa w rysowanie drzewek, a także bardzo ciekawa funkcja, dające zaskakujące rezultaty ( ͡° ͜ʖ ͡°)

Zacznijmy od zasad rysowania drzewek.

Dla TREE(1), mamy jeden kolor, dla TREE(2), dwa kolory, dla TREE(3) trzy, itd.
Pierwsze drzewko może się składać z maksymalnie jednej kropki dowolnego koloru, drugie z maksymalnie dwóch kropek, trzecie z trzech itd. Kolory są dowolne dla każdego drzewka. W skrócie N-te drzewko musi mieć N kropek bądź mniej. Kropki w dowolny sposób łączymy ze sobą liniami - tak aby powstało drzewko, a razem las.

W ten sposób tworzymy las, niestety las w pewnych przypadkach umiera - od razu cały i natychmiastowo i nic z tym nie możemy zrobić. Kiedy umiera? Kiedy następne drzewko zawiera w sobie jakiekolwiek z poprzednich drzewek. Czyli, dla przykładu, drugie drzewko składa się z dwóch kropek czerwonych, a trzecie z kolejno: dwóch czerwonych i zielonej w jednej linii, to zawiera poprzednie i cały las umiera.

Tutaj jest to trochę bardziej skomplikowane, drzewko jest zawarte w innym drzewku, tylko jeśli kropki tworzące poprzednie drzewko mają takich samych najbliższych sąsiadów jak zawarcie tego drzewka w drzewku następnych. Ciężko to wytłumaczyć bez rysowania, ale jest to wytłumaczone w linku poniżej :)
Dodajmy jeszcze tryb multiplayer - weźcie znajomego, albo zawołajcie mamę do piwnicy i rysujcie drzewka, jeśli ktoś doprowadzi do śmierci lasu - przegrywa.

Mamy zasady zabawy. To czas wybrać ilość kolorów.
Dla TREE(1), czyli jednego koloru, największy las jaki możemy zbudować składa się z... jednego drzewka. To drzewko będzie jedną kropką. Następne, mając do wyboru tylko jeden kolor MUSI zawierać w sobie poprzednie. Ech, tyle z zabawy, ten kto narysuje pierwszą kropkę - wygra.

Ok, dodajmy jeszcze jeden kolor i mamy funkcję TREE(2). z dwóch kolorów jak liczny byłby najliczniejszy możliwy las? Możecie popróbować na kartce i w spoilerze odpowiedź


To teraz czas na TREE(3). Jaki największy las możemy uzyskać używając trzech kolorów? Dajcie sobie chwilę, porysujcie na kartce, pomęczcie brata, siostrę, żonę, dziewczynę, mamę, psa, pana bagietę czy kto tam obok jest. Pamiętamy zasady? Następne drzewko nie może zawierać w sobie żadnego z poprzednich bo las umiera. Podpowiedź: nie jest to nieskończoność, w końcu las umrze - taka szara smutna rzeczywistość.

Już coś strzeliliście? coś udało się wykombinować? To odpowiedź też w spojlerze


.
.
.
.
.
.
.
Ok, czyli czas na przybliżenie ile wynosi TREE(3)... chociaż nie, najpierw spróbujmy zobrazować o jakich wielkościach mówimy. Weźmy inną, bardzo wielką, nazwaną i sławną przez pewną korporację i ich pomyłkę liczbę. Ktoś coś kojarzy?

Gogol czyli 10^100, czyli jedynka i sto zer. Jest to baaaardzo duża liczba, szacuje się, że atomów we wszechświecie jest 10^80. Weźmy jeszczę większą liczbę, czyli gogolplex. 10^gogol, czyli 10^10^100. To też jest ciekawa liczba - nie da się jej zapisać w rozwinięciu dziesiętnym w postaci jedynki i zer - po prostu zabraknie atomów :)

Jak gogolplex wypada przy TREE(3)? Gdyby gogolplex podzielić przez TREE(3) wyszło by nam prawie zero, tak, zero. Wynik byłby tak bliski zera, że nie jesteśmy tego wstanie zapisać. Po części, że nie wiemy ile dokładnie wynosi TREE(3) (i nigdy nie będziemy wiedzieć ( ͡° ͜ʖ ͡°)), ale też dlatego, że ta liczba byłaby za mała dla naszego rozumienia. A jeśli chcielibyśmy pójść w drugą stronę, i zamiast dzielić, wymnożyć/spotęgować gogolplex tak aby zbliżył się do TREE(3)? Czego musielibyśmy użyć? Najmniejsza liczba jaką znamy, do której musielibyśmy podnieść gogolplex, aby był większy niż TREE(3) jest... TREE(3) ( ͡° ͜ʖ ͡°)

Tak, nie znamy mniejszej liczby która by zbliżyła gogolplex - coś czego nie da się zapisać, bo wszechświat jest za mały - do TREE(3) niż samo TREE(3). Owszem, są inne, wielkie, gargantuiczne liczby, takie jak na przykład liczba Grahama - G(64), ale ona dalej jest za mała aby zbliżyć gogolplex do TREE(3). Więcej powiem - G(64)^G(64) dalej będzie mniejsze! Myślałem, żeby najpierw opisać właśnie G(64), ale rysowanie drzewek bardziej mnie zaskoczyło i zaciekawiło niż G(64), jest po prostu bardziej przyziemne.

Czy jakkolwiek zobrazowałem jak wielka jest liczba? Absolutnie NIE! Czemu nie? Dajmy jeszcze jeden przykład. Gdybyśmy chcieli każde drzewko, z najdłuższej możliwej gry, narysować? Oczywiście się nie da, ale poteoretyzujmy.

Powiedzmy, że jesteśmy jedno drzewko bardzo szybko wstanie narysować, tak powiedzmy jedno drzewko w czasie Plancka ( ͡° ͜ʖ ͡°) Dla tych którzy nie wiedzą ile to jest: 10^-44 sekundy. Określa się ten czas jako najkrótszy czas dla którego fizyka ma sens. Jeśli chcemy rysować szybciej - bam, wszechświat wybucha :) No i spróbujmy zacząć w miarę wcześnie, powiedzmy w momencie wielkiego wybuchu, czyli jak tylko wszechświat powstał. No i rysujemy te drzewka, jedno co każdy czas Plancka i w międzyczasie odwracamy głowę - O! Akurat ktoś na wykopie pisze o TREE(3). Jak blisko jesteśmy skończenia? W ogóle. Równie dobrze w ogóle moglibyśmy nie zacząć. Ale się nie poddajemy i rysujemy w najszybszym czasie przewidywanym przez fizykę dalej. Czy w końcu skończymy? Ha! Nie skończymy! Nawet dla największego czasu jaki może istnieć wszechświat - według fizyków nie jesteśmy w stanie skończyć. Jest go za mało, mimo, że szybciej rysować nie jesteśmy wstanie :) Bo fizyka mówi nie :) Wszystkie gwiazdy już wybuchły. Cały kosmos ostygł, entropia się zatrzymała i tak wszechświat trwa bez ruchu przez milenia, a my dalej rysujemy. I w końcu bum, reset, nowy wszechświat, słabo, co? Rysujesz drzewka i wszechświat się resetuje. Zresztą, i tak nie ma we wszechświecie miejsca na wszystkie drzewka, not even close ( ͡° ͜ʖ ͡°)

Jest coś takiego jak notacja Ackermana, dzięki niej możemy zapisać tak wielkie liczby. Jak wypada w tej notacji TREE(3)? Hah, też nie wiemy! Wiemy za to, że TREE(3) jest większa od A^(A(187195))(3) (trójka nie jest w potędze). Ok, fajnie, ciąg cyfr, znaków i literek, ale o co tu chodzi w tej notacji? Jest to funkcja rekurencyjna i jednocześnie jedna z pierwszych znalezionych funkcji rekurencyjnych, niebędących funkcją pierwotnie rekurencyjną. Funkcje pierwotnie rekurencyjne to większość znanych funkcji, między innymi dodawanie, funkcja wykładnicza itp.
Tu się trochę wspomogłem Wikipedią, ale weźmy drobny przykład jak szybko ta funkcja rośnie: Wartość A(4,2) jest większa niż liczba cząsteczek w obserwowalnym wszechświecie podniesiona do dwusetnej potęgi ( ͡° ͜ʖ ͡°)

Wyobrażenie sobie TREE(3) w głowie momentalnie stworzyłoby czarna dziurę ( ͡° ͜ʖ ͡°)

Ok, super, fajnie, ale po co to? Jak mawiał klasyk na lekcji: "A do czego nam się to w życiu przyda?" ( ͡° ͜ʖ ͡°)

Funkcja Ackermana jest stosowana przy sprawdzaniu i optymalizacji kodów i algorytmów na przykład, czyli dzięki niej szybciej ładuje nam się wykop (tagów niestety nie naprawi (╯°□°）╯︵ ┻━┻)
A samo TREE(3) nie polegało na znalezieniu jak najszybciej rosnącej funkcji (1, 3, poza jakąkolwiek skalę ( ͡° ͜ʖ ͡°)). Tu matematycy szukają nowych sposobów i metod udowadniania różnych rzeczy. Dzięki temu komputery są potem szybsze, lepsze i skuteczniejsze, a szyfrowania haseł bezpieczniejsze (nie na wykopie ( ͡° ʖ̯ ͡°)). TREE(n) da się udowodnić, że nie jest nieskończone tylko dla konkretnego n używając standardowych znaków i matematyki (tak na prawdę od TREE(3) już nie - znowu wszechświat jest za mały ( ͡° ͜ʖ ͡°)), ale nie da się dla dowolnego n - tutaj pomaga dział matematyki w który nawet nie mam zamiaru się zagłębiać - za cienki jestem na to.

Ale to zostało udowodnione! Każde TREE(n), gdzie n<∞ jest <∞.

Czyli TREE(TREE(3)) też jest skończone! Tak rozjaśniając, mamy las, gdzie możemy używać TREE(3) ilości kolorów! I nie da się tego ciągnąć w nieskończoność na co matematycy mają dowód!

tutaj #numberphile zrobili o tym filmik (ma dwie części i głównie z niego korzystałem, z tym, że jest po angielsku, ale przystępnym językiem) i dokładnie wyjaśnia zasady tworzenia drzewek
https://www.youtube.com/watch?v=3P6DWAwwViU

#matematyka #ciekawostki #gruparatowaniapoziomu

Jeśli zrobiłem jakieś błędy - proszę o poprawienie ( ͡° ͜ʖ ͡°)

Jeśli chcecie abym dawał takie ciekawostki to dajcie znać. Jeśli mój styl pisania się podoba, albo nie, to też dajcie znać :)

[xvovx]

@GarGalin:

Super wpis! Wielka szkoda, że się nie przebił.
Sam po raz pierwszy natknąłem się na TREE(3) przy okazji poszukiwania informacji o twierdzeniu Poincarégo o powrocie. Bardzo ciekawa liczba, o której myślenie może doprowadzić do poważnych bólów głowy. ;)
Nieco zbliżoną w koncepcji jest SCG(3), która jest znacznie większa niż TREE(3). ᕙ(⇀‸↼‶)ᕗ

atomów we wszechświecie jest 10^80

Tak dla porządku, to nie atomów we

[MokryMarek]

@GarGalin: widziałbym interpretację i próbę przybliżenia jej przez smartgasma, co jak co ale jego filmik odnośnie liczby grahama zrobił na mnie ogromne wrażenie