computability theory Computability theory, also known as recursion theory, is a branch of mathematical logic, computer science, and the theory of computation that originated in the 1930s with the study of computable functions and Turing degrees. The field has since ex ...

and

mathematical logic Mathematical logic is the study of Logic#Formal logic, formal logic within mathematics. Major subareas include model theory, proof theory, set theory, and recursion theory (also known as computability theory). Research in mathematical logic com ...

the Tarski–Kuratowski algorithm is a non-deterministic algorithm that produces an

upper bound In mathematics, particularly in order theory, an upper bound or majorant of a subset of some preordered set is an element of that is every element of . Dually, a lower bound or minorant of is defined to be an element of that is less ...

for the complexity of a given formula in the

arithmetical hierarchy In mathematical logic, the arithmetical hierarchy, arithmetic hierarchy or Kleene–Mostowski hierarchy (after mathematicians Stephen Cole Kleene and Andrzej Mostowski) classifies certain sets based on the complexity of formulas that define th ...

and

analytical hierarchy Analytic or analytical may refer to: Chemistry * Analytical chemistry, the analysis of material samples to learn their chemical composition and structure * Analytical technique, a method that is used to determine the concentration of a chemica ...

. The algorithm is named after

Alfred Tarski Alfred Tarski (; ; born Alfred Teitelbaum;School of Mathematics and Statistics, University of St Andrews ''School of Mathematics and Statistics, University of St Andrews''. January 14, 1901 – October 26, 1983) was a Polish-American logician ...

and

Kazimierz Kuratowski Kazimierz Kuratowski (; 2 February 1896 – 18 June 1980) was a Polish mathematician and logician. He was one of the leading representatives of the Warsaw School of Mathematics. He worked as a professor at the University of Warsaw and at the Ma ...

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

\Sigma^0_0

and

\Pi^0_0

. # Otherwise, count the number of alternations of quantifiers; call this ''k''. # If the first quantifier is ∃, the formula is in

\Sigma^0_

. # If the first quantifier is

∀ A mathematical symbol is a figure or a combination of figures that is used to represent a mathematical object, an action on mathematical objects, a relation between mathematical objects, or for structuring the other symbols that occur in a formula ...

, the formula is in

\Pi^0_

References

* Rogers, Hartley ''The Theory of Recursive Functions and Effective Computability'', MIT Press. ; Mathematical logic hierarchies Computability theory Theory of computation {{mathlogic-stub