Tarski-Kuratowski-Algorithmus - Wikipedia

In der Berechenbarkeitstheorie und der mathematischen Logik ist der Tarski-Kuratowski-Algorithmus ein nicht deterministischer Algorithmus, der eine Obergrenze für die Komplexität einer gegebenen Formel in der arithmetischen Hierarchie und der analytischen Hierarchie erzeugt.

Der Algorithmus ist nach Alfred Tarski und Kazimierz Kuratowski benannt.

Algorithmus [ edit ]

Der Tarski-Kuratowski-Algorithmus für die arithmetische Hierarchie besteht aus den folgenden Schritten:

1. Konvertieren Sie die Formel in eine Prenex-Normalform. (Dies ist der nicht deterministische Teil des Algorithmus, da es für die angegebene Formel mehr als eine gültige Prenex-Normalform geben kann.)
2. Wenn die Formel quantifiziererfrei ist, liegt sie in ${ displaystyle Sigma _ {0} ^ {0}}$ und $0 { displaystyle Pi _ {0} ^ {0}}$.
3. Andernfalls zählen Sie die Anzahl der Wechsel der Quantifizierer. nennen wir dies k .
4. Wenn der erste Quantifizierer ∃ ist, lautet die Formel in ${ displaystyle Sigma _ {k + 1} ^ {0}}$.
5. Wenn der erste Quantifizierer ∀ ist, lautet die Formel in ${\displaystyle {\mathrm{\Pi \; <!--\; \Pi \; -->}}_{k+1}^0}$.

Referenzen [ edit ]

• Rogers, H. Die Theorie rekursiver Funktionen und effektiver Berechenbarkeit MIT Press. ISBN 0-262-68052-1; ISBN 0-07-053522-1