Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Sudan function
open-in-new
<h2 id="definition">Definition</h2> F 0 ( x , y ) = x + y F n + 1 ( x , 0 ) = x if n ≥ 0 F n + 1 ( x , y + 1 ) = F n ( F n + 1 ( x , y ) , F n + 1 ( x , y ) + y + 1 ) if n ≥ 0 {\displaystyle {\begin{array}{lll}F_{0}(x,y)&=x+y\\F_{n+1}(x,0)&=x&{\text{if }}n\geq 0\\F_{n+1}(x,y+1)&=F_{n}(F_{n+1}(x,y),F_{n+1}(x,y)+y+1)&{\text{if }}n\geq 0\\\end{array}}} <p>The last equation can be equivalently written as </p> F n + 1 ( x , y + 1 ) = F n ( F n + 1 ( x , y ) , F 0 ( F n + 1 ( x , y ) , y + 1 ) ) {\displaystyle {\begin{array}{lll}F_{n+1}(x,y+1)&=F_{n}(F_{n+1}(x,y),F_{0}(F_{n+1}(x,y),y+1))\\\end{array}}} .<a class="footnote-ref" id="fnref:4" href="#fn:4"><sup>4</sup></a> <h2 id="computation">Computation</h2> <p>These equations can be used as rules of a <a href="/facts/Rewriting/9PHlnnnJ">term rewriting system (TRS)</a>. </p><p>The generalized function F ( x , y , n ) = d e f F n ( x , y ) {\displaystyle F(x,y,n){\stackrel {\mathrm {def} }{=}}F_{n}(x,y)} leads to the rewrite rules </p> (r1) F ( x , y , 0 ) → x + y (r2) F ( x , 0 , n + 1 ) → x (r3) F ( x , y + 1 , n + 1 ) → F ( F ( x , y , n + 1 ) , F ( F ( x , y , n + 1 ) , y + 1 , 0 ) , n ) {\displaystyle {\begin{array}{lll}{\text{(r1)}}&F(x,y,0)&\rightarrow x+y\\{\text{(r2)}}&F(x,0,n+1)&\rightarrow x\\{\text{(r3)}}&F(x,y+1,n+1)&\rightarrow F(F(x,y,n+1),F(F(x,y,n+1),y+1,0),n)\\\end{array}}} <p>At each reduction step the rightmost innermost occurrence of F is rewritten, by application of one of the rules (r1) - (r3). </p><p>Calude (1988) gives an example: compute F ( 2 , 2 , 1 ) → ∗ 12 {\displaystyle F(2,2,1)\rightarrow _{*}12} .<a class="footnote-ref" id="fnref:5" href="#fn:5"><sup>5</sup></a> </p><p>The reduction sequence is<a class="footnote-ref" id="fnref:6" href="#fn:6"><sup>6</sup></a> </p> <table><tbody><tr><td> F ( 2 , 2 , 1 ) _ {\displaystyle {\underline {F(2,2,1)}}} </td></tr><tr><td> → r 3 F ( F ( 2 , 1 , 1 ) , F ( F ( 2 , 1 , 1 ) _ , 2 , 0 ) , 0 ) {\displaystyle \rightarrow _{r3}F(F(2,1,1),F({\underline {F(2,1,1)}},2,0),0)} </td></tr><tr><td> → r 3 F ( F ( 2 , 1 , 1 ) , F ( F ( F ( 2 , 0 , 1 ) , F ( F ( 2 , 0 , 1 ) _ , 1 , 0 ) , 0 ) , 2 , 0 ) , 0 ) {\displaystyle \rightarrow _{r3}F(F(2,1,1),F(F(F(2,0,1),F({\underline {F(2,0,1)}},1,0),0),2,0),0)} </td></tr><tr><td> → r 2 F ( F ( 2 , 1 , 1 ) , F ( F ( F ( 2 , 0 , 1 ) , F ( 2 , 1 , 0 ) _ , 0 ) , 2 , 0 ) , 0 ) {\displaystyle \rightarrow _{r2}F(F(2,1,1),F(F(F(2,0,1),{\underline {F(2,1,0)}},0),2,0),0)} </td></tr><tr><td> → r 1 F ( F ( 2 , 1 , 1 ) , F ( F ( F ( 2 , 0 , 1 ) _ , 3 , 0 ) , 2 , 0 ) , 0 ) {\displaystyle \rightarrow _{r1}F(F(2,1,1),F(F({\underline {F(2,0,1)}},3,0),2,0),0)} </td></tr><tr><td> → r 2 F ( F ( 2 , 1 , 1 ) , F ( F ( 2 , 3 , 0 ) _ , 2 , 0 ) , 0 ) {\displaystyle \rightarrow _{r2}F(F(2,1,1),F({\underline {F(2,3,0)}},2,0),0)} </td></tr><tr><td> → r 1 F ( F ( 2 , 1 , 1 ) , F ( 5 , 2 , 0 ) _ , 0 ) {\displaystyle \rightarrow _{r1}F(F(2,1,1),{\underline {F(5,2,0)}},0)} </td></tr><tr><td> → r 1 F ( F ( 2 , 1 , 1 ) _ , 7 , 0 ) {\displaystyle \rightarrow _{r1}F({\underline {F(2,1,1)}},7,0)} </td></tr><tr><td> → r 3 F ( F ( F ( 2 , 0 , 1 ) , F ( F ( 2 , 0 , 1 ) _ , 1 , 0 ) , 0 ) , 7 , 0 ) {\displaystyle \rightarrow _{r3}F(F(F(2,0,1),F({\underline {F(2,0,1)}},1,0),0),7,0)} </td></tr><tr><td> → r 2 F ( F ( F ( 2 , 0 , 1 ) , F ( 2 , 1 , 0 ) _ , 0 ) , 7 , 0 ) {\displaystyle \rightarrow _{r2}F(F(F(2,0,1),{\underline {F(2,1,0)}},0),7,0)} </td></tr><tr><td> → r 1 F ( F ( F ( 2 , 0 , 1 ) _ , 3 , 0 ) , 7 , 0 ) {\displaystyle \rightarrow _{r1}F(F({\underline {F(2,0,1)}},3,0),7,0)} </td></tr><tr><td> → r 2 F ( F ( 2 , 3 , 0 ) _ , 7 , 0 ) {\displaystyle \rightarrow _{r2}F({\underline {F(2,3,0)}},7,0)} </td></tr><tr><td> → r 1 F ( 5 , 7 , 0 ) _ {\displaystyle \rightarrow _{r1}{\underline {F(5,7,0)}}} </td></tr><tr><td> → r 1 12 {\displaystyle \rightarrow _{r1}12} </td></tr></tbody></table> <h2 id="value-tables">Value tables</h2> <h3>Values of F0</h3> <p><i>F</i>0(<i>x</i>, <i>y</i>) = x + y </p> <table><tbody><tr><th><i>y</i> \ <i>x</i></th><th>0</th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th><th>7</th><th>8</th><th>9</th><th>10</th></tr><tr><th>0</th><td>0</td><td>1</td><td>2</td><td>3</td><td>4</td><td>5</td><td>6</td><td>7</td><td>8</td><td>9</td><td>10</td></tr><tr><th>1</th><td>1</td><td>2</td><td>3</td><td>4</td><td>5</td><td>6</td><td>7</td><td>8</td><td>9</td><td>10</td><td>11</td></tr><tr><th>2</th><td>2</td><td>3</td><td>4</td><td>5</td><td>6</td><td>7</td><td>8</td><td>9</td><td>10</td><td>11</td><td>12</td></tr><tr><th>3</th><td>3</td><td>4</td><td>5</td><td>6</td><td>7</td><td>8</td><td>9</td><td>10</td><td>11</td><td>12</td><td>13</td></tr><tr><th>4</th><td>4</td><td>5</td><td>6</td><td>7</td><td>8</td><td>9</td><td>10</td><td>11</td><td>12</td><td>13</td><td>14</td></tr><tr><th>5</th><td>5</td><td>6</td><td>7</td><td>8</td><td>9</td><td>10</td><td>11</td><td>12</td><td>13</td><td>14</td><td>15</td></tr><tr><th>6</th><td>6</td><td>7</td><td>8</td><td>9</td><td>10</td><td>11</td><td>12</td><td>13</td><td>14</td><td>15</td><td>16</td></tr><tr><th>7</th><td>7</td><td>8</td><td>9</td><td>10</td><td>11</td><td>12</td><td>13</td><td>14</td><td>15</td><td>16</td><td>17</td></tr><tr><th>8</th><td>8</td><td>9</td><td>10</td><td>11</td><td>12</td><td>13</td><td>14</td><td>15</td><td>16</td><td>17</td><td>18</td></tr><tr><th>9</th><td>9</td><td>10</td><td>11</td><td>12</td><td>13</td><td>14</td><td>15</td><td>16</td><td>17</td><td>18</td><td>19</td></tr><tr><th>10</th><td>10</td><td>11</td><td>12</td><td>13</td><td>14</td><td>15</td><td>16</td><td>17</td><td>18</td><td>19</td><td>20</td></tr></tbody></table> <h3>Values of F1</h3> <p><i>F</i>1(<i>x</i>, <i>y</i>) = 2y · (x + 2) − y − 2 </p> <table><tbody><tr><th><i>y</i> \ <i>x</i></th><th>0</th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th><th>7</th><th>8</th><th>9</th><th>10</th></tr><tr><th>0</th><td>0</td><td>1</td><td>2</td><td>3</td><td>4</td><td>5</td><td>6</td><td>7</td><td>8</td><td>9</td><td>10</td></tr><tr><th>1</th><td>1</td><td>3</td><td>5</td><td>7</td><td>9</td><td>11</td><td>13</td><td>15</td><td>17</td><td>19</td><td>21</td></tr><tr><th>2</th><td>4</td><td>8</td><td>12</td><td>16</td><td>20</td><td>24</td><td>28</td><td>32</td><td>36</td><td>40</td><td>44</td></tr><tr><th>3</th><td>11</td><td>19</td><td>27</td><td>35</td><td>43</td><td>51</td><td>59</td><td>67</td><td>75</td><td>83</td><td>91</td></tr><tr><th>4</th><td>26</td><td>42</td><td>58</td><td>74</td><td>90</td><td>106</td><td>122</td><td>138</td><td>154</td><td>170</td><td>186</td></tr><tr><th>5</th><td>57</td><td>89</td><td>121</td><td>153</td><td>185</td><td>217</td><td>249</td><td>281</td><td>313</td><td>345</td><td>377</td></tr><tr><th>6</th><td>120</td><td>184</td><td>248</td><td>312</td><td>376</td><td>440</td><td>504</td><td>568</td><td>632</td><td>696</td><td>760</td></tr><tr><th>7</th><td>247</td><td>375</td><td>503</td><td>631</td><td>759</td><td>887</td><td>1015</td><td>1143</td><td>1271</td><td>1399</td><td>1527</td></tr><tr><th>8</th><td>502</td><td>758</td><td>1014</td><td>1270</td><td>1526</td><td>1782</td><td>2038</td><td>2294</td><td>2550</td><td>2806</td><td>3062</td></tr><tr><th>9</th><td>1013</td><td>1525</td><td>2037</td><td>2549</td><td>3061</td><td>3573</td><td>4085</td><td>4597</td><td>5109</td><td>5621</td><td>6133</td></tr><tr><th>10</th><td>2036</td><td>3060</td><td>4084</td><td>5108</td><td>6132</td><td>7156</td><td>8180</td><td>9204</td><td>10228</td><td>11252</td><td>12276</td></tr></tbody></table> <h3>Values of F2</h3> <table><tbody><tr><th><i>y</i> \ <i>x</i></th><th>0</th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th><th>7</th></tr><tr><th rowspan="2">0</th><td>0</td><td>1</td><td>2</td><td>3</td><td>4</td><td>5</td><td>6</td><td>7</td></tr><tr><td colspan="8"><i>x</i></td></tr><tr><th rowspan="4">1</th><td>F1 (F2(0, 0), F2(0, 0)+1)</td><td>F1 (F2(1, 0), F2(1, 0)+1)</td><td>F1 (F2(2, 0), F2(2, 0)+1)</td><td>F1 (F2(3, 0), F2(3, 0)+1)</td><td>F1 (F2(4, 0), F2(4, 0)+1)</td><td>F1 (F2(5, 0), F2(5, 0)+1)</td><td>F1 (F2(6, 0), F2(6, 0)+1)</td><td>F1 (F2(7, 0), F2(7, 0)+1)</td></tr><tr><td>F1(0, 1)</td><td>F1(1, 2)</td><td>F1(2, 3)</td><td>F1(3, 4)</td><td>F1(4, 5)</td><td>F1(5, 6)</td><td>F1(6, 7)</td><td>F1(7, 8)</td></tr><tr><td>1</td><td>8</td><td>27</td><td>74</td><td>185</td><td>440</td><td>1015</td><td>2294</td></tr><tr><td colspan="8"><i>2x+1 · (x + 2) − x − 3</i>≈ 10lg 2·(x+1) + lg(x+2)</td></tr><tr><th rowspan="4">2</th><td>F1 (F2(0, 1), F2(0, 1)+2)</td><td>F1 (F2(1, 1), F2(1, 1)+2)</td><td>F1 (F2(2, 1), F2(2, 1)+2)</td><td>F1 (F2(3, 1), F2(3, 1)+2)</td><td>F1 (F2(4, 1), F2(4, 1)+2)</td><td>F1 (F2(5, 1), F2(5, 1)+2)</td><td>F1 (F2(6, 1), F2(6, 1)+2)</td><td>F1 (F2(7, 1), F2(7, 1)+2)</td></tr><tr><td>F1(1, 3)</td><td>F1(8, 10)</td><td>F1(27, 29)</td><td>F1(74, 76)</td><td>F1(185, 187)</td><td>F1(440, 442)</td><td>F1(1015, 1017)</td><td>F1(2294, 2296)</td></tr><tr><td>19</td><td>10228</td><td>15569256417</td><td>≈ 5,742397643 · 1024</td><td>≈ 3,668181327 · 1058</td><td>≈ 5,019729940 · 10135</td><td>≈ 1,428323374 · 10309</td><td>≈ 3,356154368 · 10694</td></tr><tr><td colspan="8">22x+1·(x+2) − x − 1 · (2x+1·(x+2) − x − 1) − (2x+1·(x+2) − x + 1)≈ 10lg 2 · (2x+1·(x+2) − x − 1) + lg(2x+1·(x+2) − x − 1) ≈ 10lg 2 · 2x+1·(x+2) + lg(2x+1·(x+2)) ≈ 10lg 2 · (2x+1·(x+2)) = 1010lg lg 2 + lg 2·(x+1) + lg(x+2) ≈ 1010lg 2·(x+1) + lg(x+2)</td></tr><tr><th rowspan="5">3</th><td>F1 (F2(0, 2), F2(0, 2)+3)</td><td>F1 (F2(1, 2), F2(1, 2)+3)</td><td>F1 (F2(2, 2), F2(2, 2)+3)</td><td>F1 (F2(3, 2), F2(3, 2)+3)</td><td>F1 (F2(4, 2), F2(4, 2)+3)</td><td>F1 (F2(5, 2), F2(5, 2)+3)</td><td>F1 (F2(6, 2), F2(6, 2)+3)</td><td>F1 (F2(7, 2), F2(7, 2)+3)</td></tr><tr><td>F1(F1(1,3), F1(1,3)+3)</td><td>F1(F1(8,10), F1(8,10)+3)</td><td>F1(F1(27,29), F1(27,29)+3)</td><td>F1(F1(74,76), F1(74,76)+3)</td><td>F1(F1(185,187), F1(185,187)+3)</td><td>F1(F1(440,442), F1(440,442)+3)</td><td>F1(F1(1015,1017), F1(1015,1017)+3)</td><td>F1(F1(2294,2297), F1(2294,2297)+3)</td></tr><tr><td>F1(19, 22)</td><td>F1(10228, 10231)</td><td>F1(15569256417,15569256420)</td><td>F1(≈6·1024, ≈6·1024)</td><td>F1(≈4·1058, ≈4·1058)</td><td>F1(≈5·10135, ≈5·10135)</td><td>F1(≈10309, ≈10309)</td><td>F1(≈3·10694, ≈3·10694)</td></tr><tr><td>88080360</td><td>≈ 7,04 · 103083</td><td>≈ 7,82 · 104686813201</td><td>≈ 101,72·1024</td><td>≈ 101,10·1058</td><td>≈ 101,51·10135</td><td>≈ 104,30·10308</td><td>≈ 101,01·10694</td></tr><tr><td colspan="8">longer expression, starts with 222x+1 an, ≈ 101010lg 2·(x+1) + lg(x+2)</td></tr><tr><th rowspan="5">4</th><td>F1 (F2(0, 3), F2(0, 3)+4)</td><td>F1 (F2(1, 3), F2(1, 3)+4)</td><td>F1 (F2(2, 3), F2(2, 3)+4)</td><td>F1 (F2(3, 3), F2(3, 3)+4)</td><td>F1 (F2(4, 3), F2(4, 3)+4)</td><td>F1 (F2(5, 3), F2(5, 3)+4)</td><td>F1 (F2(6, 3), F2(6, 3)+4)</td><td>F1 (F2(7, 3), F2(7, 3)+4)</td></tr><tr><td>F1 (F1(19, 22), F1(19, 22)+4)</td><td>F1 (F1(10228, 10231), F1(10228, 10231)+4)</td><td>F1 (F1(15569256417, 15569256420), F1(15569256417, 15569256420)+4)</td><td>F1 (F1(≈5,74·1024, ≈5,74·1024),F1(≈5,74·1024, ≈5,74·1024))</td><td>F1 (F1(≈3,67·1058, ≈3,67·1058),F1(≈3,67·1058, ≈3,67·1058))</td><td>F1 (F1(≈5,02·10135, ≈5,02·10135),F1(≈5,02·10135, ≈5,02·10135))</td><td>F1 (F1(≈1,43·10309, ≈1,43·10309),F1(≈1,43·10309, ≈1,43·10309))</td><td>F1 (F1(≈3,36·10694, ≈3,36·10694),F1(≈3,36·10694, ≈3,36·10694))</td></tr><tr><td>F1(88080360,88080364)</td><td>F1(10230·210231−10233,10230·210231−10229)</td><td colspan="6"></td></tr><tr><td>≈ 3,5 · 1026514839</td><td colspan="7"></td></tr><tr><td colspan="8">much longer expression, starts with 2222x+1 an, ≈ 10101010lg 2·(x+1) + lg(x+2)</td></tr></tbody></table> <h3>Values of F3</h3> <table><tbody><tr><th><i>y</i> \ <i>x</i></th><th>0</th><th>1</th><th>2</th><th>3</th><th>4</th></tr><tr><th rowspan="2">0</th><td>0</td><td>1</td><td>2</td><td>3</td><td>4</td></tr><tr><td colspan="5"><i>x</i></td></tr><tr><th rowspan="4">1</th><td>F2 (F3(0, 0), F3(0, 0)+1)</td><td>F2 (F3(1, 0), F3(1, 0)+1)</td><td>F2 (F3(2, 0), F3(2, 0)+1)</td><td>F2 (F3(3, 0), F3(3, 0)+1)</td><td>F2 (F3(4, 0), F3(4, 0)+1)</td></tr><tr><td>F2(0, 1)</td><td>F2(1, 2)</td><td>F2(2, 3)</td><td>F2(3, 4)</td><td>F2(4, 5)</td></tr><tr><td>1</td><td>10228</td><td>≈ 7,82 · 104686813201</td><td colspan="2"></td></tr><tr><td colspan="5">No closed expressions possible within the framework of normal mathematical notation</td></tr><tr><th rowspan="4">2</th><td>F3 (F4(0, 1), F4(0, 1)+2)</td><td>F3 (F4(1, 1), F4(1, 1)+2)</td><td>F3 (F4(2, 1), F4(2, 1)+2)</td><td>F3 (F4(3, 1), F4(3, 1)+2)</td><td>F3 (F4(4, 1), F4(4, 1)+2)</td></tr><tr><td>F3 (1, 3)</td><td>F3 (10228, 10230)</td><td>F3 (≈104686813201, ≈104686813201)</td><td colspan="2"></td></tr><tr><td colspan="5"> </td></tr><tr><td colspan="5">No closed expressions possible within the framework of normal mathematical notation</td></tr></tbody></table> <h2 id="notes-and-references">Notes and references</h2> <h2 id="bibliography">Bibliography</h2> <ul><li><a href="/facts/Wilhelm_Ackermann/8bPlUHSE">Ackermann</a>, Wilhelm (1928). <a href="http://gdz.sub.uni-goettingen.de/en/dms/loader/img/?PPN=PPN235181684_0099&DMDID=DMDLOG_0009">"Zum Hilbertschen Aufbau der reellen Zahlen"</a>. <i><a href="/facts/Mathematische_Annalen/GPhGaonc">Mathematische Annalen</a></i>. 99: 118–133. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2FBF01459088">10.1007/BF01459088</a>. <a href="/facts/JFM_(identifier)/P6rFxKKx">JFM</a> <a href="https://zbmath.org/?format=complete&q=an:54.0056.06">54.0056.06</a>. <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:123431274">123431274</a>.</li></ul> <ul><li><a href="/facts/Cristian_S._Calude/DzaS15UU">Calude, Cristian</a>; <a href="/facts/Solomon_Marcus/tktu0geJ">Marcus, Solomon</a>; Tevy, Ionel (1979). <a href="https://doi.org/10.1016%2F0315-0860%2879%2990024-7">"The first example of a recursive function which is not primitive recursive"</a>. <i><a href="/facts/Historia_Mathematica/cH72CmHe">Historia Mathematica</a></i>. 6 (4): 380–384. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2F0315-0860%2879%2990024-7">10.1016/0315-0860(79)90024-7</a>.</li></ul> <ul><li><a href="/facts/Cristian_S._Calude/DzaS15UU">Calude, Cristian</a> (1988). <a href="https://www.sciencedirect.com/science/book/9780444703569"><i>Theories of Computational Complexity</i></a>. Amsterdam: <a href="/facts/North-Holland_(imprint)/jkPSAEmR">North-Holland</a>. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-0-444-70356-9.</li></ul> <ul><li><a href="/facts/Gabriel_Sudan/dnNc7b1s">Sudan</a>, Gabriel (1927). "Sur le nombre transfini ωω". <i>Bulletin mathématique de la Société Roumaine des Sciences</i>. 30: 11–30. <a href="/facts/JFM_(identifier)/P6rFxKKx">JFM</a> <a href="https://zbmath.org/?format=complete&q=an:53.0171.01">53.0171.01</a>. <a href="/facts/JSTOR_(identifier)/YTeVmaJ7">JSTOR</a> <a href="https://www.jstor.org/stable/43769875">43769875</a>. Jbuch 53, 171</li></ul> <h2 id="external-links">External links</h2> <ul><li><a href="/facts/Rosetta_Code/HAN5rwmX">Rosetta Code</a> (23 July 2024). <a href="https://rosettacode.org/wiki/Sudan_function">"Sudan function"</a>.</li></ul> <ul><li>OEIS: A260003, A260004</li></ul> <h2 id="references">References</h2> <ol> <li id="fn:1"><p>Sudan 1927. - Sudan, Gabriel (1927). "Sur le nombre transfini ωω". Bulletin mathématique de la Société Roumaine des Sciences. 30: 11–30. JFM 53.0171.01. JSTOR 43769875. Jbuch 53, 171 <a href="https://zbmath.org/?format=complete&q=an:53.0171.01" target="_blank">https://zbmath.org/?format=complete&q=an:53.0171.01</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li> <li id="fn:2"><p>Ackermann 1928. - Ackermann, Wilhelm (1928). "Zum Hilbertschen Aufbau der reellen Zahlen". Mathematische Annalen. 99: 118–133. doi:10.1007/BF01459088. JFM 54.0056.06. S2CID 123431274. <a href="http://gdz.sub.uni-goettingen.de/en/dms/loader/img/?PPN=PPN235181684_0099&DMDID=DMDLOG_0009" target="_blank">http://gdz.sub.uni-goettingen.de/en/dms/loader/img/?PPN=PPN235181684_0099&DMDID=DMDLOG_0009</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li> <li id="fn:3"><p>Calude, Marcus & Tevy 1979. - Calude, Cristian; Marcus, Solomon; Tevy, Ionel (1979). "The first example of a recursive function which is not primitive recursive". Historia Mathematica. 6 (4): 380–384. doi:10.1016/0315-0860(79)90024-7. <a href="https://doi.org/10.1016%2F0315-0860%2879%2990024-7" target="_blank">https://doi.org/10.1016%2F0315-0860%2879%2990024-7</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li> <li id="fn:4"><p>Calude 1988, p. 92. - Calude, Cristian (1988). Theories of Computational Complexity. Amsterdam: North-Holland. ISBN 978-0-444-70356-9. <a href="https://www.sciencedirect.com/science/book/9780444703569" target="_blank">https://www.sciencedirect.com/science/book/9780444703569</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li> <li id="fn:5"><p>Calude 1988, pp. 92–95. - Calude, Cristian (1988). Theories of Computational Complexity. Amsterdam: North-Holland. ISBN 978-0-444-70356-9. <a href="https://www.sciencedirect.com/science/book/9780444703569" target="_blank">https://www.sciencedirect.com/science/book/9780444703569</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li> <li id="fn:6"><p>The rightmost innermost occurrences of F are underlined. <a href="#fnref:6" class="footnote-back-ref">↩</a></p></li> </ol>