Magnetic complex reluctance: Difference between revisions

Revision as of 20:46, 10 August 2013

In computability theory and mathematical logic the Tarski–Kuratowski algorithm is a non-deterministic algorithm which provides an upper bound for the complexity of formulas 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:

Convert the formula to prenex normal form.
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 _{k+1}^{0}$ .
If the first quantifier is ∀, the formula is in $\Pi _{k+1}^{0}$ .

References

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

Template:Mathlogic-stub

@@ Line 1: / Line 1: @@
-I would like to introduce myself to you, I am Andrew and my wife doesn't like it at all. Distributing production is exactly where her primary earnings arrives from. To climb is some thing I really appreciate performing. My wife and I live in Mississippi but now I'm contemplating other choices.<br><br>Feel free to visit my website ... tarot readings ([http://c045.danah.co.kr/home/index.php?document_srl=1356970&mid=qna danah.co.kr])
+In [[computability theory]] and [[mathematical logic]] the '''Tarski–Kuratowski algorithm''' is a [[non-deterministic algorithm]] which provides an upper bound for the complexity of formulas 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:
+# Convert the formula to [[prenex normal form]].
+# If the formula is quantifier-free, it is in <math>\Sigma^0_0</math> and <math>\Pi^0_0</math>.
+# Otherwise, count the number of alternations of quantifiers; call this ''k''.
+# If the first quantifier is [[Existential quantification|∃]], the formula is in <math>\Sigma^0_{k+1}</math>.
+# If the first quantifier is [[Universal quantification|∀]], the formula is in <math>\Pi^0_{k+1}</math>.
+==References==
+*Rogers, H. ''The Theory of Recursive Functions and Effective Computability'', MIT Press. ISBN 0-262-68052-1; ISBN 0-07-053522-1
+{{DEFAULTSORT:Tarski-Kuratowski algorithm}}
+[[Category:Mathematical logic hierarchies]]
+[[Category:Computability theory]]
+[[Category:Theory of computation]]
+{{mathlogic-stub}}

Magnetic complex reluctance: Difference between revisions

Revision as of 20:46, 10 August 2013

Algorithm

References

Navigation menu

Search