查看“︁苏丹函数”︁的源代码

'''苏丹函数'''（{{Lang|en|Sudan function}}），是[[递归]]函数，但如同[[阿克曼函数]]，不能通過[[μ算子]]定義更廣泛的[[偏遞歸函數]]類，因而不是[[原始递归]][[函数]]{{Sfn|Ackermann|1928}}。苏丹函数是第一个具有此属性的函数{{Sfn|Calude|Marcus|Tevy|1979}}。

它于1927年由[[大卫·希尔伯特]]的学生[[羅馬尼亞]][[数学家]][[加布里埃尔苏丹]]发现并发表{{Sfn|Sudan|1927}}。

== 定义 ==

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

== 數值 ==
{| class="wikitable"
|+''F''<sub>0</sub>值(''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
|}

{| class="wikitable"
|+''F''<sub>1</sub>值(''x'' ,''y''）
! ''y''\''x''
!0
!1
!2
!3
!4
!5
!6
!7
!8
!9
!10
!11
!12
!13
!14
|-
!0
|0
|1
|2
|3
|4
|5
|6
|7
|8
|9
|10
|11
|12
|13
|14
|-
!1
|1
|3
|5
|7
|9
|11
|13
|15
|17
|19
|21
|23
|25
|27
|29
|-
!2
|4
|8
|12
|16
|20
|24
|28
|32
|36
|40
|44
|48
|52
|56
|60
|-
!3
|11
|19
|27
|35
|43
|51
|59
|67
|75
|83
|91
|99
|107
|115
|123
|-
!4
|26
|42
|58
|74
|90
|106
|122
|138
|154
|170
|186
|202
|218
|234
|250
|- 
!5
|57
|89
|121
|153
|185
|217
|249
|281
|313
|345
|377
|409
|441
|473
|505
|-
!6
|120
|184
|248
|312
|376
|440
|504
|568
|632
|696
|760
|824
|888
|952
|1016
|-
!7
|247
|375
|503
|631
|759
|887
|1015
|1143
|1271
|1399
|1527
|1655
|1783
|1911
|2039
|-
!8
|502
|758
|1014
|1270
|1526
|1782
|2038
|2294
|2550
|2806
|3062
|3318
|3574
|3830
|4086
|-
!9
|1013
|1525
|2037
|2549
|3061
|3573
|4085
|4597
|5109
|5621
|6133
|6645
|7157
|7669
|8181
|-
!10
|2036
|3060
|4084
|5108
|6132
|7156
|8180
|9204
|10228
|11252
|12276
|13300
|14324
|15348
|16372
|-
!11
|4083
|6131
|8179
|10227
|12275
|14323
|16371
|18419
|20467
|22515
|24563
|26611
|28659
|30707
|32755
|-
!12
|8178
|12274
|16370
|20466
|24562
|28658
|32754
|36850
|40946
|45042
|49138
|53234
|57330
|61426
|65522
|-
!13
|16369
|24561
|32753
|40945
|49137
|57329
|65521
|73713
|81905
|90097
|98289
|106481
|114673
|122865
|131057
|-
!14
|32752
|49136
|65520
|81904
|98288
|114672
|131056
|147440
|163824
|180208
|196592
|212976
|229360
|245744
|262128
|}

{| class="wikitable"
|+''F''<sub>2</sub>值(''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 <sub>1</sub> (8, 10) = 10228
| F <sub>1</sub> (27, 29) ≈ 1.55 {{Exp10|10}}  
| F <sub>1</sub> (74, 76) ≈ 5.74 {{Exp10|24}}  
| F <sub>1</sub> (185, 187) ≈ 3.67 {{Exp10|58}}  
| F <sub>1</sub> (440, 442) ≈ 5.02 {{Exp10|135}}  
|}

== 注释和参考 ==
{{Reflist}}

== 参考书目 ==
{{refbegin}}

*{{cite journal|title=Zum Hilbertschen Aufbau der reellen Zahlen|url=http://gdz.sub.uni-goettingen.de/en/dms/loader/img/?PPN=PPN235181684_0099&DMDID=DMDLOG_0009|last=[[Wilhelm Ackermann|Ackermann]]|first=Wilhelm|journal=[[Mathematische Annalen]]|doi=10.1007/BF01459088|year=1928|volume=99|pages=118–133|jfm=54.0056.06|s2cid=123431274|access-date=2022-03-12|archive-date=2016-04-11|archive-url=https://web.archive.org/web/20160411105229/http://gdz.sub.uni-goettingen.de/en/dms/loader/img/?PPN=PPN235181684_0099&DMDID=DMDLOG_0009}}

* {{cite journal|title=The first example of a recursive function which is not primitive recursive|first1=Cristian|last2=[[Solomon Marcus|Marcus]]|first2=Solomon|journal=[[Historia Mathematica]]|issue=4|doi=10.1016/0315-0860(79)90024-7|year=1979|volume=6|pages=380-384|last3=Tevy|first3=Ionel|last1=[[Cristian S. Calude|Calude]]|doi-access=free}}

* {{cite journal|title=Sur le nombre transfini ω<sup>ω</sup>|last=[[Gabriel Sudan|Sudan]]|first=Gabriel|journal=Bulletin mathématique de la Société Roumaine des Sciences|year=1927|volume=30|pages=11-30|jfm=53.0171.01|jstor=43769875|quote=Jbuch 53, 171}}

{{refend}}

== 外部链接 ==
* OEIS: [[oeis:A260003|A260003]], [[oeis:A260004|A260004]]

[[Category:計算理論]]
[[Category:特殊函数]]
[[Category:大整数]]
[[Category:算术]]