In computability theory and mathematical logic the Tarski–Kuratowski algorithm is a non-deterministic algorithm that produces an upper bound for the complexity of a given formula in the arithmetical hierarchy and analytical hierarchy.
The algorithm is named after Alfred Tarski and Kazimierz Kuratowski.
We don't have any images related to Tarski–Kuratowski algorithm yet.
You can add one yourself here.
We don't have any YouTube videos related to Tarski–Kuratowski algorithm yet.
You can add one yourself here.
We don't have any PDF documents related to Tarski–Kuratowski algorithm yet.
You can add one yourself here.
We don't have any Books related to Tarski–Kuratowski algorithm yet.
You can add one yourself here.
We don't have any archived web articles related to Tarski–Kuratowski algorithm yet.
Algorithm
The Tarski–Kuratowski algorithm for the arithmetical hierarchy consists of the following steps:
- Convert the formula to prenex normal form. (This is the non-deterministic part of the algorithm, as there may be more than one valid prenex normal form for the given formula.)
- If the formula is quantifier-free, it is in Σ 0 0 {\displaystyle \Sigma _{0}^{0}} and Π 0 0 {\displaystyle \Pi _{0}^{0}} .
- Otherwise, count the number of alternations of quantifiers; call this k.
- If the first quantifier is ∃, the formula is in Σ k + 1 0 {\displaystyle \Sigma _{k+1}^{0}} .
- If the first quantifier is ∀, the formula is in Π k + 1 0 {\displaystyle \Pi _{k+1}^{0}} .
- Rogers, Hartley The Theory of Recursive Functions and Effective Computability, MIT Press. ISBN 0-262-68052-1; ISBN 0-07-053522-1