Rekursive Funktionen und Registermaschinen

Die Theorie der rekursiven Funktionen konstruiert die berechenbaren Funktionen aus einer Handvoll grundlegender Operationen, während Registermaschinen mit ganzen Zahlen rechnen, die in Registern gespeichert sind. Beide Modelle umrahmen die Turingmaschine und bestätigen die Robustheit der Berechenbarkeit.

Definition

Die allgemeinen rekursiven Funktionen sind jene, die aus Konstanten, Nachfolger und Projektionen durch Komposition, primitive Rekursion und unbeschränkte Minimierung gebildet werden; Registermaschinen sind abstrakte Geräte, die durch Inkrementieren, Dekrementieren und Testen des Inhalts einer endlichen Menge von Registern, die natürliche Zahlen enthalten, berechnen.

Scope

Dieses Thema behandelt die primitiv rekursiven Funktionen, die Erweiterung um unbeschränkte Minimierung zur Erlangung der allgemeinen rekursiven Funktionen, die Ackermann-Funktion als berechenbare Funktion, die nicht primitiv rekursiv ist, Register- und Zählermaschinen und ihre Universalität sowie die Äquivalenz all dieser Modelle mit der Turing-Berechenbarkeit.

Core questions

• Wie können die berechenbaren Funktionen arithmetisch ohne eine Maschine definiert werden?
• Warum ist unbeschränkte Minimierung über die primitive Rekursion hinaus erforderlich?
• Wie erreichen einfache Registermaschinen die volle Rechenleistung?
• Warum stimmen diese arithmetischen und Maschinenmodelle mit Turingmaschinen überein?

Key theories

Äquivalenz mit der Turing-Berechenbarkeit

Die allgemeinen rekursiven Funktionen und die von Registermaschinen berechneten Funktionen sind genau die Turing-berechenbaren Funktionen, was die Church-Turing-These durch Modelle, die in rein arithmetischen und elementaren Maschinenbegriffen definiert sind, untermauert.

Jenseits der primitiven Rekursion

Die Ackermann-Funktion ist total und berechenbar, wächst aber zu schnell, um primitiv rekursiv zu sein, was zeigt, dass unbeschränkte Suche wesentlich ist und dass die primitiv rekursiven Funktionen eine echte Unterklasse der berechenbaren Funktionen sind.

Universalität von Registermaschinen

Minsky zeigte, dass eine Maschine mit nur zwei Zählern und den Operationen Inkrement, Dekrement und Nulltest bereits Turing-vollständig ist, eine extreme Demonstration, wie wenig Struktur für die vollständige Berechnung erforderlich ist.

Clinical relevance

Registermaschinen modellieren die Ganzzahlarithmetik realer Prozessoren direkter als Bänder; primitive Rekursion entspricht Programmen, die immer terminieren, und liegt total funktionalen Sprachen und der Terminierungsanalyse zugrunde; und die rekursive Funktionssicht verbindet die Berechnung mit den Grundlagen der Mathematik.

History

Gödel und Herbrand definierten die allgemeinen rekursiven Funktionen in den frühen 1930er Jahren, und Kleene entwickelte die Theorie, einschließlich der Rolle der Minimierung. Ackermann hatte zuvor seine schnell wachsende Funktion vorgestellt, und Minsky führte in den 1960er Jahren Register- und Zählermaschinen ein, wobei er sogar die Universalität von Zwei-Zählermaschinen bewies.

Key figures

• Kurt Gödel
• Stephen Kleene
• Wilhelm Ackermann
• Marvin Minsky

Seminal works

• cutland1980
• minsky1967

Frequently asked questions

Was ist der Unterschied zwischen primitiv rekursiven und allgemeinen rekursiven Funktionen?

Primitiv rekursive Funktionen werden unter Verwendung begrenzter Schleifen konstruiert und terminieren immer, erfassen aber nicht jede berechenbare Funktion. Das Hinzufügen unbeschränkter Minimierung, einer Suche, die unbegrenzt laufen kann, führt zu den allgemeinen rekursiven Funktionen, die genau mit den Turing-berechenbaren Funktionen übereinstimmen.

Wie kann eine Maschine mit nur zwei Zählern so leistungsfähig sein wie ein Computer?

Minsky zeigte, dass zwei Register, die natürliche Zahlen enthalten, mit nur Inkrement, Dekrement und Test auf Null eine Turingmaschine simulieren können, indem sie ihr Band in den Registern kodieren. Die Konstruktion ist sehr ineffizient, aber sie beweist, dass minimale Hardware bereits die volle Rechenleistung erreicht.