Ist beschäftigter Biber die am schnellsten wachsende Funktion, die dem Menschen bekannt ist?

Ich hatte gerade diese interessante Frage. Was ist die am schnellsten wachsende Funktion, die dem Menschen bekannt ist? Ist es beschäftigt, Biber ?

Wir kennen Funktionen wie $x^2$ , aber diese Funktion wächst langsamer als $2^x$ , was wiederum langsamer als wächst $x!$, die wiederum langsamer wächst als $x^x$ . Wir können dann Funktionen kombinieren, um $(x^x)!$das wächst schneller als $x^x$ und so weiter.

Dann kommen wir zu rekursiven Funktionen wie Ackermanns Funktion $A(x,x)$ , die viel schneller wächst als $(x^x)!$. Dann denken die Leute über die beschäftigte Biber $B(x)$ -Funktion nach, die sogar noch schneller wächst als Ackermanns Funktion.

Zu diesem Zeitpunkt habe ich noch keine anderen Funktionen gehört, die schneller wachsen als beschäftigte Biber. Bedeutet das, dass es keine anderen Funktionen gibt, die möglicherweise schneller wachsen können als beschäftigter Biber? (Abgesehen von Fakultät von $B(x)$ und wie $A(B(x), B(x))$ usw.)

Die Busy-Beaver-Funktion wächst schneller als jede berechenbare Funktion . Sie kann jedoch von einer Turing-Maschine berechnet werden, die Zugang zu einem Orakel zur Lösung des Halteproblems erhalten hat. Sie können dann eine Belegt-Biber-Funktion "zweiter Ordnung" definieren, die schneller wächst als jede Funktion, die selbst von jeder Turing-Maschine mit einem Orakel für das Stopp-Problem berechnet werden kann. Sie können dies für immer tun und eine Hierarchie von immer schneller wachsenden, geschäftigen Biberfunktionen aufbauen.

Lesen Sie den ausgezeichneten Aufsatz von Scott Aaronson zu diesem Thema: Wer kann die größere Zahl nennen? .

Es gibt keine "am schnellsten wachsende Funktion". Tatsächlich gibt es nicht einmal eine Abfolge von Funktionen, die am schnellsten wachsen. Dies hat bereits Hausdorff gezeigt. Gegeben seien zwei Funktionen , sagen , dass g wächst schneller als f wenn lim n → ∞ g ( n $f,g\colon \mathbb{N} \longrightarrow \mathbb{N}$$g$$f$ Bei gegebener Funktionfwächstdie folgende Funktiongschneller alsf:g(n)=nf(n). Bei gegebener Folge von Funktionenfnwächstdie folgende Funktiongschneller als alle von ihnen: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).$$ Eine natürliche Frage ist, ob es eine "Skala" der am schnellsten wachsenden Funktionen gibt. Dies ist eine gut geordnete Menge von Funktionen , die „kofinale“ ist, das, ein beliebige Funktion gegeben ist f gibt es eine schnellen wachsende Funktion g α . (Anstelle einer geordneten Menge können wir äquivalent über eine Kette sprechen, dh, zwei beliebige Funktionen in der Menge müssen vergleichbar sein.) Die Existenz einer Skala ist unabhängig von ZFC: Angenommen, CH, es gibt eine Skala, während in Cohens Modell, das CH fälscht (Addition von ω 1 Real), keine Skala existiert.$g_\alpha$$f$$g_\alpha$$\omega_1$

Andere Antworten sprechen die Frage direkt an. Für einen tieferen Hintergrund wird in diesem Artikel von Lafitte der größere Kontext von beschäftigten biberartigen Funktionen betrachtet. Es hat auch einige Ergebnisse und Theoreme, die die Idee in einen allgemeineren Rahmen einpassen. Es zeigt, dass (informell) "beschäftigte biberartige Funktionen" in engem Zusammenhang mit Chaitin-Unvollständigkeitsphänomenen stehen (Satz 2.1). Es zeigt sich auch, dass es Theorien gibt, die nicht "mächtig" genug sind, um die beschäftigten biberartigen Funktionen "zu verstehen", dh sie sind in diesen Theorien aufgrund von göttlicher Unvollständigkeit nicht beweisbar. Es zeigt die Idee, fleißige biberähnliche Ergebnisse als Axiome anzunehmen und eine logische Folge von Theorien, die den Ideen von Turing ähneln.

[1] Fleißige Biber, die von Grégory Lafitte verrückt geworden sind. Abstrakt:

Wir zeigen einige Unvollständigkeitsergebnisse à la Chaitin mit den Busy-Beaver-Funktionen. Anschließend zeigen wir mit Hilfe der Ordnungslogik, wie eine Theorie erhalten werden kann, in der die Werte der ausgelasteten Biberfunktionen nachweislich ermittelt werden können, und zeigen anhand dieser Theorie eine Struktur für die Beweisbarkeit der Werte dieser Funktionen auf.

Die Hartmanis-Stearns Zeit und Raum Hierarchie Sätze beweisen , dass es keine „am schnellsten wachsende“ Funktion in Bezug auf Zeit oder Raum , weil die Skala unbeschränkt ist. Es gibt jedoch eine solche Reihenfolge , dass alle "gut verhaltenen" berechenbaren / rekursiven Funktionen verglichen werden können. Viele "schnell wachsende" mathematische Funktionen scheinen jedoch bisher nicht in Bezug auf die zeitliche / räumliche Komplexität bewertet worden zu sein, obwohl es sich um eine etwas offensichtliche oder sogar krasse theoretische "Lücke" handelt, die zu füllen ist. Dies könnte zu wichtigen "Brückensätzen" führen.