go-v.orgcodex
Menu
Page tools

codex · Philosophy

Tarski–Kuratowski algorithm

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.

== 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 Σ00 and Π00. Otherwise, count the number of alternations of quantifiers; call this k. If the first quantifier is ∃, the formula is in Σk+10. If the first quantifier is ∀, the formula is in Πk+10.

== References == Rogers, Hartley The Theory of Recursive Functions and Effective Computability, MIT Press. ISBN 0-262-68052-1; ISBN 0-07-053522-1

Wikipedia contributors, "Tarski–Kuratowski algorithm", Wikipedia, revision 1130327263, retrieved 21 November 2026, source, CC BY-SA 4.0.

More Philosophy · Search the codex