“Sudan function”的意思、由来-开放百科全书

词条

Sudan function

释义

Definition
Value tables
References
External links

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. The Sudan function was the first function having this property to be published.

It was discovered (and published^[1]) in 1927 by Gabriel Sudan, a Romanian mathematician who was a student of David Hilbert.

Definition

Value tables

Values of 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

Values of F₁(x, y)
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

In general, F₁(x, y) is equal to F₁(0, y) + 2^y x.

Values of F₂(x, y)
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	1(27, 29) ≈ 1.55 {{e>10}}	1(74, 76) ≈ 5.74 {{e>24}}	1(185, 187) ≈ 3.67 {{e>58}}	1(440, 442) ≈ 5.02 {{e>135}}

References

Cristian Calude, Solomon Marcus, Ionel Tevy, The first example of a recursive function which is not primitive recursive, Historia Mathematica 6 (1979), no. 4, 380–384 {{doi|10.1016/0315-0860(79)90024-7}}

1. ^Bull. Math. Soc. Roumaine Sci. 30 (1927), 11 - 30; Jbuch 53, 171

External links

OEIS: A260003, A260004

4 : Arithmetic|Large integers|Special functions|Theory of computation

随便看

开放百科全书收录14589846条英语、德语、日语等多语种百科知识，基本涵盖了大多数领域的百科知识，是一部内容自由、开放的电子版国际百科全书。