Функция Судана

В теории вычислений функция Судана является примером функции , которая является рекурсивной , но не примитивно-рекурсивной . Это также справедливо и для более известной функции Аккермана .

В 1926 году Дэвид Гильберт предположил, что каждая вычислимая функция примитивно-рекурсивна. Это было опровергнуто Габриэлем Суданом и Вильгельмом Аккерманом — оба его ученики — с использованием различных статей, которые были опубликованы в быстрой последовательности: Судан в 1927 году, Аккерманн в 1928 году.

Функция Судана — самый ранний опубликованный пример рекурсивной функции, которая не является примитивно-рекурсивной.

Определение

${\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}}$

Последнее уравнение можно эквивалентно записать как

${\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}}$.

Вычисление

Эти уравнения можно использовать как правила системы переписывания терминов (TRS) .

Обобщенная функция $F(x,y,n){\stackrel {\mathrm {def} }{=}}F_{n}(x,y)$ приводит к правилам перезаписи

${\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}}$

На каждом шаге редукции самое правое и внутреннее вхождение F перезаписывается применением одного из правил (r1) - (r3).

Калуд (1988) приводит пример : вычисление $F(2,2,1)\rightarrow _{*}12$.

Последовательность сокращения

${\underline {F(2,2,1)}}$

$\rightarrow _{r3}F(F(2,1,1),F({\underline {F(2,1,1)}},2,0),0)$

$\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)$

$\rightarrow _{r2}F(F(2,1,1),F(F(F(2,0,1),{\underline {F(2,1,0)}},0),2,0),0)$

$\rightarrow _{r1}F(F(2,1,1),F(F({\underline {F(2,0,1)}},3,0),2,0),0)$

$\rightarrow _{r2}F(F(2,1,1),F({\underline {F(2,3,0)}},2,0),0)$

$\rightarrow _{r1}F(F(2,1,1),{\underline {F(5,2,0)}},0)$

$\rightarrow _{r1}F({\underline {F(2,1,1)}},7,0)$

$\rightarrow _{r3}F(F(F(2,0,1),F({\underline {F(2,0,1)}},1,0),0),7,0)$

$\rightarrow _{r2}F(F(F(2,0,1),{\underline {F(2,1,0)}},0),7,0)$

$\rightarrow _{r1}F(F({\underline {F(2,0,1)}},3,0),7,0)$

$\rightarrow _{r2}F({\underline {F(2,3,0)}},7,0)$

$\rightarrow _{r1}{\underline {F(5,7,0)}}$

$\rightarrow _{r1}12$

Конкретные реализации можно найти на Rosetta Code .

Таблицы значений

Значения F ₀

F ₀ ( Икс , y ) знак равно Икс + y

и \ х	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

Значения F ₁

F1 _Икс ( ) знак равно , у 2 ^и · (х + 2) - у - 2

и \ х	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

Значения F ₂

и \ х	0	1	2	3	4	5	6	7
0	0	1	2	3	4	5	6	7
	х
1	Ф 1 (Ф 2 (0, 0), Ф 2 (0, 0)+1)	Ф 1 (Ф 2 (1, 0), Ф 2 (1, 0)+1)	Ф 1 (Ф 2 (2, 0), Ф 2 (2, 0)+1)	Ф 1 (Ф 2 (3, 0), Ф 2 (3, 0)+1)	Ф 1 (Ф 2 (4, 0), Ф 2 (4, 0)+1)	Ф 1 (Ф 2 (5, 0), Ф 2 (5, 0)+1)	Ф 1 (Ф 2 (6, 0), Ф 2 (6, 0)+1)	Ф 1 (Ф 2 (7, 0), Ф 2 (7, 0)+1)
	Ф 1 (0, 1)	Ф 1 (1, 2)	Ф 1 (2, 3)	Ф 1 (3, 4)	Ф 1 (4, 5)	Ф 1 (5, 6)	Ф 1 (6, 7)	Ф 1 (7, 8)
	1	8	27	74	185	440	1015	2294
	2 х+1 · (х + 2) - х - 3 ≈ 10 lg 2·(x+1) + lg(x+2)
2	Ф 1 (Ф 2 (0, 1), Ф 2 (0, 1)+2)	Ф 1 (Ф 2 (1, 1), Ф 2 (1, 1)+2)	Ф 1 (Ф 2 (2, 1), Ф 2 (2, 1)+2)	Ф 1 (Ф 2 (3, 1), Ф 2 (3, 1)+2)	Ф 1 (Ф 2 (4, 1), Ф 2 (4, 1)+2)	Ф 1 (Ф 2 (5, 1), Ф 2 (5, 1)+2)	Ф 1 (Ф 2 (6, 1), Ф 2 (6, 1)+2)	Ф 1 (Ф 2 (7, 1), Ф 2 (7, 1)+2)
	Ф 1 (1, 3)	Ф 1 (8, 10)	Ф 1 (27, 29)	Ф 1 (74, 76)	Ф 1 (185, 187)	Ф 1 (440, 442)	Ф 1 (1015, 1017)	Ф 1 (2294, 2296)
	19	10228	15569256417	≈ 5,742397643 · 10 24	≈ 3,668181327 · 10 58	≈ 5,019729940 · 10 135	≈ 1,428323374 · 10 309	≈ 3,356154368 · 10 694
	2 2 х+1 ·(х+2) - х - 1 · (2 х+1 ·(x+2) − x − 1) − (2 х+1 ·(х+2) - х + 1) ≈ 10 LG 2 · (2 х+1 ·(x+2) − x − 1) + lg(2 х+1 ·(х+2) - х - 1) ≈ 10 LG 2 · 2 х+1 ·(x+2) + lg(2 х+1 ·(х+2)) ≈ 10 LG 2 · (2 х+1 ·(х+2)) = 10 10 lg lg 2 + lg 2·(x+1) + lg(x+2) ≈ 10 10 lg 2·(x+1) + lg(x+2)
3	Ф 1 (Ф 2 (0, 2), Ф 2 (0, 2)+3)	Ф 1 (Ф 2 (1, 2), Ф 2 (1, 2)+3)	Ф 1 (Ф 2 (2, 2), Ф 2 (2, 2)+3)	Ф 1 (Ф 2 (3, 2), Ф 2 (3, 2)+3)	Ф 1 (Ф 2 (4, 2), Ф 2 (4, 2)+3)	Ф 1 (Ф 2 (5, 2), Ф 2 (5, 2)+3)	Ф 1 (Ф 2 (6, 2), Ф 2 (6, 2)+3)	Ф 1 (Ф 2 (7, 2), Ф 2 (7, 2)+3)
	Ф 1 (Ф 1 (1,3), Ф 1 (1,3)+3)	Ф 1 (Ф 1 (8,10), Ф 1 (8,10)+3)	Ф 1 (Ф 1 (27,29), Ф 1 (27,29)+3)	Ф 1 (Ф 1 (74,76), Ф 1 (74,76)+3)	Ф 1 (Ф 1 (185 187), Ф 1 (185,187)+3)	Ф 1 (Ф 1 (440 442), Ф 1 (440 442)+3)	Ф 1 (Ф 1 (1015,1017), Ф 1 (1015,1017)+3)	Ф 1 (Ф 1 (2294,2297), Ф 1 (2294,2297)+3)
	Ф 1 (19, 22)	Ф 1 (10228, 10231)	Ф 1 (15569256417, 15569256420)	Ф 1 (≈6·10 24 , ≈6·10 24 )	Ф 1 (≈4·10 58 , ≈4·10 58 )	Ф 1 (≈5·10 135 , ≈5·10 135 )	Ф 1 (≈10 309 , ≈10 309 )	Ф 1 (≈3·10 694 , ≈3·10 694 )
	88080360	≈ 7,04 · 10 3083	≈ 7,82 · 10 4686813201	≈ 10 1,72·10 24	≈ 10 1,10·10 58	≈ 10 1,51·10 135	≈ 10 4,30·10 308	≈ 10 1,01·10 694
	более длинное выражение, начинается с 2 2 2 х+1 ан, ≈ 10 10 10 lg 2·(x+1) + lg(x+2)
4	Ф 1 (Ф 2 (0, 3), Ф 2 (0, 3)+4)	Ф 1 (Ф 2 (1, 3), Ф 2 (1, 3)+4)	Ф 1 (Ф 2 (2, 3), Ф 2 (2, 3)+4)	Ф 1 (Ф 2 (3, 3), Ф 2 (3, 3)+4)	Ф 1 (Ф 2 (4, 3), Ф 2 (4, 3)+4)	Ф 1 (Ф 2 (5, 3), Ф 2 (5, 3)+4)	Ф 1 (Ф 2 (6, 3), Ф 2 (6, 3)+4)	Ф 1 (Ф 2 (7, 3), Ф 2 (7, 3)+4)
	Ф 1 (Ф 1 (19, 22), Ф 1 (19, 22)+4)	Ф 1 (Ф 1 (10228, 10231),   Ф 1 (10228, 10231)+4)	Ф 1 (Ф 1 (15569256417, 15569256420),   Ф 1 (15569256417, 15569256420)+4)	Ф 1 (Ф 1 (≈5,74·10 24 , ≈5,74·10 24 ), Ф 1 (≈5,74·10 24 , ≈5,74·10 24 ))	Ф 1 (Ф 1 (≈3,67·10 58 , ≈3,67·10 58 ), Ф 1 (≈3,67·10 58 , ≈3,67·10 58 ))	Ф 1 (Ф 1 (≈5,02·10 135 , ≈5,02·10 135 ), Ф 1 (≈5,02·10 135 , ≈5,02·10 135 ))	Ф 1 (Ф 1 (≈1,43·10 309 , ≈1,43·10 309 ), Ф 1 (≈1,43·10 309 , ≈1,43·10 309 ))	Ф 1 (Ф 1 (≈3,36·10 694 , ≈3,36·10 694 ), Ф 1 (≈3,36·10 694 , ≈3,36·10 694 ))
	Ф 1 (88080360, 88080364)	Ф 1 (10230·2 10231 −10233, 10230·2 10231 −10229)
	≈ 3,5 · 10 26514839
	гораздо более длинное выражение, начинается с 2 2 2 2 х+1 ан, ≈ 10 10 10 10 lg 2·(x+1) + lg(x+2)

Значения F ₃

и \ х	0	1	2	3	4
0	0	1	2	3	4
	х
1	Ф 2 (Ф 3 (0, 0), F 3 (0, 0)+1)	Ф 2 (Ф 3 (1, 0), F 3 (1, 0)+1)	Ф 2 (Ф 3 (2, 0), F 3 (2, 0)+1)	Ф 2 (Ф 3 (3, 0), F 3 (3, 0)+1)	Ф 2 (Ф 3 (4, 0), F 3 (4, 0)+1)
	Ф2 ) (0, 1	Ф 2 (1, 2)	Ф 2 (2, 3)	Ф 2 (3, 4)	Ф 2 (4, 5)
	1	10228	≈ 7,82 · 10 4686813201
	В рамках обычной математической записи невозможны замкнутые выражения.
2	Ф 3 (Ф 4 (0, 1), Ф 4 (0, 1)+2)	Ф 3 (Ф 4 (1, 1), Ф 4 (1, 1)+2)	Ф 3 (Ф 4 (2, 1), Ф 4 (2, 1)+2)	Ф 3 (Ф 4 (3, 1), Ф 4 (3, 1)+2)	Ф 3 (Ф 4 (4, 1), Ф 4 (4, 1)+2)
	F 3  (1, 3)	F 3  (10228, 10230)	F 3  (≈10 4686813201 ,  ≈10 4686813201 )
	В рамках обычной математической записи невозможны замкнутые выражения.

Библиография

• Акерманн , Вильгельм (1928). «О гильбертовой структуре действительных чисел» . Математические летописи . 99 : 118–133. дои : 10.1007/BF01459088 . ЖФМ   54.0056.06 . S2CID   123431274 .

• Калуде, Кристиан ; Маркус, Соломон ; Теви, Ионел (1979). «Первый пример рекурсивной функции, которая не является примитивно-рекурсивной» . История Математики . 6 (4): 380–384. дои : 10.1016/0315-0860(79)90024-7 .

• Калуде, Кристиан (1988). Теории вычислительной сложности . Амстердам: Северная Голландия . ISBN  978-0-444-70356-9 .

• Судан , Габриэль (1927). «О трансфинитном числе ω ^ой ". Математический бюллетень Румынского общества наук 30 : 11–30. JFM   53.0171.01 . JSTOR   43769875. . Jbuch 53, 171.

Внешние ссылки

• Розеттский кодекс . «Функция Судана» .

• ОЭИС: A260003 , A260004