Gibt es komplexere Probleme als das Totalitätsproblem, die in der praktischen Welt auftreten?

Wir wissen, dass sich das Halteproblem in der ersten Ebene der arithmetischen Hierarchie befindet. Wir wissen, dass sich das Totalitätsproblem in der 2. Ebene der arithmetischen Hierarchie befindet. Was sind einige Beispiele für Probleme in der 3. (oder höheren) Ebene der arithmetischen Hierarchie? +1 für Probleme, deren Instanzen in der praktischen Welt gelöst werden (Programmierer, Mathematiker usw.).

computability reference-request Otakar Molnár López
quelle

Jede weitere Hilfe, um dies zu einer verständlichen Frage zu machen, ist willkommen.

Otakar Molnár López

Ich bin mir nicht sicher, aber vielleicht ist es schwieriger als die Gesamtheit, zu entscheiden, ob zwei Turing-Maschinen (ungleich) für alle Eingaben die gleichen Ausgaben erzeugen.

Rus9384

en.wikipedia.org/wiki/…

@ rus9384 Ich denke, es sollte gleichwertig sein: Sie können es in der Form schreiben

\forall x . \exists y . p (x, y)

$\forall x.\exists y.p(x,y)$ mit

p

$p$ rekursiv als Totalität. Hier

x

$x$ ist die Eingabe, und

y

$y$ ist eine Anzahl von Schritten, die groß genug sind, um beide TMs anzuhalten (einmal)

y

$y$ ist bekannt, zu überprüfen, ob die Ausgabe gleich ist, ist trivial).

Chi

Wie wäre es mit

n^{t h}

$n^{th}$ -ordnungslogik? Vielleicht ist die Bewertung, ob die Aussage in einer solchen Logik wahr ist, ein komplettes Problem für

Σ_{n}^{0}

$\Sigma^0_n$ ?

Rus9384

Antworten:

Lassen $\{W_e\}_{e\in\mathbb N}$ eine kanonische Liste der rekursiv aufzählbaren, dh rechnerisch aufzählbaren, dh Turing-erkennbaren Sprachen (oder Mengen) sein.

Die Eigenschaft, die $W_e$ ist tatsächlich rekursiv, dh berechenbar, ist $\Sigma^0_3$ ::

\exists d \forall n (n \in {W.}_{e} \leftrightarrow n \notin {W.}_{d}) .

$\exists d\forall n(n\in W_e\leftrightarrow n\not\in W_d).$

Es befindet sich auf der 3. Ebene der Hierarchie: Es ist nicht von geringerer Komplexität als $\Sigma^0_3$ . Siehe zB Soare: Rekursiv aufzählbare Mengen und Grade, Satz 3.4 , für den Beweis.

Bjørn Kjos-Hanssen
quelle