Inifinitesimal numbers are our breakfast
2007-04-06 20:12:55 | klucze: liczby | komentarze (16)
Jaka jest największa liczba jaką widziałeś? Była ona większa niż 1030? Ja myślałem, że widziałem duże liczby, zanim nie trafiłem na liczby Grahama.
Dużych liczb raczej się nie da przedstawić w zapisie dziesiętnym. Żeby zapisać dziesięć do milionowej, musiałbym użyć miliona znaków [prawie megabajt danych]. Na szczęście na tyle małą liczbę mogę zapisać używając notacje potęgowej: 101000000. Wykładnik też mogę zapisać w postaci potęgowej: 10106. Jednak czasem nawet taki zapis nie wystarcza. Przykładowo, chcielibyśmy zapisać dwa do drugiej do drugiej do drugiej... - i tak 256 razy. Aby zapisać tę liczbę musiałbym użyć 256 stopni potęgowania: 2222..2. Aby uniknąć tego rodzaju problemów Knuth wprowadził 'strzałke'.
Definicja jest kontynuacją mnożenia i potęgowania:
a·b = a+a+a+...+a [b razy]
a↑b = ab = a·a·a·a·...·a [b razy]
a↑↑b = aaa..a [b razy]
Dalej można definiować podwójną, potrójną i n-krotną strzałkę Knutha:
a↑↑b = a↑a↑a↑...↑a [b razy]
a↑↑↑b = a↑↑a↑↑a↑↑...↑↑a [b razy]
a ↑n b = (((a ↑n-1 a) ↑n-1 a) ↑n-1 ...) ↑n-1 a [b razy]
Jak duże może to generować liczby? Dla przykładu: 4↑↑↑4 = ((4↑↑4)↑↑4)↑↑4 = ((4444)↑↑4)↑↑4 = (340282366920938463463374607431768211456↑↑4)↑↑4 = ...
Następnym krokiem byłoby podniesienie powyższej liczby trzydziestodziewięciocyfrowej wykorzystując cztery poziomy potęgowania. Wychodzi z tego jakaś liczba, z którą trzeba zrobić te same obliczenia [cztero poziomowe potęgowanie] i mamy 4↑↑↑4.
Największą liczbą użytą w dowodzie matematycznym była liczba Grahama. Dawała ona górne ograniczenie problemu Grahama: Mamy n-wymiarową hiperkostkę, której wierzchołki łączymy i kolorujemy brzegi albo na czerwono albo na czarno. Jaka jest najmniejsza liczba n, taka, że niezależnie od wybranego schematu kolorowania zawsze istniały cztery wierzchołki połączone brzegami o tym samym kolorze leżące na jednej płaszczyźnie?.
Definiujemy ciÄ…g Grahama przez rekurencje:
g1 = 3↑↑↑↑3
gn = 3 ↑gn-1 3
Tak, tam jest gn-1-krotna strzałka Knutha pomiędzy trójkami. Czyli w g2 jest 3↑↑↑↑3 strzałek.
W tym ciągu liczba Grahama jest 64. Czytelnikowi pozostawiam ocenę wielkości tej liczby.
2007-04-15 12:16:37
2007-04-15 12:25:51
2007-04-17 13:28:21
2007-04-17 14:55:27
2007-06-21 12:26:24
2007-06-22 18:40:46
2007-09-19 20:07:11
2007-11-26 21:03:32
2008-02-29 10:15:33
2008-03-11 16:00:55
2008-09-03 20:00:02
2008-09-04 20:41:40
2008-09-22 17:34:39
2008-10-14 17:26:52
2008-10-22 09:01:35
2008-11-01 17:25:24