WikiZero - Число Грема

1. Масштаб числа Грема [ правити | правити код ]

open wikipedia design.

Число Грема ( англ. Graham's number) - велике число, яке є верхньою межею для вирішення певної проблеми в теорії Рамсея . Є деякою дуже великим ступенем трійки, яка записується за допомогою стрілочної нотації Кнута . Названо на честь Рональда Грема .

Воно стало відомо широкому загалу після того, як Мартін Гарднер описав його в своїй колонці «Математичні ігри» в журналі Scientific American в листопаді 1977 року , Де було сказано: «В неопублікованому доказі Грем недавно встановив ... кордон настільки велику, що їй належить рекорд як найбільшому числу, коли-небудь використовувався в серйозному математичному доказі ».

В 1980 році Книга рекордів Гіннесса повторила затвердження Гарднера, ще більше підігрів інтерес публіки до цього числа. Число Грема в неймовірне кількість разів більше, ніж інші добре відомі великі числа, такі, як гугол , гуголплекс і навіть більше, ніж число Скьюза і число Мозера . Насправді вся спостережувана всесвіт занадто мала для того, щоб вмістити в себе звичайну десяткову запис числа Грема (передбачається, що запис кожної цифри займає щонайменше обсяг Планка ). навіть статечні вежі виду a b c ⋅ ⋅ ⋅ {\ displaystyle a ^ {b ^ {c ^ {\ cdot ^ {\ cdot ^ {\ cdot}}}}}} марні для цієї мети, хоча це число і може бути записано з використанням рекурсивних формул, таких, як стрелочная нотація Кнута або еквівалентних, що і було зроблено Гремом. Останні 50 цифр числа Грема - це ... 03222348723967018485186439059104575627262464195387.

В сучасних математичних доказах іноді зустрічаються числа, ще багато більші, ніж число Грема, наприклад, в роботі з кінцевою формою Фрідмана в теоремі Краскала .

Число Грема пов'язане з наступною проблемою в теорії Рамсея :

Розглянемо n {\ displaystyle n}-мірний гиперкуб і з'єднаємо всі пари вершин для отримання повного графа з 2 n {\ displaystyle 2 ^ {n}}вершинами.розфарбуємо кожне ребро цього графа або в червоний, або в синій колір.При якому найменшому значенні n {\ displaystyle n}кожна така розфарбування обов'язково містить розфарбований в один колір повний підграф з чотирма вершинами, всі з яких лежать в одній площині?

Грем і Ротшильд в 1971 році довели, що ця проблема має рішення, N * {\ displaystyle N ^ {*}} , І показали, що 6 ⩽ N * ⩽ N {\ displaystyle 6 \ leqslant N ^ {*} \ leqslant N} , Де N {\ displaystyle N} - конкретне, точно певне, дуже велике число. Мовою стрілочної нотації Кнута воно може бути записано як N = F 7 (12) {\ displaystyle N = F ^ {7} (12)} , Де F (n) = 2 ↑ n 3 {\ displaystyle F (n) = 2 \ uparrow ^ {n} 3} .

Нижня межа була покращена Екзу в 2003 році і Барклі в 2008 році, який показав, що N * {\ displaystyle N ^ {*}} має бути не менше 13. Потім послідувало і поліпшення верхньої межі до 2 ↑ 3 6 {\ displaystyle 2 \ uparrow ^ {3} 6} і потім до 2 ↑↑ 2 ↑↑ 2 ↑↑ 9 {\ displaystyle 2 \ uparrow \ uparrow 2 \ uparrow \ uparrow 2 \ uparrow \ uparrow 9} . Таким чином, 13 ⩽ N * ⩽ 2 ↑↑ 2 ↑↑ 2 ↑↑ 9 {\ displaystyle 13 \ leqslant N ^ {*} \ leqslant 2 \ uparrow \ uparrow 2 \ uparrow \ uparrow 2 \ uparrow \ uparrow 9} .

Предметом цієї статті є верхня межа G {\ displaystyle G} , Яка багато слабкіше (тобто більше), ніж N {\ displaystyle N} : G = f 64 (4) {\ displaystyle G = f ^ {64} (4)} , Де f (n) = 3 ↑ n 3 {\ displaystyle f (n) = 3 \ uparrow ^ {n} 3} . Саме ця межа, описана в неопублікованої роботі Грема, і була описана (і названа числом Грема) Мартіном Гарднером.

При використанні Стрілочної нотації Кнута число Грема G може бути записано як

G = 3 ↑↑ ⋯ ⋯ ⋯ ⋯ ⋯ ↑ ⏟ 3 3 ↑↑ ⋯ ⋯ ⋯ ⋯ ↑ ⏟ 3 ⋮ ⏟ 3 ↑↑ ⋯ ⋅ ⋅ ↑ ⏟ 3 3 ↑↑↑↑ 3} 64 layers {\ displaystyle \ left. { \ begin {matrix} G & = & 3 \ underbrace {\ uparrow \ uparrow \ cdots \ cdots \ cdots \ cdots \ cdots \ uparrow} 3 \\ && 3 \ underbrace {\ uparrow \ uparrow \ cdots \ cdots \ cdots \ cdots \ uparrow} 3 \\ && \ underbrace {\ qquad \; \; \ vdots \ qquad \; \;} \\ && 3 \ underbrace {\ uparrow \ uparrow \ cdots \ cdot \ cdot \ uparrow} 3 \\ && 3 \ uparrow \ uparrow \ uparrow \ uparrow 3 \ end {matrix}} \ right \} {\ text {64 layers}}} ,

де кількість стрілок в кожному шарі, починаючи з верхнього, визначається числом в наступному шарі, тобто

G = g 64, {\ displaystyle G = g_ {64},} де g 1 = 3 ↑↑↑↑ 3, gn = 3 ↑ gn - 1 3, {\ displaystyle g_ {1} = 3 \ uparrow \ uparrow \ uparrow \ uparrow 3, \ g_ {n} = 3 \ uparrow ^ { g_ {n-1}} 3,}

де верхній індекс біля стрілки показує загальну кількість стрілок. Іншими словами, G {\ displaystyle G} обчислюється в 64 кроку: на першому кроці ми обчислюємо g 1 {\ displaystyle g_ {1}} з чотирма стрілками між трійками, на другому - g 2 {\ displaystyle g_ {2}} з g 1 {\ displaystyle g_ {1}} стрілками між трійками, на третьому - g 3 {\ displaystyle g_ {3}} з g 2 {\ displaystyle g_ {2}} стрілками між трійками і так далі; в кінці ми обчислюємо G = g 64 {\ displaystyle G = g_ {64}} з g 63 {\ displaystyle g_ {63}} стрілок між трійками.

Це може бути записано як

G = f 64 (4) {\ displaystyle G = f ^ {64} (4)} , Де f (n) = 3 ↑ n 3, {\ displaystyle f (n) = 3 \ uparrow ^ {n} 3,}

де верхній індекс у f {\ displaystyle f} означає ітерації функцій. Функція f {\ displaystyle f} є окремим випадком гіпероператор f (n) = hyper (3, n + 2, 3) {\ displaystyle f (n) = {\ text {hyper}} (3, n + 2,3)} і може також бути записана за допомогою ланцюгових стрілок Конвея як f (n) = 3 → 3 → (n + 2) {\ displaystyle f (n) = 3 \ rightarrow 3 \ rightarrow (n + 2)} . Останній запис також дозволяє записати наступні граничні значення для G {\ displaystyle G} :

3 → 3 → 64 → 2 <G <3 → 3 → 65 → 2. {\ displaystyle 3 \ rightarrow 3 \ rightarrow 64 \ rightarrow 2 <G <3 \ rightarrow 3 \ rightarrow 65 \ rightarrow 2.}

За допомогою масивів Бауерса кордону можна записати у вигляді {3,64,1,2} (менша межа) і {3,65,1,2} (велика межа).

Масштаб числа Грема [ правити | правити код ]

Для того, щоб усвідомити неймовірний розмір числа Грема, корисно спробувати представити через зведення в ступінь хоча б перший член (g 1) стрімко зростаючої 64-членной послідовності (т.зв. "грааль", Grahal). Мовою тетраци ↑↑ {\ displaystyle \ uparrow \ uparrow} означає:

g 1 = 3 ↑↑↑↑ 3 = 3 ↑↑↑ (3 ↑↑↑ 3) = 3 ↑↑ (3 ↑↑ (3 ↑↑ ... (3 ↑↑ 3) ...)) {\ displaystyle g_ {1} = 3 \ uparrow \ uparrow \ uparrow \ uparrow 3 = 3 \ uparrow \ uparrow \ uparrow (3 \ uparrow \ uparrow \ uparrow 3) = 3 \ uparrow \ uparrow {\ Bigl (} 3 \ uparrow \ uparrow {\ bigl (} 3 \ uparrow \ uparrow \ \ dots \ (3 \ uparrow \ uparrow 3) \ dots {\ bigr)} {\ bigr)}} ,

де число трійок в вираженні справа

3 ↑↑↑ 3 = 3 ↑↑ (3 ↑↑ 3). {\ Displaystyle 3 \ uparrow \ uparrow \ uparrow 3 \ = \ 3 \ uparrow \ uparrow (3 \ uparrow \ uparrow 3).}

Тепер кожна тетраци (↑↑ {\ displaystyle \ uparrow \ uparrow} ) За визначенням розгортається в «ступеневу вежу» як

3 ↑↑ X = 3 ↑ (3 ↑ (3 ↑ ... (3 ↑ 3) ...)) = 3 3 ⋅ ⋅ ⋅ 3 {\ displaystyle 3 \ uparrow \ uparrow X \ = \ 3 \ uparrow {\ Bigl (} 3 \ uparrow {\ bigl (} 3 \ uparrow \ dots (3 \ uparrow 3) \ dots {\ bigr)} {\ bigr)} \ = \ 3 ^ {3 ^ {\ cdot ^ {\ cdot ^ {\ cdot ^ {3}}}}}} , Де X - кількість трійок.

Таким чином,

g 1 = 3 ↑↑ (3 ↑↑ (3 ↑↑ ... (3 ↑↑ 3) ...)) {\ displaystyle g_ {1} = 3 \ uparrow \ uparrow (3 \ uparrow \ uparrow (3 \ uparrow \ uparrow \ \ dots \ (3 \ uparrow \ uparrow 3) \ dots))} , Де кількість трійок - 3 ↑↑ (3 ↑↑ 3) {\ displaystyle 3 \ uparrow \ uparrow (3 \ uparrow \ uparrow 3)} .

Воно може бути записано на мові ступенів:

g 1 = 3 3 ⋅ ⋅ ⋅ ⋅ 3} 3 3 ⋅ ⋅ ⋅ 3} ... 3 3 3} 3 {\ displaystyle g_ {1} = \ left. {\ begin {matrix} 3 ^ {3 ^ {\ cdot ^ {\ cdot ^ {\ cdot ^ {\ cdot ^ {3}}}}}} \ end {matrix}} \ right \} \ left. {\ begin {matrix} 3 ^ {3 ^ {\ cdot ^ {\ cdot ^ {\ cdot ^ {3}}}}} \ end {matrix}} \ right \} \ dots \ left. {\ begin {matrix} 3 ^ {3 ^ {3}} \ end {matrix}} \ right \} 3 \ quad} , Де число веж - 3 3 ⋅ ⋅ ⋅ 3} 3 3 3} 3 {\ displaystyle \ quad \ left. {\ Begin {matrix} 3 ^ {3 ^ {\ cdot ^ {\ cdot ^ {\ cdot ^ {3 }}}}} \ end {matrix}} \ right \} \ left. {\ begin {matrix} 3 ^ {3 ^ {3}} \ end {matrix}} \ right \} 3} ,

де кількість трійок в кожній вежі, починаючи зліва, вказується попередньої вежею.

Іншими словами, g 1 {\ displaystyle g_ {1}} обчислюється шляхом обчислення кількості веж, n = 3 3 ⋅ ⋅ ⋅ 3 {\ displaystyle n = 3 ^ {3 ^ {\ cdot ^ {\ cdot ^ {\ cdot ^ {3}}}}}} (Де число трійок - 3 3 3 {\ displaystyle 3 ^ {3 ^ {3}}} = 7 625 597 484 987), і потім обчислення n {\ displaystyle n} веж в наступному порядку:

1-я вежа: 3

2-я вежа: 3 ↑ 3 ↑ 3 (кількість трійок - 3) = 7 625 597 484 987

3-тя вежа: 3 ↑ 3 ↑ 3 ↑ 3 ↑ ... ↑ 3 (кількість трійок - 7 625 597 484 987) = ...

.

.

.

g 1 {\ displaystyle g_ {1}} = N {\ displaystyle n} -я вежа: 3 ↑ 3 ↑ 3 ↑ 3 ↑ 3 ↑ 3 ↑ 3 ↑ ... ↑ 3 (кількість трійок задається результатом обчислення (n - 1) {\ displaystyle (n-1)} -й вежі)

Масштаб першого члена, g 1 {\ displaystyle g_ {1}} , Настільки великий, що його практично неможливо усвідомити, хоча запис вище відносно проста для розуміння. Хоча n {\ displaystyle n} - це всього лише кількість веж у цій формулі для g 1 {\ displaystyle g_ {1}} , Вже це число значно більше кількості обсягів Планка , Які містяться в спостерігається всесвіту (Приблизно 8, 5 ⋅ 10 185 {\ displaystyle 8 {,} 5 \ cdot 10 ^ {185}} ). Воно вже більше гуголплекс, і вся запис з 7625597484987 трійками вже на третій вежі (так зване "трітрі", Tritri) перетинаються до Сонця, якщо вести запис від Землі. Навіть вежа з чотирма трійками 3 3 3 3 = 3 7 625 597 484 987 ≈ 1, 3 × 10 363 833 4640 024 {\ displaystyle 3 ^ {3 ^ {3 ^ {3}}} = 3 ^ {7 \, 625 \, 597 \, 484 \, 987} \ approx 1 {,} 3 \ times 10 ^ {363 \, 833 \, 4640 \, 024}} вже занадто велике, щоб представити його безпосередньо. Після першого члена нас очікують ще 63 члена стрімко зростаючої послідовності.

• Graham, RL; Rothschild, BL Ramsey's Theorem for n-Parameter Sets (англ.) // Transactions of the American Mathematical Society . - 1971. - Vol. 159. - P. 257-292. - DOI : 10.2307 / 1996010 . The explicit formula for N appears on p. 290.
• Graham, RL; Rothschild, BL (1978). «Ramsey Theory», Studies in Combinatorics, Rota, G.-G., ed., Mathematical Association of America , 17: 80-99. On p. 90, in stating «the best available estimate» for the solution, the explicit formula for N is repeated from the 1971 paper.
• Gardner, Martin. Mathematical Games (англ.) // Scientific American . - Springer Nature (Англ.), 1977. - November (vol. 237). - P. 18-28.; reprinted (revised 2001) in the following book:
• Gardner, Martin. The Colossal Book of Mathematics: Classic Puzzles, Paradoxes, and Problems. - New York, NY: Norton, 2001. - ISBN 0393020231 .
• Gardner, Martin. Penrose Tiles to Trapdoor Ciphers. - Washington, DC: Mathematical Association of America , 1989. - ISBN 0-88385-521-6 .
• Exoo, Geoffrey. A Euclidean Ramsey Problem (неопр.) // Discrete Computational Geometry. - 2003. - Т. 29. - С. 223-227. - DOI : 10.1007 / s00454-002-0780-5 .