Login
Login

Sudan function

In the theory of computation, the Sudan function is an example of a function that is recursive, but not primitive recursive. This is also true of the better-known Ackermann function.

In 1926, David Hilbert conjectured that every computable function was primitive recursive. This was refuted by Gabriel Sudan and Wilhelm Ackermann {{mdash}} both his students {{mdash}} using different functions that were published in quick succession: Sudan in 1927,{{sfn|Sudan|1927}} Ackermann in 1928.{{sfn|Ackermann|1928}}

The Sudan function is the earliest published example of a recursive function that is not primitive recursive.{{sfn|Calude|Marcus|Tevy|1979}}

Definition

:\begin{array}{lll}

F_0 (x, y) & = x+y \\

F_{n+1} (x, 0) & = x & \text{if } n \ge 0 \\

F_{n+1} (x, y+1) & = F_n (F_{n+1} (x, y), F_{n+1} (x, y) + y + 1) & \text{if } n\ge 0 \\

\end{array}

The last equation can be equivalently written as

:\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}.{{sfn|Calude|1988|page=92}}

Computation

These equations can be used as rules of a term rewriting system (TRS).

The generalized function F(x,y,n) \stackrel{\mathrm{def}}{=} F_n(x,y) leads to the rewrite rules

:\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}

At each reduction step the rightmost innermost occurrence of F is rewritten, by application of one of the rules (r1) - (r3).

Calude (1988) gives an example: compute F(2,2,1) \rightarrow_{*} 12.{{sfn|Calude|1988|pages=92-95}}

The reduction sequence isThe rightmost innermost occurrences of F are underlined.

:

\underline{{F(2,2,1)}}
{{space|4}}\rightarrow_{r3} F(F(2,1,1),F(\underline{{F(2,1,1)}},2,0),0)
{{space|4}}\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)
{{space|4}}\rightarrow_{r2} F(F(2,1,1),F(F(F(2,0,1),\underline{{F(2,1,0)}},0),2,0),0)
{{space|4}}\rightarrow_{r1} F(F(2,1,1),F(F(\underline{{F(2,0,1)}},3,0),2,0),0)
{{space|4}}\rightarrow_{r2} F(F(2,1,1),F(\underline{{F(2,3,0)}},2,0),0)
{{space|4}}\rightarrow_{r1} F(F(2,1,1),\underline{{F(5,2,0)}},0)
{{space|4}}\rightarrow_{r1} F(\underline{{F(2,1,1)}},7,0)
{{space|4}}\rightarrow_{r3} F(F(F(2,0,1),F(\underline{{F(2,0,1)}},1,0),0),7,0)
{{space|4}}\rightarrow_{r2} F(F(F(2,0,1),\underline{{F(2,1,0)}},0),7,0)
{{space|4}}\rightarrow_{r1} F(F(\underline{{F(2,0,1)}},3,0),7,0)
{{space|4}}\rightarrow_{r2} F(\underline{{F(2,3,0)}},7,0)
{{space|4}}\rightarrow_{r1} \underline{{F(5,7,0)}}
{{space|4}}\rightarrow_{r1} 12

Value tables

= Values of F<sub>0</sub> =

F0(x, y) = x + y

class="wikitable" style="text-align:right; font-size:100%"
y \ x012345678910
0

| 0 || 1 || 2 || 3 || 4 || 5 || 6 || 7 || 8 || 9 || 10

1

| 1 || 2 || 3 || 4 || 5 || 6 || 7 || 8 || 9 || 10 || 11

2

| 2 || 3 || 4 || 5 || 6 || 7 || 8 || 9 || 10 || 11 || 12

3

| 3 || 4 || 5 || 6 || 7 || 8 || 9 || 10 || 11 || 12 || 13

4

| 4 || 5 || 6 || 7 || 8 || 9 || 10 || 11 || 12 || 13 || 14

5

| 5 || 6 || 7 || 8 || 9 || 10 || 11 || 12 || 13 || 14 || 15

6

| 6 || 7 || 8 || 9 || 10 || 11 || 12 || 13 || 14 || 15 || 16

7

| 7 || 8 || 9 || 10 || 11 || 12 || 13 || 14 || 15 || 16 || 17

8

| 8 || 9 || 10 || 11 || 12 || 13 || 14 || 15 || 16 || 17 || 18

9

| 9 || 10 || 11 || 12 || 13 || 14 || 15 || 16 || 17 || 18 || 19

10

| 10 || 11 || 12 || 13 || 14 || 15 || 16 || 17 || 18 || 19 || 20

= Values of F<sub>1</sub> =

F1(x, y) = 2y · (x + 2) − y − 2

class="wikitable" style="text-align:right; font-size:95%"
y \ x012345678910
0

| 0 || 1 || 2 || 3 || 4 || 5 || 6 || 7 || 8 || 9 || 10

1

| 1 || 3 || 5 || 7 || 9 || 11 || 13 || 15 || 17 || 19 || 21

2

| 4 || 8 || 12 || 16 || 20 || 24 || 28 || 32 || 36 || 40 || 44

3

| 11 || 19 || 27 || 35 || 43 || 51 || 59 || 67 || 75 || 83 || 91

4

| 26 || 42 || 58 || 74 || 90 || 106 || 122 || 138 || 154 || 170 || 186

5

| 57 || 89 || 121 || 153 || 185 || 217 || 249 || 281 || 313 || 345 || 377

6

| 120 || 184 || 248 || 312 || 376 || 440 || 504 || 568 || 632 || 696 || 760

7

| 247 || 375 || 503 || 631 || 759 || 887 || 1015 || 1143 || 1271 || 1399 || 1527

8

| 502 || 758 || 1014 || 1270 || 1526 || 1782 || 2038 || 2294 || 2550 || 2806 || 3062

9

| 1013 || 1525 || 2037 || 2549 || 3061 || 3573 || 4085 || 4597 || 5109 || 5621 || 6133

10

| 2036 || 3060 || 4084 || 5108 || 6132 || 7156 || 8180 || 9204 || 10228 || 11252 || 12276

= Values of F<sub>2</sub> =

class="wikitable" style="text-align:right; font-size:90%"
y \ x01234567
rowspan="2" | 0

| 0 || 1 || 2 || 3 || 4 || 5 || 6 || 7

colspan="8" align="center" style="background:#FAF7F4" | x
rowspan="4" | 1

| F1 (F2(0, 0),  
F2(0, 0)+1)

| F1 (F2(1, 0),  
F2(1, 0)+1)

| F1 (F2(2, 0),  
F2(2, 0)+1)

| F1 (F2(3, 0),  
F2(3, 0)+1)

| F1 (F2(4, 0),  
F2(4, 0)+1)

| F1 (F2(5, 0),  
F2(5, 0)+1)

| F1 (F2(6, 0),  
F2(6, 0)+1)

| F1 (F2(7, 0),  
F2(7, 0)+1)

F1(0, 1)

| F1(1, 2)

| F1(2, 3)

| F1(3, 4)

| F1(4, 5)

| F1(5, 6)

| F1(6, 7)

| F1(7, 8)

18277418544010152294
colspan="8" align="center" style="background:#FAF7F4" | 2x+1 · (x + 2) − x − 3
≈ 10lg 2·(x+1) + lg(x+2)
rowspan="4" | 2

| F1 (F2(0, 1),  
F2(0, 1)+2)

| F1 (F2(1, 1),  
F2(1, 1)+2)

| F1 (F2(2, 1),  
F2(2, 1)+2)

| F1 (F2(3, 1),  
F2(3, 1)+2)

| F1 (F2(4, 1),  
F2(4, 1)+2)

| F1 (F2(5, 1),  
F2(5, 1)+2)

| F1 (F2(6, 1),  
F2(6, 1)+2)

| F1 (F2(7, 1),  
F2(7, 1)+2)

F1(1, 3)

| F1(8, 10)

| F1(27, 29)

| F1(74, 76)

| F1(185, 187)

| F1(440, 442)

| F1(1015, 1017)

| F1(2294, 2296)

19

| 10228

| 15569256417

| ≈ 5,742397643 · 1024

| ≈ 3,668181327 · 1058

| ≈ 5,019729940 · 10135

| ≈ 1,428323374 · 10309

| ≈ 3,356154368 · 10694

colspan="8" align="center" style="background:#FAF7F4" | 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)
rowspan="5" | 3

| F1 (F2(0, 2),  
F2(0, 2)+3)

| F1 (F2(1, 2),  
F2(1, 2)+3)

| F1 (F2(2, 2),  
F2(2, 2)+3)

| F1 (F2(3, 2),  
F2(3, 2)+3)

| F1 (F2(4, 2),  
F2(4, 2)+3)

| F1 (F2(5, 2),  
F2(5, 2)+3)

| F1 (F2(6, 2),  
F2(6, 2)+3)

| F1 (F2(7, 2),  
F2(7, 2)+3)

F1(F1(1,3),  
F1(1,3)+3)

| F1(F1(8,10),  
F1(8,10)+3)

| F1(F1(27,29),  
F1(27,29)+3)

| F1(F1(74,76),  
F1(74,76)+3)

| F1(F1(185,187),  
F1(185,187)+3)

| F1(F1(440,442),  
F1(440,442)+3)

| F1(F1(1015,1017),  
F1(1015,1017)+3)

| F1(F1(2294,2297),  
F1(2294,2297)+3)

F1(19, 22)

| F1(10228, 10231)

| F1(15569256417,
15569256420)

| F1(≈6·1024, ≈6·1024)

| F1(≈4·1058, ≈4·1058)

| F1(≈5·10135, ≈5·10135)

| F1(≈10309, ≈10309)

| F1(≈3·10694, ≈3·10694)

88080360

| ≈ 7,04 · 103083

| ≈ 7,82 · 104686813201

| ≈ 101,72·1024

| ≈ 101,10·1058

| ≈ 101,51·10135

| ≈ 104,30·10308

| ≈ 101,01·10694

colspan="8" align="center" style="background:#FAF7F4" | longer expression, starts with 222x+1 an, ≈ 101010lg 2·(x+1) + lg(x+2)
rowspan="5" | 4

| F1 (F2(0, 3),  
F2(0, 3)+4)

| F1 (F2(1, 3),  
F2(1, 3)+4)

| F1 (F2(2, 3),  
F2(2, 3)+4)

| F1 (F2(3, 3),  
F2(3, 3)+4)

| F1 (F2(4, 3),  
F2(4, 3)+4)

| F1 (F2(5, 3),  
F2(5, 3)+4)

| F1 (F2(6, 3),  
F2(6, 3)+4)

| F1 (F2(7, 3),  
F2(7, 3)+4)

F1 (F1(19, 22),  
F1(19, 22)+4)

| F1 (F1(10228,  
10231),  
F1(10228,  
10231)+4)

| F1 (F1(15569256417,  
15569256420),  
F1(15569256417,  
15569256420)+4)

| F1 (F1(≈5,74·1024, ≈5,74·1024),
F1(≈5,74·1024, ≈5,74·1024))

| F1 (F1(≈3,67·1058, ≈3,67·1058),
F1(≈3,67·1058, ≈3,67·1058))

| F1 (F1(≈5,02·10135, ≈5,02·10135),
F1(≈5,02·10135, ≈5,02·10135))

| F1 (F1(≈1,43·10309, ≈1,43·10309),
F1(≈1,43·10309, ≈1,43·10309))

| F1 (F1(≈3,36·10694, ≈3,36·10694),
F1(≈3,36·10694, ≈3,36·10694))

F1(88080360,
88080364)		F1(10230·210231−10233,
10230·210231−10229)		colspan="6" style="border:0; background:white" |
≈ 3,5 · 1026514839colspan="7" style="border:0; background:white" |
colspan="8" align="center" style="background:#FAF7F4" | much longer expression, starts with 2222x+1 an, ≈ 10101010lg 2·(x+1) + lg(x+2)

= Values of F<sub>3</sub> =

class="wikitable" style="text-align:right; font-size:90%"
y \ x01234
rowspan="2" | 0

| 0 || 1 || 2 || 3 || 4

colspan="5" align="center" style="background:#FAF7F4" | x
rowspan="4" | 1

| F2 (F3(0, 0),  
F3(0, 0)+1)

| F2 (F3(1, 0),  
F3(1, 0)+1)

| F2 (F3(2, 0),  
F3(2, 0)+1)

| F2 (F3(3, 0),  
F3(3, 0)+1)

| F2 (F3(4, 0),  
F3(4, 0)+1)

F2(0, 1)

| F2(1, 2)

| F2(2, 3)

| F2(3, 4)

| F2(4, 5)

1

| 10228

| ≈ 7,82 · 104686813201

| style="background:white;" colspan="2" |

colspan="5" align="center" style="background:#FAF7F4" | No closed expressions possible within the framework of normal mathematical notation
rowspan="4" | 2

| F3 (F4(0, 1),  
F4(0, 1)+2)

| F3 (F4(1, 1),  
F4(1, 1)+2)

| F3 (F4(2, 1),  
F4(2, 1)+2)

| F3 (F4(3, 1),  
F4(3, 1)+2)

| F3 (F4(4, 1),  
F4(4, 1)+2)

F3 (1, 3)

| F3 (10228, 10230)

| F3 (≈104686813201, 
≈104686813201)

| style="background:white;" colspan="2" |

style="background:white;" colspan="5" |  
colspan="5" align="center" style="background:#FAF7F4" | No closed expressions possible within the framework of normal mathematical notation

Notes and references

{{reflist}}

Bibliography

{{refbegin}}

  • {{cite journal

| last= Ackermann

| first= Wilhelm

| journal= Mathematische Annalen

| title= Zum Hilbertschen Aufbau der reellen Zahlen

| year= 1928

| volume= 99

| pages= 118–133

| url= http://gdz.sub.uni-goettingen.de/en/dms/loader/img/?PPN=PPN235181684_0099&DMDID=DMDLOG_0009

| doi= 10.1007/BF01459088

| s2cid= 123431274

| jfm= 54.0056.06

}}

  • {{cite journal

| last1= Calude

| first1= Cristian

| author1-link= Cristian S. Calude

| last2= Marcus

| first2= Solomon

| author2-link= Solomon Marcus

| last3= Tevy

| first3= Ionel

| title= The first example of a recursive function which is not primitive recursive

| journal= Historia Mathematica

| year= 1979

| doi= 10.1016/0315-0860(79)90024-7

| doi-access= free

| volume= 6

| issue= 4

| pages= 380–384

}}

  • {{cite book

| last= Calude

| first= Cristian

| author-link= Cristian S. Calude

| title= Theories of Computational Complexity

| year= 1988

| url= https://www.sciencedirect.com/science/book/9780444703569

| publisher= North-Holland

| location= Amsterdam

| isbn= 978-0-444-70356-9

}}

  • {{cite journal

| last= Sudan

| first= Gabriel

| title= Sur le nombre transfini ωω

| journal= Bulletin mathématique de la Société Roumaine des Sciences

| year= 1927

| volume= 30

| pages= 11–30

| jstor= 43769875

| jfm= 53.0171.01

| quote= Jbuch 53, 171

}}

{{refend}}

External links

  • {{cite web

| author= Rosetta Code

| title= Sudan function

| date= 23 July 2024

| url= https://rosettacode.org/wiki/Sudan_function

}}

{{DEFAULTSORT:Sudan Function}}

Category:Arithmetic

Category:Large integers

Category:Special functions

Category:Theory of computation