Grzegorczyk hierarchy

<h2 id="definition">Definition</h2>
First we introduce an infinite set of functions, denoted Ei for some <a href="/facts/Natural_number/u65og8JE">natural number</a> i. We define

E
                  
                    0
                  
                
                (
                x
                ,
                y
                )
              
              
                =
              
              
                x
                +
                y
              
            
            
              
                
                  E
                  
                    1
                  
                
                (
                x
                )
              
              
                =
              
              
                
                  x
                  
                    2
                  
                
                +
                2
              
            
            
              
                
                  E
                  
                    n
                    +
                    2
                  
                
                (
                0
                )
              
              
                =
              
              
                2
              
            
            
              
                
                  E
                  
                    n
                    +
                    2
                  
                
                (
                x
                +
                1
                )
              
              
                =
              
              
                
                  E
                  
                    n
                    +
                    1
                  
                
                (
                
                  E
                  
                    n
                    +
                    2
                  
                
                (
                x
                )
                )
              
            
          
        
      
    
    {\displaystyle {\begin{array}{lcl}E_{0}(x,y)&=&x+y\\E_{1}(x)&=&x^{2}+2\\E_{n+2}(0)&=&2\\E_{n+2}(x+1)&=&E_{n+1}(E_{n+2}(x))\\\end{array}}}

E
 
 0
 
 
 
 
 {\displaystyle E_{0}}
 
 is the addition function, and 
 
 
 
 
 E
 
 1
 
 
 
 
 {\displaystyle E_{1}}
 
 is a unary function which squares its argument and adds two. Then, for each n greater than 1, 
 
 
 
 
 E
 
 n
 
 
 (
 x
 )
 =
 
 E
 
 n
 −
 1
 
 
 x
 
 
 (
 2
 )
 
 
 {\displaystyle E_{n}(x)=E_{n-1}^{x}(2)}
 
, i.e. the x-th <a href="/facts/Iterated_function/Vzsx64An">iterate</a> of 
 
 
 
 
 E
 
 n
 −
 1
 
 
 
 
 {\displaystyle E_{n-1}}
 
 evaluated at 2.
From these functions we define the Grzegorczyk hierarchy. 
 
 
 
 
 
 
 E
 
 
 
 n
 
 
 
 
 {\displaystyle {\mathcal {E}}^{n}}
 
, the n-th set in the hierarchy, contains the following functions:

<ol><li>Ek for k < n</li>
<li>the zero function (Z(x) = 0);</li>
<li>the <a href="/facts/Successor_function/R1hhkSEG">successor function</a> (S(x) = x + 1);</li>
<li>the <a href="/facts/Projection_function/10mwpNsM">projection functions</a> (
 
 
 
 
 p
 
 i
 
 
 m
 
 
 (
 
 t
 
 1
 
 
 ,
 
 t
 
 2
 
 
 ,
 …
 ,
 
 t
 
 m
 
 
 )
 =
 
 t
 
 i
 
 
 
 
 {\displaystyle p_{i}^{m}(t_{1},t_{2},\dots ,t_{m})=t_{i}}
 
);</li>
<li>the (generalized) <a href="/facts/Function_composition/r5Pvnmth">compositions of functions</a> in the set (if h, g1, g2, ... and gm are in 
 
 
 
 
 
 
 E
 
 
 
 n
 
 
 
 
 {\displaystyle {\mathcal {E}}^{n}}
 
, then 
 
 
 
 f
 (
 
 
 
 u
 ¯
 
 
 
 )
 =
 h
 (
 
 g
 
 1
 
 
 (
 
 
 
 u
 ¯
 
 
 
 )
 ,
 
 g
 
 2
 
 
 (
 
 
 
 u
 ¯
 
 
 
 )
 ,
 …
 ,
 
 g
 
 m
 
 
 (
 
 
 
 u
 ¯
 
 
 
 )
 )
 
 
 {\displaystyle f({\bar {u}})=h(g_{1}({\bar {u}}),g_{2}({\bar {u}}),\dots ,g_{m}({\bar {u}}))}
 
 is as well);<a class="footnote-ref" id="fnref:2" href="#fn:2">2</a> and</li>
<li>the results of limited (primitive) recursion applied to functions in the set, (if g, h and j are in 
 
 
 
 
 
 
 E
 
 
 
 n
 
 
 
 
 {\displaystyle {\mathcal {E}}^{n}}
 
 and 
 
 
 
 f
 (
 t
 ,
 
 
 
 u
 ¯
 
 
 
 )
 ≤
 j
 (
 t
 ,
 
 
 
 u
 ¯
 
 
 
 )
 
 
 {\displaystyle f(t,{\bar {u}})\leq j(t,{\bar {u}})}
 
 for all t and 
 
 
 
 
 
 
 u
 ¯
 
 
 
 
 
 {\displaystyle {\bar {u}}}
 
, and further 
 
 
 
 f
 (
 0
 ,
 
 
 
 u
 ¯
 
 
 
 )
 =
 g
 (
 
 
 
 u
 ¯
 
 
 
 )
 
 
 {\displaystyle f(0,{\bar {u}})=g({\bar {u}})}
 
 and 
 
 
 
 f
 (
 t
 +
 1
 ,
 
 
 
 u
 ¯
 
 
 
 )
 =
 h
 (
 t
 ,
 
 
 
 u
 ¯
 
 
 
 ,
 f
 (
 t
 ,
 
 
 
 u
 ¯
 
 
 
 )
 )
 
 
 {\displaystyle f(t+1,{\bar {u}})=h(t,{\bar {u}},f(t,{\bar {u}}))}
 
, then f is in 
 
 
 
 
 
 
 E
 
 
 
 n
 
 
 
 
 {\displaystyle {\mathcal {E}}^{n}}
 
 as well).<a class="footnote-ref" id="fnref:3" href="#fn:3">3</a></li></ol>
In other words, 
 
 
 
 
 
 
 E
 
 
 
 n
 
 
 
 
 {\displaystyle {\mathcal {E}}^{n}}
 
 is the <a href="/facts/Closure_(mathematics)/Ct6r2fJz">closure</a> of set 
 
 
 
 
 B
 
 n
 
 
 =
 {
 Z
 ,
 S
 ,
 (
 
 p
 
 i
 
 
 m
 
 
 
 )
 
 i
 ≤
 m
 
 
 ,
 
 E
 
 k
 
 
 :
 k
 <
 n
 }
 
 
 {\displaystyle B_{n}=\{Z,S,(p_{i}^{m})_{i\leq m},E_{k}:k<n\}}
 
 with respect to function composition and limited recursion (as defined above).

<h2 id="properties">Properties</h2>
These sets clearly form the hierarchy

E
            
          
          
            0
          
        
        ⊆
        
          
            
              E
            
          
          
            1
          
        
        ⊆
        
          
            
              E
            
          
          
            2
          
        
        ⊆
        ⋯
      
    
    {\displaystyle {\mathcal {E}}^{0}\subseteq {\mathcal {E}}^{1}\subseteq {\mathcal {E}}^{2}\subseteq \cdots }

because they are closures over the 
 
 
 
 
 B
 
 n
 
 
 
 
 {\displaystyle B_{n}}
 
's and 
 
 
 
 
 B
 
 0
 
 
 ⊆
 
 B
 
 1
 
 
 ⊆
 
 B
 
 2
 
 
 ⊆
 ⋯
 
 
 {\displaystyle B_{0}\subseteq B_{1}\subseteq B_{2}\subseteq \cdots }
 
.
They are strict subsets.<a class="footnote-ref" id="fnref:4" href="#fn:4">4</a><a class="footnote-ref" id="fnref:5" href="#fn:5">5</a> In other words

E
            
          
          
            0
          
        
        ⊊
        
          
            
              E
            
          
          
            1
          
        
        ⊊
        
          
            
              E
            
          
          
            2
          
        
        ⊊
        ⋯
      
    
    {\displaystyle {\mathcal {E}}^{0}\subsetneq {\mathcal {E}}^{1}\subsetneq {\mathcal {E}}^{2}\subsetneq \cdots }

because the <a href="/facts/Hyperoperation/XNn1hneN">hyperoperation</a> 
 
 
 
 
 H
 
 n
 
 
 
 
 {\displaystyle H_{n}}
 
 is in 
 
 
 
 
 
 
 E
 
 
 
 n
 
 
 
 
 {\displaystyle {\mathcal {E}}^{n}}
 
 but not in 
 
 
 
 
 
 
 E
 
 
 
 n
 −
 1
 
 
 
 
 {\displaystyle {\mathcal {E}}^{n-1}}
 
.

<ul><li>
 
 
 
 
 
 
 E
 
 
 
 0
 
 
 
 
 {\displaystyle {\mathcal {E}}^{0}}
 
 includes functions such as x+1, x+2, ...
<ul><li>Every unary function f(x) in 
 
 
 
 
 
 
 E
 
 
 
 0
 
 
 
 
 {\displaystyle {\mathcal {E}}^{0}}
 
 is upper bounded by some x+n. However, 
 
 
 
 
 
 
 E
 
 
 
 0
 
 
 
 
 {\displaystyle {\mathcal {E}}^{0}}
 
 also includes more complicated functions like x∸1, x∸y (where ∸ is the <a href="/facts/Monus/tTqUwnbL">monus</a> sign defined as x∸y = max(x-y, 0)), x mod y, etc.</li></ul></li>
<li>
 
 
 
 
 
 
 E
 
 
 
 1
 
 
 
 
 {\displaystyle {\mathcal {E}}^{1}}
 
 provides all addition functions, such as x+y, 4x, ...</li>
<li>
 
 
 
 
 
 
 E
 
 
 
 2
 
 
 
 
 {\displaystyle {\mathcal {E}}^{2}}
 
 provides all multiplication functions, such as xy, x4</li>
<li>
 
 
 
 
 
 
 E
 
 
 
 3
 
 
 
 
 {\displaystyle {\mathcal {E}}^{3}}
 
 provides all exponentiation functions, such as xy, 222x, and is exactly the <a href="/facts/ELEMENTARY/gxGLXF4R">elementary recursive functions</a>.</li>
<li>
 
 
 
 
 
 
 E
 
 
 
 4
 
 
 
 
 {\displaystyle {\mathcal {E}}^{4}}
 
 provides all <a href="/facts/Tetration/5rKeVVYv">tetration</a> functions, and so on.</li></ul>
Notably, both the function 
 
 
 
 U
 
 
 {\displaystyle U}
 
 and the characteristic function of the predicate 
 
 
 
 T
 
 
 {\displaystyle T}
 
 from the <a href="/facts/Kleene_normal_form_theorem/fdsBjwl0">Kleene normal form theorem</a> are definable in a way such that they lie at level 
 
 
 
 
 
 
 E
 
 
 
 0
 
 
 
 
 {\displaystyle {\mathcal {E}}^{0}}
 
 of the Grzegorczyk hierarchy. This implies in particular that every recursively enumerable set is enumerable by some 
 
 
 
 
 
 
 E
 
 
 
 0
 
 
 
 
 {\displaystyle {\mathcal {E}}^{0}}
 
-function.

<h2 id="relation-to-primitive-recursive-functions">Relation to primitive recursive functions</h2>
The definition of 
 
 
 
 
 
 
 E
 
 
 
 n
 
 
 
 
 {\displaystyle {\mathcal {E}}^{n}}
 
 is the same as that of the <a href="/facts/Primitive_recursive_function/4z97gRnl">primitive recursive functions</a>, PR, except that recursion is limited (
 
 
 
 f
 (
 t
 ,
 
 
 
 u
 ¯
 
 
 
 )
 ≤
 j
 (
 t
 ,
 
 
 
 u
 ¯
 
 
 
 )
 
 
 {\displaystyle f(t,{\bar {u}})\leq j(t,{\bar {u}})}
 
 for some j in 
 
 
 
 
 
 
 E
 
 
 
 n
 
 
 
 
 {\displaystyle {\mathcal {E}}^{n}}
 
) and the functions 
 
 
 
 (
 
 E
 
 k
 
 
 
 )
 
 k
 <
 n
 
 
 
 
 {\displaystyle (E_{k})_{k<n}}
 
 are explicitly included in 
 
 
 
 
 
 
 E
 
 
 
 n
 
 
 
 
 {\displaystyle {\mathcal {E}}^{n}}
 
. Thus the Grzegorczyk hierarchy can be seen as a way to limit the power of primitive recursion to different levels.
It is clear from this fact that all functions in any level of the Grzegorczyk hierarchy are primitive recursive functions (i.e. 
 
 
 
 
 
 
 E
 
 
 
 n
 
 
 ⊆
 
 
 P
 R
 
 
 
 
 {\displaystyle {\mathcal {E}}^{n}\subseteq {\mathsf {PR}}}
 
) and thus:

⋃
          
            n
          
        
        
          
            
              
                E
              
            
            
              n
            
          
        
        ⊆
        
          
            P
            R
          
        
      
    
    {\displaystyle \bigcup _{n}{{\mathcal {E}}^{n}}\subseteq {\mathsf {PR}}}

It can also be shown that all primitive recursive functions are in some level of the hierarchy,<a class="footnote-ref" id="fnref:6" href="#fn:6">6</a><a class="footnote-ref" id="fnref:7" href="#fn:7">7</a> thus

⋃
          
            n
          
        
        
          
            
              
                E
              
            
            
              n
            
          
        
        =
        
          
            P
            R
          
        
      
    
    {\displaystyle \bigcup _{n}{{\mathcal {E}}^{n}}={\mathsf {PR}}}

and the sets 
 
 
 
 
 
 
 E
 
 
 
 0
 
 
 ,
 
 
 
 E
 
 
 
 1
 
 
 −
 
 
 
 E
 
 
 
 0
 
 
 ,
 
 
 
 E
 
 
 
 2
 
 
 −
 
 
 
 E
 
 
 
 1
 
 
 ,
 …
 ,
 
 
 
 E
 
 
 
 n
 
 
 −
 
 
 
 E
 
 
 
 n
 −
 1
 
 
 ,
 …
 
 
 {\displaystyle {\mathcal {E}}^{0},{\mathcal {E}}^{1}-{\mathcal {E}}^{0},{\mathcal {E}}^{2}-{\mathcal {E}}^{1},\dots ,{\mathcal {E}}^{n}-{\mathcal {E}}^{n-1},\dots }
 
 <a href="/facts/Partition_of_a_set/VeP9g8CA">partition</a> the set of primitive recursive functions, PR.
Meyer and <a href="/facts/Dennis_Ritchie/I1yu1UWU">Ritchie</a> introduced another hierarchy subdividing the primitive recursive functions, based on the nesting depth of loops needed to write a <a href="/facts/LOOP_(programming_language)/BURN1jcQ">LOOP</a> program that computes the function. For a natural number 
 
 
 
 i
 
 
 {\displaystyle i}
 
, let 
 
 
 
 
 
 
 L
 
 
 
 i
 
 
 
 
 {\displaystyle {\mathcal {L}}_{i}}
 
 denote the set of functions computable by a LOOP program with LOOP and END commands nested no deeper than 
 
 
 
 i
 
 
 {\displaystyle i}
 
 levels.<a class="footnote-ref" id="fnref:8" href="#fn:8">8</a> Fachini and Maggiolo-Schettini showed that 
 
 
 
 
 
 
 L
 
 
 
 i
 
 
 
 
 {\displaystyle {\mathcal {L}}_{i}}
 
 coincides with 
 
 
 
 
 
 
 E
 
 
 
 i
 +
 1
 
 
 
 
 {\displaystyle {\mathcal {E}}_{i+1}}
 
 for all integers 
 
 
 
 i
 >
 1
 
 
 {\displaystyle i>1}
 
.<a class="footnote-ref" id="fnref:9" href="#fn:9">9</a>p.63

<h2 id="extensions">Extensions</h2>
Main article: <a href="/facts/Fast-growing_hierarchy/4ctDqlLY">Fast-growing hierarchy</a>
The Grzegorczyk hierarchy can be extended to <a href="/facts/Transfinite_number/m2oTjXaj">transfinite</a> <a href="/facts/Ordinal_number/GelFLjJt">ordinals</a>. Such extensions define a <a href="/facts/Fast-growing_hierarchy/4ctDqlLY">fast-growing hierarchy</a>. To do this, the generating functions 
 
 
 
 
 E
 
 α
 
 
 
 
 {\displaystyle E_{\alpha }}
 
 must be recursively defined for <a href="/facts/Limit_ordinal/jPCCoPuP">limit ordinals</a> (note they have already been recursively defined for successor ordinals by the relation 
 
 
 
 
 E
 
 α
 +
 1
 
 
 (
 n
 )
 =
 
 E
 
 α
 
 
 n
 
 
 (
 2
 )
 
 
 {\displaystyle E_{\alpha +1}(n)=E_{\alpha }^{n}(2)}
 
). If there is a standard way of defining a fundamental sequence 
 
 
 
 
 λ
 
 m
 
 
 
 
 {\displaystyle \lambda _{m}}
 
, whose limit ordinal is 
 
 
 
 λ
 
 
 {\displaystyle \lambda }
 
, then the generating functions can be defined 
 
 
 
 
 E
 
 λ
 
 
 (
 n
 )
 =
 
 E
 
 
 λ
 
 n
 
 
 
 
 (
 n
 )
 
 
 {\displaystyle E_{\lambda }(n)=E_{\lambda _{n}}(n)}
 
. However, this definition depends upon a standard way of defining the fundamental sequence. Rose (1984) suggests a standard way for all ordinals α < <a href="/facts/Epsilon_numbers_(mathematics)/t7w8KgA9">ε0</a>.
The original extension was due to <a href="/facts/Martin_L%C3%B6b/yoRsokW0">Martin Löb</a> and Stan S. Wainer and is sometimes called the <a href="/facts/L%C3%B6b%E2%80%93Wainer_hierarchy/4ctDqlLY">Löb–Wainer hierarchy</a>.<a class="footnote-ref" id="fnref:10" href="#fn:10">10</a>

<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/ELEMENTARY/gxGLXF4R">ELEMENTARY</a></li>
<li><a href="/facts/Fast-growing_hierarchy/4ctDqlLY">Fast-growing hierarchy</a></li>
<li><a href="/facts/Ordinal_analysis/bx5joaVU">Ordinal analysis</a></li></ul>
<h2 id="notes">Notes</h2>

<h2 id="bibliography">Bibliography</h2>
<ul><li>Brainerd, Walter S.; Landweber, Lawrence H. (1974). Theory of computation. Wiley. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 9780471095859.</li></ul>
<ul><li>Cichon, E. A.; Wainer, S. S. (1983). "The slow-growing and the Grzegorczyk hierarchies". <a href="/facts/Journal_of_Symbolic_Logic/lfXVXcoy">Journal of Symbolic Logic</a>. 48 (2): 399–408. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.2307%2F2273557">10.2307/2273557</a>. <a href="/facts/ISSN_(identifier)/DPAflDvU">ISSN</a> <a href="https://search.worldcat.org/issn/0022-4812">0022-4812</a>. <a href="/facts/JSTOR_(identifier)/YTeVmaJ7">JSTOR</a> <a href="https://www.jstor.org/stable/2273557">2273557</a>. <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0704094">0704094</a>. <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:1390729">1390729</a>.</li></ul>
<ul><li>Gakwaya, Jean-Sylvestre (1997). "A survey on the Grzegorczyk Hierarchy and its Extension through the BSS Model of Computability". <a href="/facts/CiteSeerX_(identifier)/SceDmd3c">CiteSeerX</a> <a href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.69.4621">10.1.1.69.4621</a>.</li></ul>
<ul><li><a href="/facts/Andrzej_Grzegorczyk/YIW9k7Dt">Grzegorczyk, Andrzej</a> (1953). <a href="http://matwbn.icm.edu.pl/ksiazki/rm/rm04/rm0401.pdf">"Some classes of recursive functions"</a> (PDF). Rozprawy Matematyczne. 4: 1–45.</li></ul>
<ul><li><a href="/facts/Martin_L%C3%B6b/yoRsokW0">Löb, Martin Hugo</a>; Wainer, Stan S. (1970). "Hierarchies of Number Theoretic Functions I, II: A Correction". <a href="/facts/Archiv_f%C3%BCr_mathematische_Logik_und_Grundlagenforschung/gy7j6XuM">Archiv für mathematische Logik und Grundlagenforschung</a>. 14 (3–4): 198–199. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2Fbf01991855">10.1007/bf01991855</a>. <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:119830535">119830535</a>.</li></ul>
<ul><li>Rose, H.E. (1984). Subrecursion: Functions and hierarchies. <a href="/facts/Oxford_University_Press/CYyTzzWG">Oxford University Press</a>. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 0-19-853189-3.</li></ul>
<ul><li>Wagner, K.; Wechsung, G. (1986). "Computational Complexity". Mathematics and Its Applications. 21. Springer. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-90-277-2146-4.</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Wagner & Wechsung 1986, p. 43. - Wagner, K.; Wechsung, G. (1986). "Computational Complexity". Mathematics and Its Applications. 21. Springer. ISBN 978-90-277-2146-4. <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Here 
 
 
 
 
 
 
 u
 ¯
 
 
 
 
 
 {\displaystyle {\bar {u}}}
 
 represents a tuple of inputs to f. The notation 
 
 
 
 f
 (
 
 
 
 u
 ¯
 
 
 
 )
 
 
 {\displaystyle f({\bar {u}})}
 
 means that f takes some arbitrary number of arguments and if 
 
 
 
 
 
 
 u
 ¯
 
 
 
 =
 (
 x
 ,
 y
 ,
 z
 )
 
 
 {\displaystyle {\bar {u}}=(x,y,z)}
 
, then 
 
 
 
 f
 (
 
 
 
 u
 ¯
 
 
 
 )
 =
 f
 (
 x
 ,
 y
 ,
 z
 )
 
 
 {\displaystyle f({\bar {u}})=f(x,y,z)}
 
. In the notation 
 
 
 
 f
 (
 t
 ,
 
 
 
 u
 ¯
 
 
 
 )
 
 
 {\displaystyle f(t,{\bar {u}})}
 
, the first argument, t, is specified explicitly and the rest as the arbitrary tuple 
 
 
 
 
 
 
 u
 ¯
 
 
 
 
 
 {\displaystyle {\bar {u}}}
 
. Thus, if 
 
 
 
 
 
 
 u
 ¯
 
 
 
 =
 (
 x
 ,
 y
 ,
 z
 )
 
 
 {\displaystyle {\bar {u}}=(x,y,z)}
 
, then 
 
 
 
 f
 (
 t
 ,
 
 
 
 u
 ¯
 
 
 
 )
 =
 f
 (
 t
 ,
 x
 ,
 y
 ,
 z
 )
 
 
 {\displaystyle f(t,{\bar {u}})=f(t,x,y,z)}
 
. This notation allows composition and limited recursion to be defined for functions, f, of any number of arguments. <a href="/wiki/Tuple" target="_blank">/wiki/Tuple</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Here 
 
 
 
 
 
 
 u
 ¯
 
 
 
 
 
 {\displaystyle {\bar {u}}}
 
 represents a tuple of inputs to f. The notation 
 
 
 
 f
 (
 
 
 
 u
 ¯
 
 
 
 )
 
 
 {\displaystyle f({\bar {u}})}
 
 means that f takes some arbitrary number of arguments and if 
 
 
 
 
 
 
 u
 ¯
 
 
 
 =
 (
 x
 ,
 y
 ,
 z
 )
 
 
 {\displaystyle {\bar {u}}=(x,y,z)}
 
, then 
 
 
 
 f
 (
 
 
 
 u
 ¯
 
 
 
 )
 =
 f
 (
 x
 ,
 y
 ,
 z
 )
 
 
 {\displaystyle f({\bar {u}})=f(x,y,z)}
 
. In the notation 
 
 
 
 f
 (
 t
 ,
 
 
 
 u
 ¯
 
 
 
 )
 
 
 {\displaystyle f(t,{\bar {u}})}
 
, the first argument, t, is specified explicitly and the rest as the arbitrary tuple 
 
 
 
 
 
 
 u
 ¯
 
 
 
 
 
 {\displaystyle {\bar {u}}}
 
. Thus, if 
 
 
 
 
 
 
 u
 ¯
 
 
 
 =
 (
 x
 ,
 y
 ,
 z
 )
 
 
 {\displaystyle {\bar {u}}=(x,y,z)}
 
, then 
 
 
 
 f
 (
 t
 ,
 
 
 
 u
 ¯
 
 
 
 )
 =
 f
 (
 t
 ,
 x
 ,
 y
 ,
 z
 )
 
 
 {\displaystyle f(t,{\bar {u}})=f(t,x,y,z)}
 
. This notation allows composition and limited recursion to be defined for functions, f, of any number of arguments. <a href="/wiki/Tuple" target="_blank">/wiki/Tuple</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">Rose 1984. - Rose, H.E. (1984). Subrecursion: Functions and hierarchies. Oxford University Press. ISBN 0-19-853189-3. <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">Gakwaya 1997. - Gakwaya, Jean-Sylvestre (1997). "A survey on the Grzegorczyk Hierarchy and its Extension through the BSS Model of Computability". CiteSeerX 10.1.1.69.4621. <a href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.69.4621" target="_blank">https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.69.4621</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">Rose 1984. - Rose, H.E. (1984). Subrecursion: Functions and hierarchies. Oxford University Press. ISBN 0-19-853189-3. <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">Gakwaya 1997. - Gakwaya, Jean-Sylvestre (1997). "A survey on the Grzegorczyk Hierarchy and its Extension through the BSS Model of Computability". CiteSeerX 10.1.1.69.4621. <a href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.69.4621" target="_blank">https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.69.4621</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
<li id="fn:8">A. R. Meyer, D. M. Ritchie, "The complexity of loop programs". Proceedings A.C.M. National Meeting, 1967. <a href="https://people.csail.mit.edu/meyer/meyer-ritchie.pdf" target="_blank">https://people.csail.mit.edu/meyer/meyer-ritchie.pdf</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></li>
<li id="fn:9">E. Fachini, A. Maggiolo-Schettini, "[A hierarchy of primitive recursive sequence functions]". From Informatique théorique, book 13, no. 1 (1979), pp.49--67. <a href="#fnref:9" class="footnote-back-ref">↩</a></li>
<li id="fn:10">Löb & Wainer 1970. - Löb, Martin Hugo; Wainer, Stan S. (1970). "Hierarchies of Number Theoretic Functions I, II: A Correction". Archiv für mathematische Logik und Grundlagenforschung. 14 (3–4): 198–199. doi:10.1007/bf01991855. S2CID 119830535. <a href="https://doi.org/10.1007%2Fbf01991855" target="_blank">https://doi.org/10.1007%2Fbf01991855</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></li>
</ol>

Grzegorczyk hierarchy open-in-new

Grzegorczyk hierarchy