132 строчки на Python, которые рождают математического гипермонстра

Наверное, все слышали хотя бы в общих чертах про число Лоудера, очень большого гугологического монстра. Но если нет, то вкратце Loader's number — это одно из самых больших чисел, когда-либо появившихся в серьёзном математическом контексте, и оно знаменито именно в сообществе гугологов.Оно было получено в 2002 году программистом Ральфом Лоудером в результате работы его программы, которая выиграла соревнование по написанию самой эффективной программы для вывода в Лямбда-исчислении. Почему оно так знаменито и так велико? Не просто "большое", а "максимально эффективное". Программа Лоудера была настолько оптимизирована, что, по мнению многих специалистов, она достигает практического предела мощности для вычислимой функции в рамках Лямбда-исчисления. Она создает число, которое, вероятно, является самым большим вычислимым числом, когда-либо явно описанным с помощью столь компактной программы. Основа - лямбда-исчисление. Это не просто алгоритм, написанный на C++ или Python. Он работает в фундаментальной системе, которая является основой функционального программирования и самой теории вычислимости,что придает числу огромную "математическую плотность". Ну и как вишенка на торте - оно превосходит других гигантов: Число Лоудера невероятно больше, чем многие другие известные "большие числа", такие как распиаренное число Грэма или даже числа, сгенерированные быстрорастущей иерархией на низких уровнях. Его мощность находится на очень высоких ординалах.

Насколько оно велико?

Попытки описать его размер бессмысленны в привычных нам терминах. Даже запись его в виде степенной башни или с помощью стрелочной нотации Кнута заняла бы объём, многократно превосходящий наблюдаемую вселенную. Его "размер" обычно сравнивают с его положением в Иерархии быстрорастущих функций (Fast-growing hierarchy).

Если f_0(n) = n+1 (примитивная рекурсия), а f_?(n) уже растет как функция Аккермана, то функция, которая генерирует число Лоудера, по мощности соответствует f_?(?_?) в иерархии с фундаментальной последовательностью расширенной функции Веблена. Это невероятно высокий и сложный для понимания уровень роста. Резюмируя, в мире гугологии это своего рода "святой грааль" среди вычислимых чисел. Это число, полученное, возможно, самым эффективным из всех придуманных способов, и оно представляет собой практический предел того, насколько большое число можно задать с помощью короткой программы в фундаментальной вычислительной системе, по крайней мере на настоящий момент. Его "сишный" код я приводить не буду, так как он легко гуглится, но приведу свой, и поясню, почему это тоже вычислительный монстр, пусть и не самый "эффективный" и здоровенный численно как вышеописанный гигант, но в "бестиарии гугологических фантастических тварей" может занять место ну точно в первой десятке из известных. Ниже его код, в отличие от кода числа loader, код ниже максимально прост и понятен, но, тем не менее, разберем его последовательно.

Поехали. ? Python BOOM.py

Архитектура

Самоподдерживающаяся рекурсивная система, достигающая ?(?_{?+1}) в иерархии быстрорастущих функций - выше TREE(3) и SCG(13)* (по оценкам роста комментарий будет ниже)

Анализ функций

1. conway_chain(chain)

Вычисляет сonway chained arrow notation, ( [a,b,c] ? a?b?c в нотации Конвея). Это базовый кирпичик моего кода (базовый механизм гиперопераций), рост у него довольно скромный (рост: f?(n) - двойная экспонента для цепочек длины 3+), но это только начало.

2. _nested(step, depth, value)

Тройная вложенная рекурсия с самоприменением, создает двойные циклы с вызовами C() и рекурсией по step-1, совокупный рост дает как f{??^?}(n) ( фиксированная точка ?-уровня). Роль в коде - создает экспоненциальное усиление через вложенность

3. re(n)

Удобная рекурсивная обертка над _nested (Самодиагонализация через _nested). Итоговый рост дает как f{??}(n) - уровень функции Аккермана-Петера.

4. hyper_scaling(n, iteration)

Это не что иное, как экспоненциальное масштабирование через башни степеней (n^n итераций с tower(math.e) усилением). По росту можно оценить как f{?^?}(n) - суперэкспоненциальный. Функция существуенно усиливает числа перед построением цепочек

5. scale(n, depth)

Ее назначение - рекурсивное масштабирование с адаптивной длиной цепочки (создает цепочки переменной сложности). Длина цепочки определяется рекурсивно через scale(). Вклад в рост: f{?^? + ?}(n) - комбинация масштабирования и рекурсии

6. meta_conway(chain, depth, labels) (КЛЮЧЕВАЯ)

В результате meta_conway создаются мета-деревья с динамическими лейблами (аналог TREE). Надо сказать, что это не обертка над известной функцией TREE, а скорее задействование близкого по духу механизма для деревьев, на случай если вдруг появятся мысли обвинить в плагиате :). Механика: Каждый элемент порождает поддеревья с рекурсивными лейблами, а суммарный рост досигает f{?(?,0)}(n) - уровень комбинаторных деревьев. В результате - динамические лейблы создают комбинаторный взрыв

7. hyper_conway(n, depth)

Самоподдерживающиеся гипер-цепи. labels = boom(n-1) ? полная циклическая зависимость, что позволяет получить итеративное самоусиление (for s in range(strong_chain)) и выйти на темп роста быстрорастущей иерархии уровня f{?(?^?)}(n) - коллапсирующие ординалы или что-то вроде того.

8. C(n) (этакий центральный хаб)

Представляет собойУниверсальный усилитель, создающий рекурсивные итерации C(n-1) с усилением chain_up. Суммарный рост оценивается как f{?(??,0)}(n) -по сути композиция всех механизмов усиления. Также он связывает все компоненты программы.

9. boom(n, depth, mode)

Точка входа и функционально финальная мета-рекурсивная функция. Три режима (init/iter/boom) с каскадными вызовами. Глубина рекурсии = C(re(n)) - самоподдерживающаяся, а уровень роста f{?(?_{?+1})}(n) - ПРЕВЫШАЕТ TREE(3) и SCG(13)

Краткое резюме по функциональности

1. Полная самоподдерживающаяся архитектура - boom ? hyper_conway ? boom

2. Мета-деревья с динамическими лейблами - комбинаторный взрыв почти как в TREE

3. Итеративное самоусиление - цепочки пересоздаются на основе собственных результатов

4. Многоуровневая диагонализация - re ? C ? hyper_conway ? meta_conway

5. Рекурсии везде, где можно и нельзя (если очень хочется - то можно) :)

? Таблица сравнений б.-растущих иерархий (FGH)

? Зачем это?

Данный код собой представляет концептуальную модель реализации вычислений значений из мира продвинутой гугологии на базовом python. Разумеется, автор не претендует на какое-то мало мальски значимое достижение в теории вычислений или математики. Цель - показать, как из базовых функций, циклов, и базовой арифметики (ну, по факту чуть более чем базовой - если брать во внимания механизм цепочек Конвея - но не принципиально) без привлечения доп библиотек или сложных построений в 100+ строчках кода можно создавать монстров высшего уровня больших чисел. Запускать код со значением Boom(>=2) если очень хочется - можно, но результата не дождетесь, так как по факту этот код для бесконечной машины Тьюринга. Ну и сам код ниже.

import math from typing import List  def _nested(step: int, depth: int, value: int) -> int:     if step <= 0:         return value     cur = value     for i in range(C(step)):         temp_cur = cur         for j in range(C(step)):             number = C(temp_cur)             temp_cur = _nested(step - 1, depth + 1, C(number))         cur = _nested(step - 1, depth + 1, temp_cur)     return cur  def re(n):     if n <= 1:         return n     if n == 2:         return C(_nested(C(n), C(n), C(n)))     return C(_nested(re(n - 1), re(n - 1), re(n - 1)))  def hyper_scaling(n, iteration=0):     if iteration > n and n > 0:         return n     def scale_map(x, level):         if level == 0:             return x         def tower(h, b=math.e):             return 1 if h <= 0 else b ** tower(h - 1, b)         scale_height = max(1, int(abs(x)))         return tower(scale_height)     cur = n     steps = n ** n     for i in range(steps):         cur_scale = scale_map(cur, i)         next_val = cur ** cur_scale         cur = hyper_scaling(next_val, iteration + 1)     return cur  def scale(n, depth=0):     if depth > n:         return n     scaled_n = hyper_scaling(n)     raw_length = conway_chain([scaled_n] * n)     chain_length = scale(raw_length, depth + 1) or 1     chain = []     for i in range(chain_length):         element = scale(scaled_n + i, depth + 1)         chain.append(element)     return conway_chain(chain)  def hyper_conway(n, depth=0):     if depth > n ** n: return n     labels = boom(n - 1, mode="boom") if n > 1 else n     chain = [meta_conway([n] * n, depth + 1, max_depth=n ** n, labels=labels)] * n     strong_chain = conway_chain(chain)     for s in range(strong_chain):         chain = [meta_conway([strong_chain]*n, depth + 1, max_depth=n ** n, labels=labels)] * n     return conway_chain(chain)  def meta_conway(chain: List[int], depth: int = 1, max_depth: int = None, labels: int = 3) -> int:     if max_depth is None:         max_depth = len(chain) ** len(chain)     if depth > max_depth:         return conway_chain(chain)     if len(chain) == 1:         return conway_chain( [chain[0]] * chain[0])     meta_elements = []     for x in chain:         sub_arrays = []         dynamic_labels = meta_conway([x] * x, depth + 1, max_depth, labels) if x > 1 else labels         for label in range(1, min(dynamic_labels, labels) + 1):             sub_chain = [(x + label)] * (x + label)             sub_val = meta_conway(sub_chain, depth + 1, max_depth, labels - 1 if labels > 1 else 1)             sub_arrays.append(sub_val)         tree_val = conway_chain(sub_arrays)         meta_elements.append(tree_val)     return conway_chain(meta_elements)  def conway_chain(chain: List[int]) -> int:     if len(chain) == 1:         return chain[0]     elif len(chain) == 2:         a, b = chain[0], chain[1]         return a ** b     else:         a, b = chain[0], chain[1]         tail = chain[2:]         if b == 1:             return conway_chain([a] + tail)         else:             inner_chain = [a] + [b - 1] + tail             inner_result = conway_chain(inner_chain)             new_chain = [a, inner_result] + tail[:-1] if len(tail) > 1 else [a, inner_result]             return conway_chain(new_chain)  def C(n: int):     if n <= 1:         return scale(hyper_conway(n))     chain_up = n     for s in range(C(n - 1)):         chain_up = scale(hyper_conway(chain_up))     return chain_up  def boom(n, depth=0, mode="boom", is_main_boom=False):     if n <= 1: return 1     if depth > C(re(n)) and mode == "init": return n     r = n     if mode == "init":         for _ in range(C(re(n))):             r = C(re(boom(r - 1, depth + 1, "init")))         return r     elif mode == "iter":         cur = boom(C(re(n)), 0, "init")         for s in range(C(re(cur))):             cur = boom(C(re(s)), 0, "init")         return cur     else:  # "boom"         for _ in range(C(re(n))):             r = C(re(boom(r - 1, depth + 1, "boom")))         cur = r         for step in range(C(re(n))):             cur = boom(C(re(step)), 0, "boom")         if is_main_boom and n > 1:             for _ in range(boom(C(re(n)), mode="iter")):                 cur = boom(C(re(cur)), mode="boom", is_main_boom=False)         return cur  if __name__ == "__main__":     print(boom(1, mode="boom", is_main_boom=True))