Открыть сервисСервис

Число Грэма

Число Грэма — верхняя граница, предложенная математиком Роном Грэмом в 1971 году для решения задачи о гиперкубе. Значение числа настолько велико, что его невозможно записать в стандартной десятичной системе счисления, а для его обозначения используются специальные многократно вложенные операции, такие как стрелочная нотация Кнута и функция Акермана. Число Грэма считается одним из самых больших чисел, когда-либо использованных в серьёзных математических доказательствах.

История

Число было введено в 1971 году американским математиком Рональдом Грэмом (Ronald Graham, 1935—2020) в ходе работы над комбинаторной задачей, связанной с гиперкубом. Задача была сформулирована в статье, посвящённой проблеме Рамсея, и опубликована в 1977 году в соавторстве с Джозефом Бёркхардтом и Элвином С. Ротом. Грэм доказал, что для определённого конечного графа, построенного на вершинах n-мерного гиперкуба, при определённых условиях раскраски его рёбер число вершин, при котором гарантировано появление одноцветного полного подграфа, не превышает некоторого числа G. Это число и получило название «число Грэма».

Задача формулируется следующим образом: каждая пара вершин n-мерного гиперкуба соединяется рёбром, и каждое ребро раскрашивается в один из четырёх цветов. Требуется найти минимальное n, при котором при любой раскраске обязательно существует одноцветный полный подграф на четырёх вершинах. Грэм доказал, что такое n существует и не превышает определённого числа, которое впоследствии стало известно как число Грэма.

Способы записи

Число Грэма настолько велико, что его невозможно представить в виде обычного числа с конечным числом цифр. Для его записи используются иерархические конструкции.

Стрелочная нотация

Стрелочная нотация Кнута позволяет записывать гипероперации компактно. Одна стрелка обозначает возведение в степень, две стрелки — тетрацию (повторённое возведение в степень), три стрелки — пентацию и так далее. Число Грэма можно записать как многократно вложенную конструкцию из стрелок, где количество стрелок определяется предыдущим уровнем вложенности.

Функция Акермана

Функция Акермана — рекурсивная функция, растущая быстрее любого примитивно-рекурсивного числа. Число Грэма можно выразить через функцию Акермана с определёнными аргументами, причём уровень вложенности функции также определяется предыдущим уровнем.

Конкретная запись

Число Грэма можно описать следующим образом. Пусть g₁ = 3↑↑↑↑3 (где ↑↑↑↑ — гипероперация с четырьмя стрелками). Затем g₂ = 3↑^(g₁)3, где количество стрелок равно g₁. Далее g₃ = 3↑^(g₂)3, и так далее. Число Грэма равно g₆₄, то есть результату 64-кратного применения этой процедуры. Каждый следующий уровень gᵢ определяется предыдущим, и уже g₂ представляет собой число, которое невозможно записать в виде обычного числа с конечным числом цифр.

Сравнение с другими большими числами

Число Грэма значительно превосходит многие известные большие числа, такие как число Скьюса, число Мозера и число Грэма-Рамсея. Оно также значительно больше числа Грэма, используемого в других контекстах, таких как число Грэма в теории Рамсея.

ЧислоПриближённая величина
10¹⁰⁰ (гугол)10¹⁰⁰
10^(10^100) (гуголплекс)10^(10^100)
Число Мозера10^(10^(10^...))
Число Грэмаg₆₄

Значение

Число Грэма стало символом того, насколько огромными могут быть числа, возникающие в математике. Оно широко используется в популяризации математики и в литературе, посвящённой большим числам. В 2014 году число Грэма было включено в Книгу рекордов Гиннесса как одно из самых больших чисел, когда-либо использованных в серьёзных математических доказательствах.

Интересные факты

  • Рон Грэм был не только математиком, но и профессиональным жонглёром. Он установил рекорд, продержавшийся много лет, по количеству одновременно жонглируемых объектов.
  • Грэм был женат на писательнице и математике Фанни Грэм (Fanny Graham).
  • Число Грэма было упомянуто в книге «Числа: Руководство по числам» (The Book of Numbers) Джона Конвея и Ричарда Гая.

Источники

  • Graham R. L., Rothschild B. L., Spencer J. H. Ramsey Theory. — New York: John Wiley & Sons, 1980.
  • Conway J. H., Guy R. K. The Book of Numbers. — New York: Copernicus, 1996.
  • Weisstein E. W. Graham's Number // MathWorld — A Wolfram Web Resource.
Заметили ошибку или не согласны с информацией в статье? Напишите нам support@bfometr.ru