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 — both his students — using different functions that were published in quick succession: Sudan in 1927, Ackermann in 1928.
The Sudan function is the earliest published example of a recursive function that is not primitive recursive.
Definition
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}}}
The last equation can be equivalently written as
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}}}
Computation
These equations can be used as rules of a term rewriting system (TRS) .
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)}
(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}}}
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
)
→
∗
12
{\displaystyle F(2,2,1)\rightarrow _{*}12}
The reduction sequence is[ 6]
F
(
2
,
2
,
1
)
_
{\displaystyle {\underline {F(2,2,1)}}}
→
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)}
→
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)}
→
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)}
→
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)}
→
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)}
→
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)}
→
r
1
F
(
F
(
2
,
1
,
1
)
_
,
7
,
0
)
{\displaystyle \rightarrow _{r1}F({\underline {F(2,1,1)}},7,0)}
→
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)}
→
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)}
→
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)}
→
r
2
F
(
F
(
2
,
3
,
0
)
_
,
7
,
0
)
{\displaystyle \rightarrow _{r2}F({\underline {F(2,3,0)}},7,0)}
→
r
1
F
(
5
,
7
,
0
)
_
{\displaystyle \rightarrow _{r1}{\underline {F(5,7,0)}}}
→
r
1
12
{\displaystyle \rightarrow _{r1}12}
Value tables
Values of F0
F 0 (x , y ) = x + y
y x 0
1
2
3
4
5
6
7
8
9
10
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 F1
F 1 (x , y ) = 2y · (x + 2) − y − 2
y x 0
1
2
3
4
5
6
7
8
9
10
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 F2
y x 0
1
2
3
4
5
6
7
0
0
1
2
3
4
5
6
7
x
1
F1 (F2 (0, 0), 2 (0, 0)+1)
F1 (F2 (1, 0), 2 (1, 0)+1)
F1 (F2 (2, 0), 2 (2, 0)+1)
F1 (F2 (3, 0), 2 (3, 0)+1)
F1 (F2 (4, 0), 2 (4, 0)+1)
F1 (F2 (5, 0), 2 (5, 0)+1)
F1 (F2 (6, 0), 2 (6, 0)+1)
F1 (F2 (7, 0), 2 (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)
1
8
27
74
185
440
1015
2294
2x+1 · (x + 2) − x − 3 lg 2·(x+1) + lg(x+2)
2
F1 (F2 (0, 1), 2 (0, 1)+2)
F1 (F2 (1, 1), 2 (1, 1)+2)
F1 (F2 (2, 1), 2 (2, 1)+2)
F1 (F2 (3, 1), 2 (3, 1)+2)
F1 (F2 (4, 1), 2 (4, 1)+2)
F1 (F2 (5, 1), 2 (5, 1)+2)
F1 (F2 (6, 1), 2 (6, 1)+2)
F1 (F2 (7, 1), 2 (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
22x+1 ·(x+2) − x − 1 · (2x+1 ·(x+2) − x − 1) − (2x+1 ·(x+2) − x + 1)lg 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)
3
F1 (F2 (0, 2), 2 (0, 2)+3)
F1 (F2 (1, 2), 2 (1, 2)+3)
F1 (F2 (2, 2), 2 (2, 2)+3)
F1 (F2 (3, 2), 2 (3, 2)+3)
F1 (F2 (4, 2), 2 (4, 2)+3)
F1 (F2 (5, 2), 2 (5, 2)+3)
F1 (F2 (6, 2), 2 (6, 2)+3)
F1 (F2 (7, 2), 2 (7, 2)+3)
F1 (F1 (1,3), 1 (1,3)+3)
F1 (F1 (8,10), 1 (8,10)+3)
F1 (F1 (27,29), 1 (27,29)+3)
F1 (F1 (74,76), 1 (74,76)+3)
F1 (F1 (185,187), 1 (185,187)+3)
F1 (F1 (440,442), 1 (440,442)+3)
F1 (F1 (1015,1017), 1 (1015,1017)+3)
F1 (F1 (2294,2297), 1 (2294,2297)+3)
F1 (19, 22)
F1 (10228, 10231)
F1 (15569256417,
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
longer expression, starts with 222x+1 an, ≈ 101010lg 2·(x+1) + lg(x+2)
4
F1 (F2 (0, 3), 2 (0, 3)+4)
F1 (F2 (1, 3), 2 (1, 3)+4)
F1 (F2 (2, 3), 2 (2, 3)+4)
F1 (F2 (3, 3), 2 (3, 3)+4)
F1 (F2 (4, 3), 2 (4, 3)+4)
F1 (F2 (5, 3), 2 (5, 3)+4)
F1 (F2 (6, 3), 2 (6, 3)+4)
F1 (F2 (7, 3), 2 (7, 3)+4)
F1 (F1 (19, 22), 1 (19, 22)+4)
F1 (F1 (10228, 1 (10228,
F1 (F1 (15569256417, 1 (15569256417,
F1 (F1 (≈5,74·1024 , ≈5,74·1024 ),1 (≈5,74·1024 , ≈5,74·1024 ))
F1 (F1 (≈3,67·1058 , ≈3,67·1058 ),1 (≈3,67·1058 , ≈3,67·1058 ))
F1 (F1 (≈5,02·10135 , ≈5,02·10135 ),1 (≈5,02·10135 , ≈5,02·10135 ))
F1 (F1 (≈1,43·10309 , ≈1,43·10309 ),1 (≈1,43·10309 , ≈1,43·10309 ))
F1 (F1 (≈3,36·10694 , ≈3,36·10694 ),1 (≈3,36·10694 , ≈3,36·10694 ))
F1 (88080360,
F1 (10230·210231 −10233,10231 −10229)
≈ 3,5 · 1026514839
much longer expression, starts with 2222x+1 an, ≈ 10101010lg 2·(x+1) + lg(x+2)
Values of F3
y x 0
1
2
3
4
0
0
1
2
3
4
x
1
F2 (F3 (0, 0), 3 (0, 0)+1)
F2 (F3 (1, 0), 3 (1, 0)+1)
F2 (F3 (2, 0), 3 (2, 0)+1)
F2 (F3 (3, 0), 3 (3, 0)+1)
F2 (F3 (4, 0), 3 (4, 0)+1)
F2 (0, 1)
F2 (1, 2)
F2 (2, 3)
F2 (3, 4)
F2 (4, 5)
1
10228
≈ 7,82 · 104686813201
No closed expressions possible within the framework of normal mathematical notation
2
F3 (F4 (0, 1), 4 (0, 1)+2)
F3 (F4 (1, 1), 4 (1, 1)+2)
F3 (F4 (2, 1), 4 (2, 1)+2)
F3 (F4 (3, 1), 4 (3, 1)+2)
F3 (F4 (4, 1), 4 (4, 1)+2)
F3 (1, 3)
F3 (10228, 10230)
F3 (≈104686813201 , 4686813201 )
No closed expressions possible within the framework of normal mathematical notation
Notes and references
^ The rightmost innermost occurrences of F are underlined.
Bibliography
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
External links
