Число Грэма

Материал из Неолурк, народный Lurkmore
Перейти к навигации Перейти к поиску
Если долго всматриваться в бездну, бездна начнёт всматриваться в тебя.
Graham black hole.jpg

Число Грэма (число Грехема, англ. Graham’s number) — ебически огромное число, которое вывел внезапно Рональд Грэм как верхний предел в хуй никому не упёршейся проблемы с раскрашенными гиперкубами из теории Рамсея. То есть, предупреждая вопросы отдельных личностей «почему именно столько, а не столько плюс адын» — это не просто взятая от балды величина, это решение конкретной задачи.

Суть[править]

Снизу — то, как не должно быть

Проблема с кубами в теории Рамсея состоит в том, что это никакая не проблема, а одна из задач в комбинаторике, где любят переставлять или красить мелкие части одного большого множества и смотреть, что интересного может получиться. В нашем случае предлагается взять n-мерный кубик, соединить его вершины линиями, и каждое получившееся ребро покрасить одним цветом из двух — либо синим, либо красным. Суть в том, чтобы понять, до какого значения n можно, по-разному закрашивая рёбра, избежать ситуации, когда одна плоскость в кубе закрашена одним цветом. То есть, мы не хотим, чтобы получался одноцветный конвертик, как на картинке. Математики посидели-позакрашивали — видят, что в обычном кубике это сделать легче лёгкого. Добавили ещё измерение (получился тессеракт), снова позакрашивали — получилось, избежать конвертика можно. Добавили пятое, шестое, седьмое — всё отлично! Но тут пришёл Грэм и сказал, что они занимаются хуитой, и он-де сразу сейчас посчитает, при каком количестве измерений одноцветный конвертик будет получаться по-любому. ИЧСХ, посчитал-таки, однако искомым решением это назвать нельзя.

Дело в том, что теорема предлагает найти наименьшее количество измерений с нарушением условия появления одноцветной плоскости. Но хитрый Грэм подумал и решил, что считать по порядку никакого терпения не хватит. Он подозревал, что количество измерений будет большим, но не бесконечным, поэтому, применив специальное кунг-фу из комбинаторики, посчитал сразу максимальное количество этих самых измерений. Этим приёмом он не нашёл решения теоремы, но обозначил верхнюю границу поисков. То есть, если вдруг начнёте решать эту задачу с гиперкубами, то размерности больше числа Грэма можете не брать. И на сегодняшний день та самая минимальная размерность гиперкуба лежит между 13-ю измерениями и, собственно, числом Грэма. Таким образом, число Грэма — это верхний предел количества измерений гиперкуба, при котором точно невозможно избежать подграфа, закрашенного одним цветом.

Популярность[править]

Хотя ныне в математике используются числа, которые в 100500 раз больше, чем число Грэма, все они не настолько известны по ряду причин. Во-первых, на число Грэма обратил внимание широкой публики такой популяризатор матана, как Мартин Гарднер, написав колонку в научном журнале, где сказал, что Грэм совсем охуел придумывать такие числа. А в 1980 году число и вовсе попало в книгу рекордов Гиннесса, где ему был приписан рекорд как самому большому числу, когда-либо использовавшемуся в математическом доказательстве. В довесок ко всему, сам «способ» вычисления этой величины довольно понятен простому смертному (это просто перемноженные по несложному алгоритму тройки). После этого все мало-мальски знакомые с матаном стали фапать на это число, пытаясь как-то представить себе и объяснить другим масштаб этого числа. Но не тут-то было

Доступное разъяснение
Формальная запись для самых любознательных

Эпичность[править]

…, ведь число риальнэ БОЛЬШОЕ. Нет, правда. На самом деле, оно больше любых самых смелых фантазий. Представьте себе цифру, написанную самым мелким шрифтом. Таким мелким, что на атоме можно нарисовать миллионы таких цифр. Представьте себе пространство, заполненное этими цифрами во всех трёх измерениях, вплотную друг к другу. Так вот, места, чтобы вместить десятичную запись числа Грэма, потребуется гораздо больше всей наблюдаемой Вселенной. Мало того, оно не вместится даже в количество Вселенных, равное количеству цифр, помещённых в нашу Вселенную. И так далее… ну ты понел. Продолжать можно, пока клавиатура не сотрётся. А когда сотрётся, сходить за новой и убить тоже. Кстати, до сих пор мы говорили только о количестве цифр, из которых состоит число Грэма, а не о самом числе (например, миллиард секунд — это почти 32 года, но в самом числе «миллиард» всего 10 цифр, которые можно пересчитать за 10 секунд)! Никакие гуголы с гуголплексами тут даже рядом не стояли.

Но все эти эпитеты и аналогии всё равно не отражают масштаба трагедии. По-настоящему заклинить свой МНУ ты можешь, попытавшись вникнуть в принцип вычисления этого числа. А чтобы не пугать честной норот простынёй непонятных знаков, мы положим его под половицу.

Глубока ли кроличья нора?
Чтобы хоть как-то представить себе масштаб числа, разберём его запись поподробнее.

1. Итак, в математике существует понятие «гипероператор» для определения уровня арифметических действий. Так, сложение — это гипероператор первого уровня, а гипероператор второго уровня — умножение, которое суть повторяющееся сложение. То есть множитель — это число, которое говорит нам, сколько раз надо сложить умножаемую величину. Например: 3 · 3 = 3 + 3 + 3 = 9. Следующий гипероператор — возведение в степень, xn = х^n, что по сути является повторяющимся умножением. Пример: 33 = 3 · 3 · 3 = 27. Запись 33 в нотации Кнута будет выглядеть как 3↑3. Здесь для ясности следует сказать, что первая цифра в выражении 3↑3 — это значение, с которым мы и производим действие, а количество стрелочек между цифрами — это арифметическое действие; в данном случае одна стрелочка означает возведение в степень. Вторая цифра означает то, в какую степень надо возвести первую цифру (сколько раз перемножить на себя). Соответственно, выражение 7↑4 означает семь в четвёртой степени. Иначе говоря, 7 нужно умножить на 7 четыре раза.

2. Гипероператор четвёртого уровня — тетрация, повторяющееся возведение в степень. В записи Кнута — две стрелки между цифрами. Пример: 3↑↑3 = 33 = 333 = 327 = 7 625 597 484 987. То есть вторая цифра при наличии двух стрелок означает, что столько раз нужно возвести в степень самого себя первое число. Другими словами, показывает нам высоту степенной башни из первой цифры. Например, запись 5↑↑8 означает башню из восьми пятёрок, нагромождённых друг на друга, как кубики.

Тем, чей мозг совсем заплыл жиром или занят лишь мыслями о том, как найти тян, вкачать своего эльфа или избавиться от прыщей, следует запомнить, что в тетрации выражения высчитываются сверху вниз, или справа налево. Проще говоря, 333 равняется нихуя не 273, а как раз-таки 327. Теперь ты видишь, мой маленький мохнатый друг, что тетрация — уже довольно мощный способ записи, позволяющий коротеньким выражением записывать числа в 100500 раз бо́льшие, чем само 100500. Но это ещё не всё, ибо она является недостаточно мощным гипероператором для вычисления числа Грэма.

3. Идём дальше: гипероператор пятого уровня — пентация (повторяющаяся тетрация). Три стрелочки между цифрами. Вот здесь-то и начинается пиздец, от которого люди, не являющиеся профессиональными математиками, плюют на всю эту лабуду и больше не пытаются её понять. Но ведь ты не такой, как они? Если ты подумал, что пентация числа 3 раскладывается на 3 в степени 7 625 597 484 987, то ты ошибаешься. Ты даже не представляешь, НАСКОЛЬКО ошибаешься. Ибо 3 в степени 7 625 597 484 987 — это всего лишь 3↑↑4. А пентация — это 3↑↑↑3 = 3↑↑(3↑↑3) = 3↑↑(7 625 597 484 987) = 3↑3…(количество возведений в степень — 7 625 597 484 987 раз)…↑3. То есть, степенная башня из троек получается высотой в более чем семь с половиной триллионов этажей! Иначе говоря, вторая цифра при наличии трёх стрелочек означает, какой высоты будет башня тетраций первой цифры. Для большей наглядности: 3↑↑↑4 можно записать как 3333, либо 3 ↑↑ (3 ↑↑ (3 ↑↑ 3)). И здесь главное — понять, что эта башня из тетраций не есть башня из степеней, тут эскалация намного стремительнее. 3↑↑↑4 = 3333 = 7 625 597 484 98733.
Понял, наконец, сука?! 3↑↑↑4 равняется 3 в тетрации числа, которое получается в результате вычисления степенной башни из цифры 3 высотой в 7 625 597 484 987 этажей. Соответственно, если 3↑↑↑4 записать как степенную башню из троек, то количество этажей в этой башне будет равняться числу, которое получится при вычислении степенной башни высотой в 7 625 597 484 987 этажей. Представил? Не представил, конечно, такие величины с наскоку не осмыслить.

Если ты всё-таки начал потихоньку не понимать, что за херня здесь происходит, то заново перечитай пункт 2.

4. И последний нужный нам гипероператор — гексация. Как вы уже догадались, четыре стрелочки между тройками. Это, соответственно, повторяющаяся пентация. Вторая цифра при наличии четырёх стрелочек означает, какой высоты будет уже «пентационная» башня. 3↑↑↑↑3 = 3↑↑↑(3↑↑↑3) = 3↑↑3↑↑3…3↑↑3, где количество тетраций — результат вычисления пентации 3↑↑↑3. Если опять ничего не понял, то заново прочитай пункты 3 и 2.
Если мы переместимся в самый конец этой немыслимой цепочки тетраций и начнём её вычислять, то уже вторая с конца тройка будет в тетрации равна 7 625 597 484 987. А результатом тетрации третьей тройки с конца будет число, полученное пентацией тройки в предыдущем пункте. А перед нами — ещё гуголплексы и гуголплексы повторяющихся тетраций цифры 3. Тут уже бесполезно что-то пытаться осмыслить, как-то охватить результат… И тут вы, возможно, спросите: «Неужели это число Грэма? Надо же, насколько громадное!» Но нет, это не число Грэма. Это была только математическая присказка, и она ничтожно, неизмеримо мала по сравнению с числом Грэма.

Стало быть, гексация — это всего лишь добавление к пентации одной ссаной стрелочки, но результат оказывается больше в невообразимое количество порядков. А теперь, собственно, вычисление числа Грэма. Цифра три в примерах была использована не просто так, ибо число Грэма по сути и есть перемноженные тройки. Итак, назовём результат нашей гексации (3↑↑↑↑3) G1. Это какбэ был первый шаг вычислений. Только первый. А следующий шаг ускоряет прогрессию так, что добавление одной, десяти, МИЛЛИОНА стрелок между цифрами — топтание на месте. Шаг второй — вычисление G2: теперь мы берём результат нашей гексации тройки и пишем выражение, где число стрелочек сверхстепени будет равно этому результату. G2 = 3↑↑↑↑↑↑↑↑↑↑↑↑↑↑…(количество стрелочек сверхстепени — G1)…↑↑↑↑↑↑↑3. Интересно, как называется гипероператор ТАКОГО уровня?..

Запись не то что результата, но даже этого гипероператора уже невозможна без сокращения. А число, получившееся при его вычислении (если, конечно, его возможно было бы вычислить), заполнило бы своими цифрами и Вселенную, и параллельные миры, и подпространство, и всяческий другой астрал. И не забываем, что в G1 количество стрелочек было равно четырём — и это уже число, недоступное для вычисления и записи обычным способом! А в G2 это число — только количество сверхстепеней. Вот так-то. Прогрессия невероятно стремительная. И это только начало. Следующим шагом идёт вычисление числа G3, где количество стрелочек сверхстепени будет равно G2! Подобным образом после этого следует ещё 62 шага вычислений, где результат каждого шага будет лишь количеством стрелок сверхстепени следующего шага, и число Грэма есть G64!

Ваистену, матан иногда штырит похлеще любых наркотиков.

Мякотка числа также в том, что, несмотря на невозможность записать число полностью, вполне возможно вычислить его последние цифры. Нерды от матана, сперва немного охуев от масштаба числа, взяли себя в руки и высчитали более 500 цифр с конца этого числа. Вот десять самых последних: …2464195387. А какая цифра первая? Ну, калькулятор вам в руки, только имейте в виду, что тепловая смерть Вселенной прервёт ваши вычисления в самом начале.

Moar[править]

Литлвуд первым расставляет точки

Но время идёт, математики не сидят сложа руки, и невозможное для осознания число Грэма больше не является чем-то особенным. В настоящее время самым большим числом является величина под названием «Число Райо» (Rayo’s number). У него даже есть формула и алгоритм вычисления, только вот посчитать как-то не удаётся: мощностей не хватает (и вряд ли когда-нибудь хватит). Поэтому, чтобы хоть как-то его определять, для него придумали следующую языковую конструкцию: «Самое маленькое число, большее, чем любое конечное число, определённое выражением на языке теории множеств с использованием гугола символов или меньше». Аплодисменты.

UPD: И даже число Райо уже не самое большое. Математик Джонатан Бауэрс таки смог его переплюнуть, придумав функцию, дающую число, которое он назвал Utter Oblivion. Однако тру-гугологи говорят нам, что это число с помощью придуманных Бауэрсом конструкций определяется как-то нечётко, поэтому его превосходит число под названием LNGN (Large Number Garden Number), имеющее формулу F10(10↑1010).

Видеота[править]

Годное видео про сабж. Видеоряд доставляет...
О сабже с 18-й минуты

Интересные факты[править]

  • Онотоле знает все цифры этого числа. Но вам не скажет.
  • Результат степенной башни из гуголплексов в гуголплекс этажей неизмеримо меньше числа Грэма.

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

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

Eipi10.gif Хехехеххехехе. Пожилой математик одобряет
НаукиЛогика (Второй семестр) • Высшая математикаФизикаЕвгеникаМатанРоссийскаяСопроматСтатистикаФилософия (Детерминизм) • Бремя доказыванияЗнатствоМногие знания, многие печалиПритча про слепых и слонаБиологияПердун и ворВ глубине науки скрывается богословиеОсновной вопрос философии
ДостиженияTeXАтомная бомбаБиореакторБольшой адронный коллайдерГМОДвести двадцатьКорчевательКубик РубикаНанотехнологииПалата мер и весовРезонатор ГельмгольцаРоботыТермоядерный синтезЧернобыльЭкзоскелетФукусимаФракталРулерЦиркульMp3256МозгИзенареллаСверхпроводникиКвантовый интернетДНК-тестКристаллУгольник (Угол) • КвалиаБессознательноеИзобретательПустое множествоИскания под фонарёмДрожжиCRC
Теории и открытияГеометрия ЛобачевскогоЗвездчатый многоугольникКвантовая механикаКогнитивная психологияПопуляционная теория МальтусаРадиацияТёмная энергияТеория большого взрыва (сериалБольшой взрыв — антинаучен) • Теория относительностиТеория разбитых оконТеория струнЧетвёртое измерениеЧёрная дыраЭволюцияЭлементарные частицыЭнтропияЛюбительская астрономияОтношенияЗадачи с недостатком информацииГомбокНеосвещаемая комнатаМногомерные фигурыИсторияМежконтинентальная баллистическая ракетаOutside InЧёрный лебедьРептильный мозгТрансжирыБуриданов осёлНепрерывность сознанияКока-кола и МентосКвантовое бессмертиеВычисление длины акулы по её зубуФундаментальная проблема материализмаИнтерференцияИсхождениеЧистый листНеапокалиптические сценарии будущегоИстины не существуетЦепь МарковаЗадача ДидоныИндекс ХиршаНобелевская премияЭндорфинКалькулятор
Мемы265xkcdБритва ОккамаДеление на ноль (Яценюк) • Дигидрогена монооксидДомино в задачахЗадача Льва ТолстогоЗадача ЭйнштейнаЗакон МерфиЗакон ПаретоКвадратно-гнездовой способ мышленияКвадратура кругаКоробочка фотоновКот ШрёдингераКритерий ПоппераМатановая капчаМатематизацияМетод научного тыкаПик нефтиПоймать льва в пустынеПростые числаРекурсияСферический конь в вакуумеТеорема Абеля — ГалуаВеликая теорема ФермаЧисло ГрэмаЧисло ЭрдёшаСдвиг парадигмыПритча про сранье в лесуСингулярность
Люди и организацииИзябретательИлон МаскГермес Триждывеличайший • Организации (ИТМОМФТИНМУ) • БайронБелоненкоБерезовскийВассерманВербицкийда ВинчиДекартДокинзИнженерКэрроллЛабораторияЛейбницЛуговский (цитатник) • Паскаль • Перельманы (ГригорийЯков) • ПереслегинПятисемитыСаганТейлорТеслаТехнофашистыФейнманХайямХокингЭшерАндрей КурпатовРоджер ПенроузWolfram AlphaАлександр ПушнойСергей ХачатуровЭхнатонЯценюкКульт СингулярностиАрхивариусЖак Ив КустоПрофессор БагировNautilus LiveShark-ReferencesИван ИльинЦЕРНОлег ЗаморинПрофессор
ПаранаукаScience freaks/Научное фричествоScorcher.ruАртефактВеликая тайна водыВечный двигательГомеопатияГСМИнформационное поле ВселеннойКвадратно-гнездовой способ мышленияНаучный креационизм (аргументы) • НЛППринцип АрнольдаСоционикаТелегонияТорсионные поляХУЯСЭлектронный голосовой феноменСколковоАртефакты ПетербургаЮрий Рыбников (Счёт древних шизов) • Странные графикиНевозможные фигурыРадужные каплиВикипедияMagnetic GamesПсихолухСоциотипыНаучпопАнтиизенареллаВлияние мочи на солнечные лучиВасилиск РокоИллюзорность мираПеренос сознанияАнтропогенез.руЦеребральный сортингСмекалочкаПарадоксы путешествий во времениТёмная материяЭрнст Юнгер
Фрики и шарлатаныSherakБританские учёныеБронниковГаряевЖдановКатющикЛотовЛысенкоМалаховМулдашевМухинНиконовОлег Т.ПетрикПротопоповРАЕНСкляровСтерлиговФоменкоЧащихинЧернобровЧудиновЧурляевЧуровКульт наукиХимтрейлыМатематика — злоАндрей ВерёвкинЯценюкСергей СавельевЭкзамены это расизм
СрачиБесполезная наукаВзлетит или не взлетит?Дети индигоЛуносрачНаука vs религияПирамидосрачПлутоносрачФизики vs лирикиШмель летать не долженНольЖизнь коротка, искусство вечноОптическая иллюзияВопрос про возраст капитанаНеопределённостьА что, если?Закат ЕвропыИнтерес людей к акуламПарадокс сотворения мираЭффект Даннинга — Крюгера
Pi image.png Смысл большой в числах — они сильны и велики
Числа и цифры+11.02.0π3,53,628/641314/88161920252834384042515763778086101121128220228265282314322359404410502640646666111111381200+ε133715001812200023003310360537309000/~96001230940 00010050026060213 000 0001 000 000 000 (СталинскийЗолотой) • 1 208 925 819 614 629 174 706 176G64144 00024:00
Проценты90% женщин95% населения (95 простых процентов) • Инфа 100%146%
Время3 секунды5 секундПолшестого7:4010:101917 год1980-е (1984 год) • 1990-е2000-е (2000 год) • 2010-е (2012 год)
Прочее1 Guy 1 Jar2 Girls 1 CupSweet home2 в 13 Guys 1 Hammer58 видов геевАвтомобильные номераГетДЕЕ1991ГРДеление на нольЗакон ПаретоКодМатанМатановая капчаНатуральные числаПростые числаВещественные числаРулеткаСотни нефтиВеликая теорема ФермаТеория относительностиЧуть более, чем наполовинуСемь чудес светаКвадратура кругаТри обезьяныДевушка и пять негров (Piper Perri Surrounded) • Проклятие 7Два срокаDota 25.11.17Дока 2Несчастливые числаСчастливые числа