Число Грэма

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

Число Грэма (англ. Graham's number) — гигантское число, которое является верхней границей для решения определённой проблемы в теории Рамсея. Является некоторой очень большой степенью тройки, которая записывается с помощью нотации Кнута. Названо в честь Рональда Грэма.

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

В 1980 году Книга рекордов Гиннесса повторила утверждения Гарднера, ещё больше подогрев интерес публики к этому числу. Число Грэма в невообразимое количество раз больше, чем другие хорошо известные большие числа, такие, как гугол, гуголплекс и даже больше, чем число Скьюза и число Мозера. Вся наблюдаемая вселенная слишком мала для того, чтобы вместить в себя обыкновенную десятичную запись числа Грэма (предполагается, что запись каждой цифры занимает по меньшей мере объём Планка). Даже степенные башни вида бесполезны для этой цели (в том же смысле), хотя это число и может быть записано с использованием рекурсивных формул, таких, как нотация Кнута или эквивалентных, что и было сделано Грэмом. Последние 500 цифр числа Грэма — это

...02425950695064738395657479136519351798334535362521
   43003540126026771622672160419810652263169355188780
   38814483140652526168785095552646051071172000997092
   91249544378887496062882911725063001303622934916080
   25459461494578871427832350829242102091825896753560
   43086993801689249889268099510169055919951195027887
   17830837018340236474548882222161573228010132974509
   27344594504343300901096928025352751833289884461508
   94042482650181938515625357963996189939679054966380
   03222348723967018485186439059104575627262464195387.

В современных математических доказательствах иногда встречаются числа, ещё много бо́льшие, чем число Грэма, например, в работе с конечной формой Фридмана в теореме Краскала — так называемое TREE(3).

Проблема Грэма[править | править код]

Пример: 2 цвета и 3-мерный куб, содержащий один одноцветный 4-вершинный копланарный полный подграф. Подграф показан ниже куба. Этот куб не будет содержать такой подграф, если, например, нижний край у настоящего подграфа будет заменен на синий — что доказывает с помощью контрпримера, что N* > 3.

Число Грэма связано со следующей проблемой в теории Рамсея:

Рассмотрим -мерный гиперкуб и соединим все пары вершин для получения полного графа с вершинами. Раскрасим каждое ребро этого графа либо в красный, либо в синий цвет. При каком наименьшем значении каждая такая раскраска обязательно содержит раскрашенный в один цвет полный подграф с четырьмя вершинами, все из которых лежат в одной плоскости?

Грэм и Ротшильд в 1971 году доказали, что эта проблема имеет решение, , и показали, что , где  — конкретное, точно определённое, очень большое число. На языке стрелочной нотации Кнута оно может быть записано как , где . Это число именуется как «малое число Грэма» (англ. Little Graham).

Нижняя граница была улучшена Экзу в 2003 году и Баркли в 2008 году, который показал, что должно быть не меньше 13. Потом последовало и улучшение верхней границы до и затем до . Таким образом, .

Предметом настоящей статьи является верхняя граница , которая много слабее (то есть больше), чем : , где . Именно эта граница, описанная в неопубликованной работе Грэма, и была описана (и названа числом Грэма) Мартином Гарднером.

Определение числа Грэма[править | править код]

При использовании Стрелочной нотации Кнута число Грэма G может быть записано как

,

где количество стрелок в каждом слое, начиная с верхнего, определяется числом в следующем слое, то есть

где

где верхний индекс у стрелки показывает общее количество стрелок. Другими словами, вычисляется в 64 шага: на первом шаге мы вычисляем с четырьмя стрелками между тройками, на втором — с стрелками между тройками, на третьем — с стрелками между тройками и так далее; в конце мы вычисляем с стрелок между тройками.

Это может быть записано как

, где

где верхний индекс у означает итерации функций. Функция является частным случаем гипероператоров и может также быть записана при помощи цепных стрелок Конвея как . Последняя запись также позволяет записать следующие граничные значения для :

С помощью массивной нотации Бауэрса границы числа Грэма можно записать как:

{3,64,1,2} < G < {3,65,1,2}.

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

Для того чтобы осознать размер числа Грэма, полезно попробовать представить через возведение в степень хотя бы первый член (g1) стремительно растущей 64-членной последовательности (т. н. «грааль», Grahal). На языке тетраций означает:

,

где число троек в выражении справа

Теперь каждая тетрация () по определению разворачивается в «степенную башню» как

, где X — количество троек.

Таким образом,

, где количество троек — .

Оно может быть записано на языке степеней:

, где число башен — ,

где количество троек в каждой башне, начиная слева, указывается предыдущей башней.

Другими словами, вычисляется путём вычисления количества башен, (где число троек — = 7 625 597 484 987), и затем вычисления башен в следующем порядке:

1-я башня: 3

2-я башня: 3↑3↑3 (количество троек — 3) = 7 625 597 484 987

3-я башня: 3↑3↑3↑3↑…↑3 (количество троек — 7 625 597 484 987) = …

.

.

.

= -я башня: 3↑3↑3↑3↑3↑3↑3↑…↑3 (количество троек задаётся результатом вычисления -й башни)

Масштаб первого члена, , настолько велик, что его практически невозможно осознать, хотя запись выше относительно проста для понимания. Хотя  — это всего лишь количество башен в этой формуле для , уже это число много больше количества объёмов Планка, которые содержатся в наблюдаемой вселенной (примерно ). Оно уже больше гуголплекса, и вся запись с 7625597484987 тройками уже на третьей башне (так называемое «тритри», Tritri) будет занимать расстояние от Земли до Солнца. Даже башня с четырьмя тройками представляет собой уже слишком большое число, чтобы представить его непосредственно. После первого члена нас ожидают ещё 63 члена стремительно растущей последовательности.

См. также[править | править код]

Литература[править | править код]

Ссылки[править | править код]