Algoritmus Tarski – Kuratowski - Tarski–Kuratowski algorithm

v teorie vypočítatelnosti a matematická logika the Algoritmus Tarski – Kuratowski je nedeterministický algoritmus který vyrábí horní hranice pro složitost daného vzorce v aritmetická hierarchie a analytická hierarchie.

Algoritmus je pojmenován po Alfred Tarski a Kazimierz Kuratowski.

Algoritmus

Algoritmus Tarski – Kuratowski pro aritmetickou hierarchii se skládá z následujících kroků:

1. Převést vzorec na normální forma prenex. (Toto je nedeterministická část algoritmu, protože pro daný vzorec může existovat více než jedna platná prenex normální forma.)
2. Pokud je vzorec bez kvantifikátoru, je v ${ displaystyle Sigma _ {0} ^ {0}}$ a ${ displaystyle Pi _ {0} ^ {0}}$.
3. V opačném případě spočítejte počet střídání kvantifikátorů; zavolej to k.
4. Pokud je první kvantifikátor ∃, vzorec je v ${ displaystyle Sigma _ {k + 1} ^ {0}}$.
5. Pokud je první kvantifikátor ∀, vzorec je v ${ displaystyle Pi _ {k + 1} ^ {0}}$.

Reference

• Rogers, H. Teorie rekurzivních funkcí a efektivní vypočítatelnost, MIT Stiskněte. ISBN  0-262-68052-1; ISBN  0-07-053522-1

Tento matematická logika související článek je a pahýl. Wikipedii můžete pomoci pomocí rozšiřovat to.