In
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 e ...
and
mathematical logic
Mathematical logic is the study of logic, formal logic within mathematics. Major subareas include model theory, proof theory, set theory, and recursion theory. Research in mathematical logic commonly addresses the mathematical properties of for ...
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.
Algorithm
The Tarski–Kuratowski algorithm for the arithmetical hierarchy consists of the following steps:
# Convert the formula to
prenex normal form
A formula of the predicate calculus is in prenex normal form (PNF) if it is written as a string of quantifiers and bound variables, called the prefix, followed by a quantifier-free part, called the matrix. Together with the normal forms in propos ...
. (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
and
.
# Otherwise, count the number of alternations of quantifiers; call this ''k''.
# If the first quantifier is
∃
In predicate logic, an existential quantification is a type of quantifier, a logical constant which is interpreted as "there exists", "there is at least one", or "for some". It is usually denoted by the logical operator symbol ∃, which, whe ...
, the formula is in
.
# 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
.
References
*
Rogers, Hartley ''The Theory of Recursive Functions and Effective Computability'', MIT Press. ;
Mathematical logic hierarchies
Computability theory
Theory of computation
{{mathlogic-stub