Czy zajęty bóbr to najszybciej rosnąca funkcja znana człowiekowi?

Właśnie miałem to interesujące pytanie. Jaka jest najszybciej rosnąca funkcja znana człowiekowi? Czy to zajęty bóbr ?

Znamy funkcje takie jak $x^2$ , ale ta funkcja rośnie wolniej niż $2^x$ , co z kolei rośnie wolniej niż, który z kolei rośnie wolniej niż . Następnie możemy łączyć funkcje, aby miećktóry rośnie szybciej niż i tak dalej.$x!$$x^x$$(x^x)!$$x^x$

Następnie dochodzimy do funkcji rekurencyjnych, takich jak funkcja Ackermanna która rośnie znacznie szybciej niż. Potem ludzie zastanawiają się nad zajętą funkcją bobra która rośnie nawet szybciej niż funkcja Ackermanna.$A(x,x)$$(x^x)!$$B(x)$

W tym momencie nie słyszałem o żadnych innych funkcjach, które rosłyby szybciej niż zajęty bóbr. Czy to oznacza, że ​​nie ma innych funkcji, które mogłyby rosnąć szybciej niż zajęty bóbr? (Poza silnią i podobną do itp.)$B(x)$$A(B(x), B(x))$

Zajęty bóbr rośnie szybciej niż jakakolwiek funkcja obliczalna . Można go jednak obliczyć za pomocą maszyny Turinga, która otrzymała dostęp do wyroczni w celu rozwiązania problemu zatrzymania. Następnie można zdefiniować funkcję bobra zajętego „drugiego rzędu”, która rośnie szybciej niż jakakolwiek funkcja, która może być obliczona nawet przez dowolną maszynę Turinga z wyrocznią dotyczącą problemu zatrzymania. Możesz to robić wiecznie, budując hierarchię coraz szybciej rozwijających się funkcji bobra.

Zobacz doskonały esej Scotta Aaronsona na ten temat: Kto może wymienić większą liczbę? .

Nie ma czegoś takiego jak „najszybciej rosnąca funkcja”. W rzeczywistości nie ma nawet sekwencji najszybciej rosnących funkcji. Zostało to już pokazane przez Hausdorffa. Biorąc pod uwagę dwie funkcje , powiedzmy, że g rośnie szybciej niż f, jeśli lim n → ∞ g ( n $f,g\colon \mathbb{N} \longrightarrow \mathbb{N}$$g$$f$ Biorąc pod uwagę funkcjęf, następująca funkcjagrośnie szybciej niżf:g(n)=nf(n). Biorąc pod uwagę sekwencję funkcjifn, następująca funkcjagrośnie szybciej niż wszystkie:g(n)=nmaxm≤nfm(n)

$$\lim_{n\rightarrow\infty} \frac{g(n)}{f(n)} = \infty.$$ $f$$g$$f$ $$g(n) = nf(n).$$ $f_n$$g$ $$g(n) = n \max_{m \leq n} f_m(n).$$ Naturalnym pytaniem jest to, czy istnieje „skala” najszybciej rosnących funkcji. Jest to dobrze uporządkowany zestaw funkcji który jest „cofinal”, co oznacza, że ​​przy dowolnej funkcji f istnieje szybciej rosnąca funkcja g α . (Zamiast dobrze uporządkowanego zestawu, możemy w równoważny sposób mówić o łańcuchu, to znaczy, że dowolne dwie funkcje w zestawie muszą być porównywalne.) Istnienie skali jest niezależne od ZFC: zakładając, że CH, istnieje skala, natomiast w modelu Cohena że fałszuje CH (dodanie ω 1 Real) nie istnieje waga.$g_\alpha$$f$$g_\alpha$$\omega_1$

Inne odpowiedzi odnoszą się bezpośrednio do pytania. Aby uzyskać więcej i głębsze tło, ten artykuł autorstwa Lafitte na ten temat rozważa szerszy kontekst zajętych funkcji podobnych do bobrów. Ma również pewne wyniki i twierdzenia pasujące do pomysłu w bardziej ogólnych ramach. Pokazuje, że (nieformalnie) „zajęte funkcje podobne do bobrów” mają ścisły związek ze zjawiskiem niekompletności Chaitin (Twierdzenie 2.1). Pokazuje także, że istnieją teorie, które nie są „wystarczająco mocne”, aby „zrozumieć” zajęte funkcje podobne do bobrów, tj. Są nie do udowodnienia w tych teoriach z powodu niekompletności związanej z Godlem. Pokazuje ideę zakładania zajętych wyników podobnych do bobrów jako aksjomatów i logicznego postępu teorii, które dają wyniki podobne do pomysłów pierwotnie przewidzianych przez Turinga.

[1] Zajęte bobry oszalały przez Grégory Lafitte. Abstrakcyjny:

Pokazujemy niektóre wyniki niekompletności à la Chaitin przy użyciu zajętych funkcji bobra. Następnie, za pomocą logiki porządkowej, pokazujemy, jak uzyskać teorię, w której można ustalić wartości zajętych funkcji bobra, i wykorzystać to do ujawnienia struktury sprawdzalności wartości tych funkcji.

Twierdzenia o hierarchii czasu i przestrzeni Hartmanisa-Stearnsa dowodzą, że nie ma funkcji „najszybciej rosnącej” pod względem czasu lub przestrzeni, ponieważ skala jest nieograniczona. Ale daje takie uporządkowanie , że można porównać wszystkie „dobrze wychowane” funkcje obliczeniowe / rekurencyjne. Jednak wiele „szybko rosnących” funkcji matematycznych nie wydaje się jak dotąd ocenianych pod względem złożoności czasu / przestrzeni, mimo że jest to dość oczywista, a nawet rażąca teoretyczna „luka” do wypełnienia. Może to doprowadzić do powstania ważnych „twierdzeń pomostowych”.