Fungsi rekursif primitif dan fungsi Ackerman

Fungsi Ackerman adalah salah satu fitur paling terkenal dalam Ilmu Komputer. Ini dikaitkan dengan setidaknya satu hasil mendasar dan setidaknya satu hasil yang cukup penting. Hasil mendasar, untuk membuatnya lebih rapi dan tidak dapat dipahami, adalah sebagai berikut: ada fungsi komputasi yang didefinisikan di mana-mana yang tidak bersifat rekursif primitif. Hasil penting adalah bahwa hutan set disjoint (juga dikenal sebagai persatuan set disjoint) sangat cepat .

Saya sangat suka mempelajari fungsi Ackerman, sebagai semuanya terhubung dengan itu sangat indah dan elegan. Jadi hasil fundamental yang dicatat di atas jauh lebih mudah dipahami daripada yang terlihat.

Dari teks di bawah ini Anda akan mempelajari apa fungsi rekursif primitif dan bagaimana mengetahui bahwa fungsi Akkerman tidak berlaku untuk mereka. Dan, tentu saja, teks ini akan meyakinkan Anda bahwa itu adalah desain yang sangat indah dan alasan yang sangat indah!

1. Mengapa ini mungkin menarik

Diskusi tentang hubungan antara fungsi rekursif primitif dan fungsi Ackerman adalah contoh pemecahan masalah standar dalam teori komputabilitas: model perhitungan tertentu, fungsi tertentu diberikan, dan perlu untuk menentukan apakah fungsi ini dapat dihitung dalam model ini.

Contoh serupa lainnya dikaitkan, misalnya, dengan decidability algoritmik , kesetaraan berbagai model komputasi (mesin Turing, fungsi rekursif parsial, algoritma Markov normal, dan sebagainya). Dan melalui mereka kita sudah terhubung dengan area definisi praktis untuk kelengkapan Turing bahasa pemrograman, transformasi setara teks program dan hal-hal menarik lainnya.

Fungsi Ackerman tampaknya telah diciptakan secara khusus untuk menjadi contoh yang elegan untuk memecahkan masalah tersebut. Anda akan segera melihatnya.

2. Fungsi Ackerman

, « ». , , , .

$$$a_0, a_1, ..., a_n, ...$. :

$$

$$a_0(x) = x + 1$$

$$

$$a_{i+1}(x) = a_{i}[x+2](x)$$

$$$f[n](x) = f\Big(f(...(f(x))...)\Big)$— $$$n$, $$$n$. , : , $$$x+2$$$$x$— $$$x$.

, — , .

:

def Foo(number, argument):
    if number == 0:
        return argument + 1

    result = argument
    for i in range(argument + 2):
        result = Foo(number - 1, result)

    return result

$$$a_i(x)$Foo(i, x).

. -, : $$$a_i(x) > x$$$$i$$$$x$. , , $$$a_0(x) = x + 1 > x$, $$$a_0$.

-, : $$$a_{i+1}(x) \gt a_i(x)$$$$i$$$$x$. , — , . :

$$

$$a_{i+1}(x) = a_i[x+2](x) \ge a_i[2](x) = a_i\Big(a_i(x)\Big) > a_i(x)$$

,

$$

$$a_{i+1}(x) \ge a_i\Big(a_i(x)\Big)$$

3. - ()

« ». — . : , , , .

- ? «». - :

1. , : $$$Null(x_1,x_2,...,x_k) = 0$
2. : $$$S(x)=x+1$
3. -: $$$P_k^i(x_1, x_2,...,x_k)=x_i$

. « »:

• . $$$f$— $$$k$, $$$g_1,g_2,...,g_k$— $$$n$, $$$n$$$$F$: $$$n$, $$$k$$$$g_1,...,g_k$, $$$f$. !

$$

$$F(x_1,...,x_n)=f\Big(g_1(x_1,...,x_n),...,g_k(x_1,...,x_n)\Big)$$

• . $$$f$— $$$k$, $$$g$— $$$k+2$, , :

$$

$$F(x_1,...,x_k,0)=f(x_1,...,x_k)$$

$$

$$F(x_1,...,x_k,y+1)=g\Big(x_1,...,x_k,y,F(x_1,...,x_k,y)\Big)$$

, . : , . : , , . , .. , .

, — , , .

.

, . , . , :

$$

$$Sum(x,0)=P_1^1(x)$$

$$

$$Sum(x,y+1)=S\Big(P_3^3(x,y,Sum(x,y))\Big)$$

— , . , . $$$Sum(x,0)=x$, , .. $$$x$. $$$P_1^1$. , : $$$x,y,Sum(x,y)$. , $$$P_3^3$, .

:

$$

$$Mult(x,0)=Null(x)$$

$$

$$Mult(x,y+1)=Sum\Big(P_3^1(x,y,Mult(x,y)),P_3^3(x,y,Mult(x,y))\Big)$$

- . , ! , :

$$$Fib_0 = 0$
$$$Fib_1 = 1$
$$$Fib_{n+2} = Fib_n + Fib_{n+1}$

, ; , !

, . , $$$F$, . , $$$G$, , :

$$$F(n) = Fib_n$
$$$G(n) = Fib_{n+1}$

$$$F$0, 1, 1, 2, 3, 5; $$$G$, , 1, 1, 2, 3, 5, 8. :
$$$G(n+1) = G(n) + F(n)$
$$$F(n+1) = G(n)$

:

$$

$$F(0)=Null()$$

$$

$$G(0)=S(Null())$$

$$

$$F(y+1)=P_2^1\Big(G(y),F(y)\Big)$$

$$

$$G(y+1)=Sum\Big(F(y),G(y)\Big)$$

:

def G(x):
    if x == 0:
        return 1
    return G(x - 1) + F(x - 1)

def F(x):
    if x == 0:
        return 0
    return G(x - 1)

, , , , $$$n$- - !

4. ,

, - « » . : - $$$k$$$$f$$$$n$, :

$$

$$f(x_1,...,x_k)<a_n(max(x_1,...,x_k))$$

— . , , .

, :

$$

$$Null(x_1,...,x_k)=0<max(x_1,...,x_k) + 1=a_0(max(x_1,...,x_k))$$

$$

$$S(x)=x+1=a_0(x)<a_1(x)$$

$$

$$P_k^i(x_1,...,x_k)=x_i\le max(x_1,...,x_k)<a_0\Big(max(x_1,...,x_k)\Big)$$

, , $$$a_0$(: , , ). — $$$a_0$, $$$a_1$. - , , , .

. : , , , , .

$$$F$$$$f,g_1,...,g_k$, $$$a_M$. , $$$F$. :

$$

$$F(x_1,...,x_n)=f\Big(g_1(x_1,...,x_n),...,g_k(x_1,...,x_n)\Big)<$$

$$

$$<a_M\Big(max(g_1(x_1,...,x_n),...,g_k(x_1,...,x_n))\Big)<$$

$$

$$<a_M\Big[max\Big(a_M(max(x_1,...,x_n)),...,a_M(max(x_1,...,x_n))\Big)\Big]$$

$$

$$<a_M\Big(a_M(max(x_1,...,x_n))\Big) \le a_{M+1}\Big(max(x_1,...,x_n)\Big)$$

$$$f$, $$$g_i$, $$$k$, . $$$a_M$, $$$a_{M+1}$.

$$$F$$$$f$$$$g$, $$$a_M$.

, , . : $$$f$:

$$

$$F(x_1,...,x_k,0)=f(x_1,...,x_k)<a_M\Big(max(x_1,...,x_k)\Big)$$

, , :

$$

$$F(x_1,...,x_k,1)=g\Big(x_1,...,x_k,0,F(x_1,...,x_k,0)\Big)<$$

$$

$$<a_M\Big(max(x_1,...,x_k,0,a_M(max(x_1,...,x_k))\Big)<$$

$$

$$<a_M\Big(a_M(max(x_1,...,x_k)\Big)=a_M[2](max(x_1,...,x_k))$$

$$$F$, $$$g$. $$$a_M$: ,

$$

$$a_M\Big(max(x_1,...,x_k)\Big)>max(x_1,...,x_k, 0)$$

, ,

$$

$$F(x_1,...,x_k,y)<a_M[y+1](max(x_1,...,x_k))$$

Dan properti dari urutan fungsi yang diperkenalkan menjamin hal itu

$$

$$a_M[y+1](max(x_1,...,x_k))<a_{M+1}\Big(max(x_1,...,x_k,y)\Big)$$

Akhirnya:

$$

$$F(x_1,...,x_k,y)<a_{M+1}\Big(max(x_1,...,x_k,y)\Big)$$

Dan di sinilah bukti kita selesai. Sangat lucu bahwa ternyata setiap aplikasi komposisi atau rekursi primitif meningkatkan jumlah fungsi yang diperlukan oleh kondisi pernyataan oleh satu.

5. Fungsi Ackerman dan PRF, bagian dua

Jadi, kita tahu bahwa untuk fungsi rekursif primitif ada fungsi $$$a_M$yang akan tumbuh lebih cepat. Sekarang Anda dapat mendefinisikan fungsi berikut:

$$

$$A(n)=a_n(n)$$

Bahkan, dengan memperkenalkan urutan fungsi dari satu argumen, kami memperkenalkan fungsi dari dua argumen: yang pertama menetapkan nomor fungsi dalam urutan, yang kedua - argumen itu sendiri. Menyamakan angka dan argumen, kita mendapatkan fungsi dari satu argumen.

: $$$A$-.

, , -. 4 $$$M$, $$$A(x)<a_M(x)$$$$x$. , :

$$

$$A(M+1)=a_{M+1}(M+1)>a_M(M+1)$$

, -. - , ! .

6. ?

, , - , . , . $$$n^n$. Apalagi fungsi dari bentuk apa pun

$$

$$n^{n^{...^{n^n}}}$$

dengan jumlah eksponen yang telah ditentukan, bersifat primitif rekursif. Saya tidak akan malas dan membuktikannya. Untuk memulai, saya akan membangun sebuah fungsi$$$n^y$:

$$

$$Pow(n,0)=S(Null())$$

$$

$$Pow(n,y+1)=Mult\Big(P_3^1(n,y,Pow(n,y)),P_3^3(n,y,Pow(n,y))\Big)$$

Sekarang saya menggunakannya untuk mendefinisikan suatu fungsi $$$n^n$:

$$

$$SPow(n)=Pow(P_1^1(n),P_1^1(n))$$

Seperti yang Anda lihat, ini dilakukan dengan substitusi sederhana. Sekarang tidak ada kesulitan dalam mendefinisikan suatu fungsi$$$n^{n^n}$:

$$

$$SSPow(n)=Pow(P_1^1(n),SPow(n))$$

Dengan analogi, kita dapat membangun suatu fungsi di mana $$$n$diangkat ke kekuasaan $$$n$lima kali, sepuluh kali, seratus kali, sejuta kali. Fungsi Ackerman tumbuh lebih cepat daripada fungsi-fungsi ini. Begitulah cepatnya pertumbuhannya!