Welche Bedeutung haben primitive rekursive Funktionen?

Ich studierte den Beweis, dass die Ackermann-Funktion rekursiv, aber nicht primitiv rekursiv ist, und eine Frage traf mich: "Na und?". Warum spielt es eine Rolle? Welche Bedeutung haben primitive rekursive Funktionen?

Das Problem des Anhaltens ist unentscheidbar, aber man könnte einwenden, dass es für die meisten Programme einfach ist, zu überprüfen, ob sie angehalten werden oder nicht, indem man nach offensichtlichen Endlosschleifen sucht. Wenn Sie dagegen sicherstellen möchten, dass Ihr Programm immer beendet wird, können Sie dies tun, indem Sie die Anzahl der Schleifeniterationen für jede Schleife a priori begrenzen. Betrachten Sie beispielsweise den Pseudocode für das wiederholte Quadrieren:

def power(x, y, p):
   "compute x^y mod p"
   assert y >= 0
   result = 1
   while y > 0:
     if x is odd: result = result * x (mod p)
     y = y div 2
     x = x * x
   return result

Woher wissen wir, dass dieser Vorgang immer endet? Ein Weg wäre, die Schleife a priori zu binden:

def power(x, y, p):
   "compute x^y mod p"
   assert y >= 0
   bound = y
   result = 1
   loop bound times:
     if x is odd: result = result * x (mod p)
     y = y div 2
     x = x * x
     if y == 0: break
   return result

Jetzt ist klar, dass dieses Programm beendet wird, und wenn wir anderswo keinen Fehler gemacht haben, würden die beiden Programme dieselbe Ausgabe erzeugen.

Primitive rekursive Funktionen sind solche, die von Programmen berechnet werden, in denen alle Schleifen begrenzt sind und keine Rekursion erfolgt.

Wir erlauben zwar keine Rekursion (da sie nicht begrenzt ist), können sie jedoch mit einer Schleife simulieren. Wir können jetzt mehrere Fragen stellen:

1. Ist jede berechenbare Funktion in dieser Form präsentierbar?
2. Wenn nicht, wie ist die Beziehung zwischen dieser Klasse und allen berechenbaren Funktionen?

Um 1 zu beantworten, kann man zeigen, dass bestimmte berechenbare Funktionen, die "zu schnell" wachsen, nicht primitiv rekursiv sind, beispielsweise die Ackermann-Funktion. Umgekehrt ist jede Funktion, deren Wachstumsrate "vernünftig" ist, primitiv rekursiv. Und jede berechenbare Funktion kann im Formular angegeben werden$f(x) = \psi(\min_y \phi(x,y))$für primitive rekursive , wo wir als Prädikat betrachten.$\phi,\psi$$\phi$

Als ich meinen Berechenbarkeitskurs belegte, wurde uns dies folgendermaßen vorgestellt:

Primitive Rekursion ist eine natürliche Methode zum Definieren einer Berechnung (wahrscheinlich offensichtlich, wenn Sie einen mathematischen Verstand haben, ist es für einen Programmierer einfacher zu verstehen, dass Rekursion eine Rückwärtsschleife ist).

Wenn Sie also die primitive Rekursion beherrschen, fragen Sie sich: Ist das alles, was in der Berechnung steckt?

Nun, es stellt sich heraus, dass es nicht so ist. Erstens fehlen undefinierte Werte. Ok, Sie können also die primitive Rekursion auf partielle primitive rekursive Funktionen erweitern.

Dennoch gibt es einige (vollständige) berechenbare Funktionen, die nicht primitiv rekursiv sind. Nun, Ackermann ist einer davon. Deshalb ist die Ackermann-Funktion wichtig. Es stellt sich heraus, dass "Rekursion" "primitive Rekursion + Minimierung" ist, und obwohl dies nicht bewiesen werden kann, scheint es, dass dies alles ist, was zur Berechnung erforderlich ist.

Primitive rekursive Funktionen sind also so wichtig wie sie sind

1. einfacher Formalismus
2. Basis für die Definition der Rekursion

Ich bin mir nicht sicher - vielleicht wird es jemand anderes wissen -, aber ich denke, bevor Ackermann seine Funktion entwickelte, dachten Mathematiker, dass berechenbare = primitive Rekursion + Teilfunktionen.