Funcția Sudan

În teorie calculabilitate, Sudan funcția este un total non primitiv funcție recursivă .

Funcția a fost prima care a respins credința că funcțiile recursive erau neapărat primitive. Descoperirea este atribuită matematicianului Gabriel Sudan , student al lui David Hilbert în 1927, cu câțiva ani înainte de cea a celei mai cunoscute funcții a lui Ackermann .

Definiție

Lasa-i sa fie $n,x,y\in \mathbb {N}$ ${\ displaystyle n, x, y \ in \ mathbb {N}}$ ${\ displaystyle n, x, y \ in \ mathbb {N}}$

$F_{0}(x,y)=x+y,$ ${\ displaystyle F_ {0} (x, y) = x + y,}$ ${\ displaystyle F_ {0} (x, y) = x + y,}$

$F_{n+1}(x,0)=x,$ ${\ displaystyle F_ {n + 1} (x, 0) = x,}$ ${\ displaystyle F_ {n + 1} (x, 0) = x,}$

$F_{n+1}(x,y+1)=F_{n}(F_{n+1}(x,y),F_{n+1}(x,y)+y+1).$ ${\ displaystyle F_ {n + 1} (x, y + 1) = F_ {n} (F_ {n + 1} (x, y), F_ {n + 1} (x, y) + y + 1) .}$ ${\ displaystyle F_ {n + 1} (x, y + 1) = F_ {n} (F_ {n + 1} (x, y), F_ {n + 1} (x, y) + y + 1) .}$

Tabelul valorilor

Valorile lui F ₀ ( x , y )
y \ x	0	1	2	3	4	5
0	0	1	2	3	4	5
1	1	2	3	4	5	6
2	2	3	4	5	6	7
3	3	4	5	6	7	8
4	4	5	6	7	8	9
5	5	6	7	8	9	10
6	6	7	8	9	10	11

Valorile lui F ₁ ( x , y ) (OEIS: A260003 )
y \ x	0	1	2	3	4	5	6
0	0	1	2	3	4	5	6
1	1	3	5	7	9	11	13
2	4	8	12	16	20	24	28
3	11	19	27	35	43	51	59
4	26	42	58	74	90	106	122
5	57	89	121	153	185	217	249
6	120	184	248	312	376	440	504

Avem: $F_{1}(x,y)=F_{1}(0,y)+2^{y}x$ ${\ displaystyle F_ {1} (x, y) = F_ {1} (0, y) + 2 ^ {y} x}$ ${\ displaystyle F_ {1} (x, y) = F_ {1} (0, y) + 2 ^ {y} x}$ .

Valorile lui F ₂ ( x , y ) (OEIS: A260004 )
y \ x	0	1	2	3	4	5
0	0	1	2	3	4	5
1	1	8	27	74	185	440
2	19	F ₁ (8, 10) = 10228	F ₁ (27, 29) ≈ 1,55 × 10 ¹⁰	F ₁ (74, 76) ≈ 5,74 × 10 ²⁴	F ₁ (185, 187) ≈ 3,67 × 10 ⁵⁸	F ₁ (440, 442) ≈ 5,02 × 10 ¹³⁵

Bibliografie

Cristian Calude, Solomon Marcus și Ionel Tevy, Primul exemplu de funcție recursivă care nu este recursivă primitivă , Historia Mathematica 6, 1979, nr. 4, 380–384 doi : 10.1016 / 0315-0860 (79) 90024-7.
Funcția Sudan - Salt în sus Bull. Matematica. Soc. Roumaine Sci. 30, 1927, 11 - 30; Jbuch 53, 171.

Portalul de matematică : accesați intrările Wikipedia care se ocupă de matematică

y \ x	0	1	2	3	4	5	6
0	0	1	2	3	4	5	6
1	1	3	5	7	9	11	13
2	4	8	12	16	20	24	28
3	11	19	27	35	43	51	59
4	26	42	58	74	90	106	122
5	57	89	121	153	185	217	249
6	120	184	248	312	376	440	504

y \ x	0	1	2	3	4	5	6
0	0	1	2	3	4	5	6
1	1	3	5	7	9	11	13
2	4	8	12	16	20	24	28
3	11	19	27	35	43	51	59
4	26	42	58	74	90	106	122
5	57	89	121	153	185	217	249
6	120	184	248	312	376	440	504

y \ x	0	1	2	3	4	5	6
0	0	1	2	3	4	5	6
1	1	3	5	7	9	11	13
2	4	8	12	16	20	24	28
3	11	19	27	35	43	51	59
4	26	42	58	74	90	106	122
5	57	89	121	153	185	217	249
6	120	184	248	312	376	440	504