Введение
Число, придуманное Рональдом Грэмом. Очень большое число, названное в честь Рональда Грэма, — это огромное число, возникшее как верхняя граница ответа на задачу в математической области теории Рамзи. Оно намного больше, чем многие другие большие числа, такие как число Скуэза и число Мозера, оба из которых, в свою очередь, намного больше гуголплекса. Как и в случае с этими числами, оно настолько велико, что наблюдаемая Вселенная слишком мала, чтобы вместить обычное цифровое представление числа Грэма, предполагая, что каждая цифра занимает один объём Планка, возможно, наименьший измеримый объём. Но даже количество цифр в этом цифровом представлении числа Грэма само по себе будет таким огромным числом, что его цифровое представление невозможно уместить в наблюдаемой Вселенной. И даже количество цифр этого числа — и так далее, число раз превышающее общее количество объёмов Планка в наблюдаемой Вселенной. Таким образом, число Грэма нельзя выразить даже степенными башнями масштаба физической Вселенной вида. Однако число Грэма можно явно задать с помощью вычислимых рекурсивных формул, использующих нотацию Кнута со стрелками вверх или эквивалентную ей, как это и сделал Рональд Грэм, именем которого оно названо. Поскольку существует рекурсивная формула для его определения, оно намного меньше, чем типичные числа занятых бобров, последние из которых растут быстрее, чем любая вычислимая последовательность. Хотя оно слишком велико, чтобы когда-либо быть полностью вычислено, последовательность цифр числа Грэма может быть вычислена явно с помощью простых алгоритмов; последние 13 цифр — 7262464195387. Используя нотацию Кнута со стрелками вверх, число Грэма равно , где.
the very large number named after Ronald Graham
Graham's number is an immense number that arose as an upper bound on the answer of a problem in the mathematical field of Ramsey theory. It is much larger than many other large numbers such as Skewes's number and Moser's number, both of which are in turn much larger than a googolplex. As with these, it is so large that the observable universe is far too small to contain an ordinary digital representation of Graham's number, assuming that each digit occupies one Planck volume, possibly the smallest measurable space. But even the number of digits in this digital representation of Graham's number would itself be a number so large that its digital representation cannot be represented in the observable universe. Nor even can the number of digits of that number—and so forth, for a number of times far exceeding the total number of Planck volumes in the observable universe. Thus Graham's number cannot be expressed even by physical universe scale power towers of the form
However, Graham's number can be explicitly given by computable recursive formulas using Knuth's up arrow notation or equivalent, as was done by Ronald Graham, the number's namesake. As there is a recursive formula to define it, it is much smaller than typical busy beaver numbers, the latter of which grow faster than any computable sequence. Though too large to ever be computed in full, the sequence of digits of Graham's number can be computed explicitly via simple algorithms; the last 13 digits are 7262464195387. Using Knuth's up arrow notation, Graham's number is , where
Число Грэма использовалось Грэмом в беседах с популяризатором науки Мартином Гарднером в качестве упрощённого объяснения верхней границы задачи, над которой он работал. В 1977 году Гарднер описал это число в журнале Scientific American, представив его широкой публике. На момент представления оно было самым большим конкретным положительным целым числом, когда-либо использованным в опубликованном математическом доказательстве. В 1980 году число было описано в Книге рекордов Гиннеса, что способствовало его популярности. Другие конкретные целые числа (например, TREE(3)), известные как значительно большие числа Грэма, с тех пор появились во многих серьёзных математических доказательствах, например, в связи с различными конечными формами теоремы Крускаля Харви Фридмана. Кроме того, более строгие верхние границы для задачи теории Рамзи, из которой было получено число Грэма, впоследствии были доказаны.
Публикация
Число приобрело известность, когда Мартин Гарднер описал его в разделе «Математические игры» журнала Scientific American в ноябре 1977 года, написав, что Грэм недавно установил в неопубликованном доказательстве «верхнюю границу настолько огромную, что она является рекордной для наибольшего числа, когда-либо использованного в серьезном математическом доказательстве». Книга рекордов Гиннеса 1980 года повторила утверждение Гарднера, что еще больше подогрело интерес к этому числу. По словам физика Джона Баэза, Грэм придумал величину, ныне известную как число Грэма, в беседе с Гарднером. Когда Грэм пытался объяснить результат в теории Рамзи, который он получил совместно со своим коллегой Брюсом Ли Ротшильдом, он обнаружил, что описанная величина легче объясняется, чем фактическое число, фигурирующее в доказательстве. Поскольку число, которое Грэм описал Гарднеру, больше, чем число в самой статье, оба они являются допустимыми верхними границами для решения задачи, изучаемой Грэмом и Ротшильдом.