главная новое лучшее написать
2

Ответ спасен из Яндекс.Кью

Число Грэма это не самое большое число в мире, это "самое большое натуральное число, когда-либо использовавшееся в серьезном математическом доказательстве". Грэм это фамилия, кстати, а не сокращение, писать его БОЛЬШИМИ БУКВАМИ не имеет смысла.

Как уже написали в другом ответе, изобрести число больше тривиально, например, прибавить к числу Грэма любое другое натуральное число, или умножить его на что-нибудь, или в квадрат возвести, да мало ли операций над натуральными числами.

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

Эта конструкция называется Busy Beaver, и строится она так:

Возьмем какой-нибудь язык программирования. Возьмём все возможные программы на этом языке длины не более N байт. Их конечное число: в самом деле, их точно не более 256^N. Большая часть из них вообще не запустится, часть запустится и ничего не выдаст, или выдаст какой-то бред, или ошибку, часть зациклится, а какие-то программы выдадут в итоге некое число. Поскольку программ всего конечное количество, будет конечным и множество всех чисел, которые мы можем так получить. Максимальное из этих чисел назовём BusyBeaver(N).

(я здесь упрощаю, язык программирования в исходном определении не любой, а вполне конкретный, машины Тьюринга, и "символов" у них нет, но всё это не принципиально)

Последовательность BusyBeaver с ростом N растёт катастрофически быстро. Даже просто оценить, насколько быстро она растёт, буквально невозможно. В самом деле, допустим, мы нашли формулу, ограничивающую её рост. Ну, например, BusyBeaver(N) < 256^N^N^N^N. Запишем эту формулу в виде программы. Пусть эта программа займет M символов. Выберем N такое, что N > M+lg(N) (чтобы запись числа N тоже уместилась в ту же программу) и посчитаем с помощью неё оценку BusyBeaver(N). Ого, мы пришли к противоречию: программа длины M+lg(N) выдала число больше, чем BusyBeaver(N)!

То есть какое бы мы ни придумали определение "последовательности Очень Больших чисел", которое можно записать в виде вычислимой процедуры, BusyBeaver всё равно растёт быстрее.

Небольшое отступление. Так, стоп, что-то здесь не то, почему это не противоречие? Вот возьмем и определим SmizzyBeaver(N) = BusyBeaver(N)+1, она ещё быстрее будет расти.

Это не противоречие, потому что последовательность BusyBeaver невычислима. Буквально не существует процедуры, позволяющей взять N и вычислить BusyBeaver(N) (поэтому эти числа известны только для очень маленьких N).

Ну вот, после того, как всё сказано: ответ на исходный вопрос простой, запишите вычисление числа Грэма в виде программки и возьмите BusyBeaver(длины этой программки), это число будет больше не только числа Грэма, но и любых чисел, которые можно вычислить программой той же сложности. BusyBeaver(не очень-то большого числа, соответствующего пределу рабочей памяти человека) представить себе буквально невозможно.