Fast Growing Hierarchy

Die Fast Growing Hierarchy ist eine Folge von Funktionen, die in der mathematischen Logik und insbesondere in der Berechenbarkeitstheorie verwendet wird, um die Wachstumsraten von Funktionen zu klassifizieren. Jede Funktion in dieser Hierarchie wächst signifikant schneller als die vorherigen Funktionen. Die Hierarchie bietet Erkenntnisse darüber, wie schnell bestimmte Funktionen ansteigen können, und wird oft in Zusammenhang mit der Untersuchung von großen Zahlen und der Komplexität von Algorithmen verwendet. Es beginnt mit einfachen Funktionen wie der Nachfolgerfunktion und erweitert sich dann zu immer komplexeren Funktionen, die wiederum schneller wachsen.

Definition

Um die Fast Growing Hierarchy zu definieren, beginnt man mit einer einfachen Funktion, wie der Nachfolgerfunktion $f_{0}(n)=n+1$ . Von dort aus werden komplexere Funktionen schrittweise aufgebaut. Eine typische Folge für den Aufbau der Fast Growing Hierarchy ist durch die Verwendung der sogenannten „diagonalen“ Methode oder durch Verwendung der Gewinnfunktionen von Veblen.

Die hierarchischen Funktionen werden üblicherweise wie folgt definiert:

1. Grundfunktion: Die Nachfolgerfunktion $f_{0}(n)$ ist die einfachste Funktion in dieser Hierarchie. Sie besagt lediglich, dass man von einer natürlichen Zahl n zur nächsten natürlichen Zahl $n+1$ gelangt. Diese Funktion wächst nicht sehr schnell.

2. Rekursionsbasis: $f_{m+1}(n)$ bedeutet, dass $f_{m}(n)$ n-mal angewendet wird. Zum Beispiel ist $f_{3}(4)=f_{2}(f_{2}(f_{2}(f_{2}(4))))$ .

3. Für Limesordinalzahlen $\lambda$ , wo keine unmittelbare Vorgängerzahl existiert (also nicht wie bei $\alpha +1$ ), wird eine etwas komplexere Definition benötigt, die oft eine bisher definierte Sequenz von bereits bestehenden Funktionen bis $\lambda$ verwendet, um $f_{\lambda }$ zu definieren.

Erste Funktionen der Fast Growing Hierarchy
Level	Formel	Mathematische Funktion
$f_{0}(n)$	$n+1$	Addition
$f_{1}(n)$	$f_{0}^{n}(n){=n+}\underbrace {1+1\cdots +1} _{n{\text{ mal +1}}}=n+n=2n$	Multiplikation
$f_{2}(n)$	$f_{1}^{n}(n)=n\cdot \underbrace {2\cdot \ldots \cdot 2} _{n{\text{ mal }}\cdot 2}=2^{n}n$	Exponentiation
$f_{3}(n)$	$f_{2}^{n}(n)\geq 2^{n}n\cdot ((2^{n}n)\uparrow \uparrow (n-1))\geq 2\uparrow \uparrow n$	Tetration
$f_{m}(n)$	$f_{m-1}^{n}(n)\geq f_{m-1}(n)\uparrow ^{m-1}n\geq 2\uparrow ^{m-1}n$

Wachstum der Funktionen

Erste Werte der Fast Growing Hierarchy
Stufe	1	2	3	...
$1$	$f_{1}(1)=2*1=2$	$f_{1}(2)=2*2=4$	$f_{1}(3)=2*3=6$	...
$2$	$f_{2}(1)=2^{1}*1=2$	$f_{2}(2)=2^{2}*2=8$	$f_{2}(3)=2^{3}*3=24$	...
$3$	$f_{3}(1)=1*2^{1}=2$	$f_{3}(2)=f_{2}(f_{2}(2))=f_{2}(8)=8*2^{8}=2048$	$f_{3}(3)=f_{2}(f_{2}(f_{2}(3)))=f_{2}(f_{2}(24))=f_{2}(242^{24})=f_{2}(402653184)=4026531842^{402653184}=6.89508*10^{121210694}{\text{ (eine Zahl mit über 121 Mio. Ziffern)}}$	...
...	...	...	...	...

Das Wachstum der Funktionen in der Fast Growing Hierarchy ist extrem schnell. Zum Beispiel übersteigt das Wachstum von $f_{\omega }(n)$ (wobei $\omega$ die erste unendliche Ordinalzahl ist) bereits alle primitiv rekursiven Funktionen, einschließlich sehr schnell wachsender Funktionen wie die Ackermann-Funktion. Funktionen höherer Ordnung in der Hierarchie wachsen so schnell, dass ihre Werte für alle praktischen Anwendungen außerhalb der Bereichen der reinen Mathematik und theoretischen Informatik als unendlich betrachtet werden können.

$f_{\omega }(n)$ ist dabei definiert als $f_{n}(n)$ , also eine Diagonale der obigen Tabelle ( $f_{1}(1)$ , $f_{2}(2)$ , $f_{3}(3)$ ,...).

$f_{\omega +1}(n)$ ist definiert als $f_{n}^{n}(n)$ , also eine n-malige Anwendung von $f_{\omega }(n)$ auf n. Zum Beispiel:

$f_{\omega +1}(2)=f_{\omega }(f_{\omega }(2))=f_{\omega }(8)$

$=f_{8}(8)>2\uparrow \uparrow \uparrow \uparrow \uparrow \uparrow \uparrow 8=2\uparrow ^{7}8$

Verwendung

Die Fast Growing Hierarchy ist in der mathematischen Logik und Berechenbarkeitstheorie von Bedeutung, da sie hilft, die "Stärken" verschiedener unendlicher Ordinalzahlen zu vergleichen sowie Einblicke in die Struktur und Grenzen der Beweisbarkeit und Berechenbarkeit gibt. Sie wird auch genutzt, um die Wachstumsgrenzen von Funktionen zu demonstrieren, die in verschiedenen Bereichen der Mathematik auftreten, und um die Komplexität von Algorithmen oder Problemen in der theoretischen Informatik zu klassifizieren.

Beispielsweise liegt Grahams Zahl in der Fast Growing Hierarchy bei $f_{\omega +1}(64)$ .

Grenzen der Fast Growing Hierarchy

Trotz der enormen Wachstumsgeschwindigkeit der Fast Growing Hierarchy können selbst die höchsten Funktionen nicht mit der Wachstumsrate der Sequenz TREE(n)-Funktion Schritt halten. Diese Funktion wächst noch deutlich schneller als alles, was in der Fast Growing Hierarchy beschrieben wird. TREE(n) ist die Funktion von Harvey Friedman (Mathematiker) zur Lösung von Problemen des Satzes von Kruskal.

Weblinks