Tarski–Kuratowski algorithm

<h2 id="algorithm">Algorithm</h2>
<p>The Tarski–Kuratowski algorithm for the arithmetical hierarchy consists of the following steps:
</p>
<ol><li>Convert the formula to <a href="/facts/Prenex_normal_form/D0UCl45n">prenex normal form</a>. (This is the non-deterministic part of the algorithm, as there may be more than one valid prenex normal form for the given formula.)</li>
<li>If the formula is quantifier-free, it is in 
  
    
      
        
          Σ
          
            0
          
          
            0
          
        
      
    
    {\displaystyle \Sigma _{0}^{0}}
  
 and 
  
    
      
        
          Π
          
            0
          
          
            0
          
        
      
    
    {\displaystyle \Pi _{0}^{0}}
  
.</li>
<li>Otherwise, count the number of alternations of quantifiers; call this <i>k</i>.</li>
<li>If the first quantifier is <a href="/facts/Existential_quantification/hHveaBYo">∃</a>, the formula is in 
  
    
      
        
          Σ
          
            k
            +
            1
          
          
            0
          
        
      
    
    {\displaystyle \Sigma _{k+1}^{0}}
  
.</li>
<li>If the first quantifier is <a href="/facts/Universal_quantification/agNmvJKN">∀</a>, the formula is in 
  
    
      
        
          Π
          
            k
            +
            1
          
          
            0
          
        
      
    
    {\displaystyle \Pi _{k+1}^{0}}
  
.</li></ol>

<ul><li><a href="/facts/Hartley_Rogers_Jr./tQfHl6ad">Rogers, Hartley</a> <i>The Theory of Recursive Functions and Effective Computability</i>, MIT Press. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 0-262-68052-1; <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 0-07-053522-1</li></ul>

Tarski–Kuratowski algorithm open-in-new

Tarski–Kuratowski algorithm