Primitive rekursive Funktionen und Ackerman-Funktion

Ackermans Funktion ist eines der bekanntesten Merkmale der Informatik. Es ist mit mindestens einem fundamentalen Ergebnis und mindestens einem einfach wichtigen Ergebnis verbunden. Das grundlegende Ergebnis, um es ordentlich und unverständlich auszudrücken, ist folgendes: Es gibt überall eine bestimmte berechenbare Funktion, die nicht primitiv rekursiv ist. Ein wichtiges Ergebnis ist, dass der Wald disjunkter Mengen (auch als disjunkte Mengenvereinigung bezeichnet ) sehr schnell ist .

Ich mag es wirklich, die Funktion von Ackerman zu studieren, als Alles, was damit verbunden ist, ist sehr schön und elegant. Das oben aufgezeichnete fundamentale Ergebnis ist also viel einfacher zu verstehen, als es scheint.

Aus dem folgenden Text erfahren Sie, was primitive rekursive Funktionen sind und wie Sie herausfinden, dass die Akkerman-Funktion für sie nicht gilt. Und natürlich wird dieser Text Sie davon überzeugen, dass es sich um ein unglaublich schönes Design und eine unglaublich schöne Argumentation handelt!

1. Warum es interessant sein kann

Die Diskussion der Beziehung zwischen primitiven rekursiven Funktionen und der Ackerman-Funktion ist ein Beispiel für die Lösung eines Standardproblems in der Berechenbarkeitstheorie: Ein bestimmtes Berechnungsmodell, eine bestimmte Funktion sind angegeben, und es muss bestimmt werden, ob diese Funktion in diesem Modell berechenbar ist.

Andere ähnliche Beispiele sind beispielsweise mit der algorithmischen Entscheidbarkeit , der Äquivalenz verschiedener Rechenmodelle (Turing-Maschinen, teilweise rekursive Funktionen, normale Markov-Algorithmen usw.) verbunden. Und durch sie sind wir bereits mit einem völlig praktischen Definitionsbereich für die Vollständigkeit von Programmiersprachen, äquivalenten Transformationen von Programmtexten und anderen interessanten Dingen verbunden.

Ackermans Funktion scheint speziell geschaffen worden zu sein, um ein elegantes Beispiel für die Lösung solcher Probleme zu sein. Sie werden es bald sehen.

2. Ackerman-Funktion

, « ». , , , .

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

Solche Aussagen für die Analysis zu beweisen, ist eine Freude. Zuerst beweisen wir es für grundlegende Funktionen und überprüfen dann, ob die Eigenschaft beim Anwenden von Operationen erhalten bleibt.

Nun, für grundlegende Operationen ist alles klar:

$$

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

Im ersten Fall verwenden wir die Tatsache, dass die Identität Null immer kleiner als Eins ist, und sogar die Funktion $$$a_0$fügt seinem Argument eins hinzu (denken Sie daran: Wir befinden uns in einer diskreten Welt, hier sind alle Argumente entweder natürliche Zahlen oder Null). Im zweiten Fall ist das Hinzufügen von eins genau das Ergebnis der Anwendung der Funktion$$$a_0$Das ist monoton weniger als eine Funktion $$$a_1$. Im dritten Fall gibt die Projektionsfunktion eines ihrer Argumente zurück, das genau kleiner als das Maximum aller Argumente ist und um eins erhöht wird.

. : , , , , .

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

,

$$

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

:

$$

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

. , , .

5. ,

, , - $$$a_M$, . :

$$

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

, , : , — . , .

: $$$A$-.

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

$$

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

, -. - , ! .

6. ?

, , - , . , . $$$n^n$. ,

$$

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

mit einer vorbestimmten Anzahl von Exponenten ist primitiv rekursiv. Ich werde nicht faul sein und es beweisen. Zu Beginn werde ich eine Funktion erstellen$$$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)$$

Jetzt benutze ich es, um eine Funktion zu definieren $$$n^n$::

$$

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

Wie Sie sehen können, erfolgt dies durch einfaches Ersetzen. Jetzt gibt es keine Schwierigkeit mehr, eine Funktion zu definieren$$$n^{n^n}$::

$$

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

In Analogie können wir eine Funktion konstruieren, in der $$$n$zur Macht erhoben $$$n$fünfmal, zehnmal, hundertmal, eine Millionmal. Ackermans Funktion wächst schneller als jede dieser Funktionen. So schnell wächst es!