- Регистрация
- 23 Август 2023
- Сообщения
- 2 984
- Лучшие ответы
- 0
- Реакции
- 0
- Баллы
- 51
Offline
Наверное, все слышали хотя бы в общих чертах про число Лоудера, очень большого гугологического монстра. Но если нет, то вкратце Loader's number — это одно из самых больших чисел, когда-либо появившихся в серьёзном математическом контексте, и оно знаменито именно в сообществе гугологов.Оно было получено в 2002 году программистом Ральфом Лоудером в результате работы его программы, которая выиграла соревнование по написанию самой эффективной программы для вывода в Лямбда-исчислении. Почему оно так знаменито и так велико? Не просто "большое", а "максимально эффективное". Программа Лоудера была настолько оптимизирована, что, по мнению многих специалистов, она достигает практического предела мощности для вычислимой функции в рамках Лямбда-исчисления. Она создает число, которое, вероятно, является самым большим вычислимым числом, когда-либо явно описанным с помощью столь компактной программы. Основа - лямбда-исчисление. Это не просто алгоритм, написанный на C++ или Python. Он работает в фундаментальной системе, которая является основой функционального программирования и самой теории вычислимости,что придает числу огромную "математическую плотность". Ну и как вишенка на торте - оно превосходит других гигантов: Число Лоудера невероятно больше, чем многие другие известные "большие числа", такие как распиаренное число Грэма или даже числа, сгенерированные быстрорастущей иерархией на низких уровнях. Его мощность находится на очень высоких ординалах.
Насколько оно велико?
Попытки описать его размер бессмысленны в привычных нам терминах. Даже запись его в виде степенной башни или с помощью стрелочной нотации Кнута заняла бы объём, многократно превосходящий наблюдаемую вселенную. Его "размер" обычно сравнивают с его положением в Иерархии быстрорастущих функций (Fast-growing hierarchy).
Если f_0
= n+1 (примитивная рекурсия), а f_ω уже растет как функция Аккермана, то функция, которая генерирует число Лоудера, по мощности соответствует 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₂
- двойная экспонента для цепочек длины 3+), но это только начало.2. _nested(step, depth, value)
Тройная вложенная рекурсия с самоприменением, создает двойные циклы с вызовами C() и рекурсией по step-1, совокупный рост дает как f{ε₀^ω}
( фиксированная точка ω-уровня). Роль в коде - создает экспоненциальное усиление через вложенность3. re
Удобная рекурсивная обертка над _nested (Самодиагонализация через _nested). Итоговый рост дает как f{ε₀}
- уровень функции Аккермана-Петера.4. hyper_scaling(n, iteration)
Это не что иное, как экспоненциальное масштабирование через башни степеней (n^n итераций с tower(math.e) усилением). По росту можно оценить как f{ω^ω}
- суперэкспоненциальный. Функция существуенно усиливает числа перед построением цепочек5. scale(n, depth)
Ее назначение - рекурсивное масштабирование с адаптивной длиной цепочки (создает цепочки переменной сложности). Длина цепочки определяется рекурсивно через scale(). Вклад в рост: f{ω^ω + ω}
- комбинация масштабирования и рекурсии6. meta_conway(chain, depth, labels) (КЛЮЧЕВАЯ)
В результате meta_conway создаются мета-деревья с динамическими лейблами (аналог TREE). Надо сказать, что это не обертка над известной функцией TREE, а скорее задействование близкого по духу механизма для деревьев, на случай если вдруг появятся мысли обвинить в плагиате
. Механика: Каждый элемент порождает поддеревья с рекурсивными лейблами, а суммарный рост досигает f{φ(ω,0)} - уровень комбинаторных деревьев. В результате - динамические лейблы создают комбинаторный взрыв7. hyper_conway(n, depth)
Самоподдерживающиеся гипер-цепи. labels = boom(n-1) → полная циклическая зависимость, что позволяет получить итеративное самоусиление (for s in range(strong_chain)) и выйти на темп роста быстрорастущей иерархии уровня f{θ(Ω^Ω)}
- коллапсирующие ординалы или что-то вроде того.8. C
(этакий центральный хаб)Представляет собой Универсальный усилитель, создающий рекурсивные итерации C(n-1) с усилением chain_up. Суммарный рост оценивается как f{φ(Γ₁,0)}
-по сути композиция всех механизмов усиления. Также он связывает все компоненты программы.9. boom(n, depth, mode)
Точка входа и функционально финальная мета-рекурсивная функция. Три режима (init/iter/boom) с каскадными вызовами. Глубина рекурсии = C(re
) - самоподдерживающаяся, а уровень роста f{θ(ε_{Ω+1})} - ПРЕВЫШАЕТ TREE(3) и SCG(13)Краткое резюме по функциональности
Полная самоподдерживающаяся архитектура - boom → hyper_conway → boom
Мета-деревья с динамическими лейблами - комбинаторный взрыв почти как в TREE
Итеративное самоусиление - цепочки пересоздаются на основе собственных результатов
Многоуровневая диагонализация - re → C → hyper_conway → meta_conway
Рекурсии везде, где можно и нельзя (если очень хочется - то можно)
Уровень | Функция | Ординал | Статус |
|---|---|---|---|
1 | conway_chain | 2 | База |
2 | hyper_scaling | ω^ω | Гипероперации |
3 | re | ε₀ | Самодиагонализация |
4 | meta_conway | φ(ω,0) | TREE-уровень |
5 | hyper_conway | θ(Ω^Ω) | Прорыв |
6 | boom | θ(ε_{Ω+1}) | Превосходит TREE и близок к SCG(13) |
🌌 Зачем это?
Данный код собой представляет концептуальную модель реализации вычислений значений из мира продвинутой гугологии на базовом 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
:if n <= 1:
return n
if n == 2:
return C(_nested(C
, C, C))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
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
)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
) and mode == "init": return nr = n
if mode == "init":
for _ in range(C(re
)):r = C(re(boom(r - 1, depth + 1, "init")))
return r
elif mode == "iter":
cur = boom(C(re
), 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
)):r = C(re(boom(r - 1, depth + 1, "boom")))
cur = r
for step in range(C(re
)):cur = boom(C(re(step)), 0, "boom")
if is_main_boom and n > 1:
for _ in range(boom(C(re
), 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))