Die primitiven rekursiven Funktionen werden mit primitivem recursion und Zusammensetzung als Hauptoperationen definiert und sind eine strenge Teilmenge der Gesamt-µ-Recursive-Funktionen (µ-recursive Funktionen werden auch teilweise rekursiv genannt). Der Begriff wurde von Rózsa Péter ins Leben gerufen.

In der Berechenbarkeitstheorie sind primitive rekursive Funktionen eine Klasse von Funktionen, die einen wichtigen Baustein unterwegs zu einer vollen Formalisierung der Berechenbarkeit bilden. Diese Funktionen sind auch in der Probetheorie wichtig.

Die meisten in der Zahlentheorie normalerweise studierten Funktionen sind rekursiv primitiv. Zum Beispiel: Hinzufügung, Abteilung, factorial, Exponential- und die n-te Blüte sind der ganze rekursive Primitive. So sind viele Annäherungen an reellwertige Funktionen. Tatsächlich ist es schwierig, eine berechenbare Funktion auszudenken, die rekursiv nicht primitiv ist, obwohl einige bekannt sind (sieh die Abteilung auf Beschränkungen unten).

Der Satz von primitiven rekursiven Funktionen ist als PR in der Kompliziertheitstheorie bekannt.

Jede primitive rekursive Funktion ist eine allgemeine rekursive Funktion.

Definition

Die primitiven rekursiven Funktionen sind unter den mit der Zahl theoretischen Funktionen, die Funktionen von den natürlichen Zahlen (natürliche Zahlen) {0, 1, 2 sind...} zu den natürlichen Zahlen. Diese Funktionen nehmen n Argumente für eine natürliche Zahl n und werden n-stufig genannt.

Die grundlegenden primitiven rekursiven Funktionen werden durch diese Axiome gegeben:

1. Unveränderliche Funktion: Die 0-ary unveränderliche Funktion 0 ist rekursiv primitiv.
2. Nachfolger-Funktion: Der 1-ary Nachfolger fungiert S, der den Nachfolger seines Arguments zurückgibt (sieh Postulate von Peano), ist rekursiv primitiv. D. h. S (k) = k + 1.
3. Vorsprung-Funktion: Für jeden n1 und jeden bin ich mit 1in, die n-stufige Vorsprung-Funktion P, der sein i-th Argument zurückgibt, rekursiv primitiv.

Kompliziertere primitive rekursive Funktionen können durch die Verwendung der durch diese Axiome gegebenen Operationen erhalten werden:

1. Zusammensetzung: Gegebener f, eine k-ary primitive rekursive Funktion und k M ary primitive rekursive Funktionen g..., g, die Zusammensetzung von f mit g..., g, d. h. die M ary Funktion sind rekursiv primitiv.
2. Primitiver recursion: Gegebener f, eine k-ary primitive rekursive Funktion und g, (k+2)-ary primitive rekursive Funktion, (k+1)-ary Funktion h werden als der primitive recursion von f und g definiert, d. h. die Funktion h ist rekursiv wenn primitiv
3. : und

:

Die primitiven rekursiven Funktionen sind die grundlegenden Funktionen und diejenigen, die bei den grundlegenden Funktionen durch die Verwendung der Maschinenbediener eine begrenzte Zahl von Zeiten erhalten sind.

Rolle der Vorsprung-Funktionen

Die Vorsprung-Funktionen können verwendet werden, um die offenbare Starrheit in Bezug auf den arity der Funktionen oben zu vermeiden; durch das Verwenden von Zusammensetzungen mit verschiedenen Vorsprung-Funktionen ist es möglich, eine Teilmenge der Argumente einer Funktion zu einer anderen Funktion zu passieren. Zum Beispiel, wenn g und h 2-ary primitive rekursive Funktionen dann sind

:

ist rekursiv auch primitiv. Eine formelle Definition mit Vorsprung-Funktionen ist

:

Das Umwandeln von Prädikaten zu numerischen Funktionen

In einigen Einstellungen ist es natürlich, primitive rekursive Funktionen zu denken, die als Eingangstupel nehmen, die Zahlen mit Wahrheitswerten {t = wahr, f=false} mischen, oder die Wahrheitswerte als Produktionen erzeugen (sieh Kleene [1952 Seiten 226-227]). Das kann vollbracht werden, indem es die Wahrheitswerte mit Zahlen auf jede feste Weise identifiziert wird. Zum Beispiel ist es üblich, den Wahrheitswert t mit der Nummer 1 zu identifizieren, und die Wahrheit schätzen f mit der Nummer 0. Sobald diese Identifizierung, die charakteristische Funktion eines Satzes A gemacht worden ist, der wörtlich 1 oder 0 zurückkehrt, kann als ein Prädikat angesehen werden, das erzählt, ob eine Zahl im Satz A ist. Solch eine Identifizierung von Prädikaten mit numerischen Funktionen wird für den Rest dieses Artikels angenommen.

Computersprachdefinition

Ein Beispiel einer primitiven rekursiven Programmiersprache ist dasjenige, das grundlegende arithmetische Maschinenbediener enthält (z.B + und - oder tragen Sie BEI und machen Sie ABSTRICHE), conditionals und Vergleich (WENN DANN, IST WENIGER GLEICH - ALS), und begrenzte Schleifen, solcher als das grundlegende für die Schleife, wo es einen bekannten oder berechenbares ober gebunden zu allen Schleifen (WEIL ich VON 1 bis n) gibt. Keine Kontrollstrukturen der größeren Allgemeinheit, solcher als während Schleifen oder WENN DANN plus GOTO, werden auf einer primitiven rekursiven Sprache zugelassen. Der Bloop von Douglas Hofstadter in Gödel, Escher, ist Junggeselle ein solcher. Das Hinzufügen unbegrenzter Schleifen (WÄHREND, GOTO) macht die Sprache teilweise rekursiv, oder Turing-abgeschlossen; Floop ist solcher, wie fast alle wirklichen Computersprachen sind.

Willkürliche Computerprogramme oder Maschinen von Turing, können nicht im Allgemeinen analysiert werden, um zu sehen, ob sie hinken oder nicht (das stockende Problem). Jedoch, der ganze primitive rekursive Funktionshalt. Das ist nicht ein Widerspruch; primitive rekursive Programme sind eine nichtwillkürliche Teilmenge aller möglichen Programme, gebaut spezifisch, um zerlegbar zu sein.

Beispiele

Die meisten mit der Zahl theoretischen Funktionen das definierbare Verwenden recursion auf einer einzelnen Variable sind rekursiv primitiv. Grundlegende Beispiele schließen die Hinzufügung und "beschränkte Subtraktion" Funktionen ein.

Hinzufügung

Intuitiv kann Hinzufügung mit den Regeln rekursiv definiert werden:

:add (0, x) =x,

:add (n+1, x) =add (n, x) +1.

Um das eine strenge primitive rekursive Definition einzubauen, definieren Sie:

:add (0, x) =P (x),

:add (S (n), x) =S (P (n, tragen (n, x), x)) bei.

Hier ist P die Vorsprung-Funktion, die 3 Argumente nimmt und das zweite zurückgibt.

P ist einfach die Identitätsfunktion; seine Einschließung ist durch die Definition des primitiven recursion Maschinenbedieners oben erforderlich; es spielt die Rolle von f. Die Zusammensetzung von S und P, der rekursiv primitiv ist, spielt die Rolle von g. Der Begriff S (n) bezieht sich auf "den Nachfolger von n".

Subtraktion

Weil primitive rekursive Funktionen natürliche Zahlen aber nicht ganze Zahlen verwenden, und die natürlichen Zahlen unter der Subtraktion nicht geschlossen werden, wird eine beschränkte Subtraktionsfunktion in diesem Zusammenhang studiert. Dieses beschränkte SubtraktionsfunktionsU-Boot (a, b) kehrt zurück, wenn das nichtnegativ ist und 0 sonst zurückkehrt.

Die Vorgänger-Funktionstaten als das Gegenteil des Nachfolgers fungieren, und wird durch die Regeln rekursiv definiert:

:pred (0) =0,

:pred (n+1) =n.

Diese Regeln können in eine mehr formelle Definition durch primitiven recursion umgewandelt werden:

:pred (0) =0,

:pred (S (n)) =P (n, pred (n)).

Die beschränkte Subtraktionsfunktion ist von der Vorgänger-Funktion definierbar, die gewissermaßen der Weise analog ist, wie Hinzufügung vom Nachfolger definiert wird:

:sub (0, x) =P (x),

:sub (S (n), x) =pred (P (n, U-Boot (n, x), x)).

Hier entspricht U-Boot (a, b) b-a; wegen der Einfachheit ist die Ordnung der Argumente aus der "Standard"-Definition geschaltet worden, um die Voraussetzungen von primitivem recursion zu passen. Das konnte mit der Zusammensetzung mit passenden Vorsprüngen leicht berichtigt werden.

Andere primitive rekursive Funktionen schließen exponentiation und Primality-Prüfung ein. In Anbetracht primitiver rekursiver Funktionen e, f, g, und h, eine Funktion, die den Wert von g zurückgibt, wenn ef und der Wert von h sonst rekursiv primitiv sind.

Operationen auf ganzen Zahlen und rationalen Zahlen

Durch das Verwenden von Gödel numberings können die primitiven rekursiven Funktionen erweitert werden, um auf anderen Gegenständen wie ganze Zahlen und rationale Zahlen zu funktionieren. Wenn ganze Zahlen durch Zahlen von Gödel auf eine Standardweise, die arithmetischen Operationen einschließlich der Hinzufügung, Subtraktion verschlüsselt werden, und Multiplikation der ganze rekursive Primitive ist. Ähnlich, wenn die rationals durch Zahlen von Gödel dann vertreten werden, sind die Feldoperationen der ganze rekursive Primitive.

Beziehung zu rekursiven Funktionen

Die breitere Klasse von teilweisen rekursiven Funktionen wird durch das Einführen eines unbegrenzten Suchmaschinenbedieners definiert. Der Gebrauch dieses Maschinenbedieners kann auf eine teilweise Funktion, d. h. eine Beziehung mit höchstens einem Wert für jedes Argument hinauslaufen, aber hat keinen Wert für jedes Argument notwendigerweise (sieh Gebiet). Eine gleichwertige Definition stellt fest, dass eine teilweise rekursive Funktion diejenige ist, die durch eine Maschine von Turing geschätzt werden kann. Eine rekursive Gesamtfunktion ist eine teilweise rekursive Funktion, die für jeden Eingang definiert wird.

Jede primitive rekursive Funktion ist rekursiv ganz, aber nicht alle rekursiven Gesamtfunktionen sind rekursiv primitiv. Die Funktion von Ackermann (M, n) ist ein wohl bekanntes Beispiel einer rekursiven Gesamtfunktion, die rekursiv nicht primitiv ist. Es gibt eine Charakterisierung der primitiven rekursiven Funktionen als eine Teilmenge der rekursiven Gesamtfunktionen mit der Funktion von Ackermann. Diese Charakterisierung stellt fest, dass eine Funktion rekursiv wenn und nur primitiv ist, wenn es eine natürliche Zahl solche M gibt, dass die Funktion durch eine Maschine von Turing geschätzt werden kann, die immer innerhalb (M, n) oder weniger Schritte hinkt, wo n die Summe der Argumente der primitiven rekursiven Funktion ist.

Ein wichtiges Eigentum der primitiven rekursiven Funktionen besteht darin, dass sie rekursiv enumerable Teilmenge des Satzes aller rekursiven Gesamtfunktionen sind (der nicht selbst rekursiv enumerable ist). Das bedeutet, dass es eine einzelne berechenbare Funktion f (e, n) solch dass gibt:

• Für jede primitive rekursive Funktion g gibt es einen solchen e dass g (n) = f (e, n) für den ganzen n und
• Für jeden e ist die Funktion h (n) = f (e, n) rekursiv primitiv.

Jedoch sind die primitiven rekursiven Funktionen rekursiv enumerable Satz von berechenbaren Gesamtfunktionen nicht am größten.

Beschränkungen

Primitive rekursive Funktionen neigen dazu, sehr nah unserer Intuition dessen zu entsprechen, wie eine berechenbare Funktion sein muss. Sicher sind die anfänglichen Funktionen intuitiv berechenbar (in ihrer wirklichen Einfachheit), und die zwei Operationen, durch die neue primitive rekursive Funktionen schaffen kann, sind auch sehr aufrichtig. Jedoch schließt der Satz von primitiven rekursiven Funktionen jede mögliche berechenbare Gesamtfunktion  — this nicht ein kann mit einer Variante des diagonalen Arguments des Kantoren gesehen werden. Dieses Argument stellt eine berechenbare Gesamtfunktion zur Verfügung, die rekursiv nicht primitiv ist. Eine Skizze des Beweises ist wie folgt:

:The können primitive rekursive Funktionen eines Arguments (d. h., unäre Funktionen) berechenbar aufgezählt werden. Diese Enumeration verwendet die Definitionen der primitiven rekursiven Funktionen (die im Wesentlichen gerade Ausdrücke mit der Zusammensetzung und den primitiven recursion Operationen als Maschinenbediener und die grundlegenden primitiven rekursiven Funktionen als Atome sind), und angenommen werden kann, jede Definition einmal zu enthalten, wenn auch dieselbe Funktion oft auf der Liste vorkommen wird (da viele Definitionen dieselbe Funktion definieren; tatsächlich einfach erzeugt das Bestehen nach der Identitätsfunktion ungeheuer viele Definitionen irgendwelcher primitiver rekursiver Funktion). Das bedeutet, dass die-th Definition einer primitiven rekursiven Funktion in dieser Enumeration davon effektiv bestimmt werden kann. Tatsächlich, wenn man einen Gödel verwendet, der numeriert, um Definitionen als Zahlen zu verschlüsseln, dann wird diese-th Definition in der Liste durch eine primitive rekursive Funktion dessen geschätzt. Lassen Sie zeigen die unäre primitive rekursive durch diese Definition gegebene Funktion an.

:Now definieren die "Schätzer-Funktion" mit zwei Argumenten, dadurch. Klar ist ganz und berechenbar, da man die Definition effektiv bestimmen kann, und eine primitive rekursive Funktion zu sein, selbst ganz und berechenbar ist, immer so definiert und effektiv berechenbar wird. Jedoch wird ein diagonales Argument zeigen, dass die Funktion von zwei Argumenten rekursiv nicht primitiv ist.

:Suppose waren rekursiv primitiv, dann würde die unäre Funktion, die dadurch definiert ist, auch rekursiv sein primitiv, weil sie durch die Zusammensetzung von der Nachfolger-Funktion definiert wird und. Aber kommt dann in der Enumeration vor, also gibt es, numerieren ein solch dass. Aber gibt jetzt einen Widerspruch.

Dieses Argument kann auf jede Klasse von berechenbaren (ganzen) Funktionen angewandt werden, die auf diese Weise, wie erklärt, im Artikel Machines aufgezählt werden können, den das immer hält. Bemerken Sie jedoch, dass die teilweisen berechenbaren Funktionen (diejenigen, die für alle Argumente nicht definiert zu werden brauchen), zum Beispiel durch das Aufzählen der Maschine von Turing encodings ausführlich aufgezählt werden können.

Andere Beispiele von ganzen rekursiv, aber nicht primitive rekursive Funktionen sind bekannt:

• Die Funktion, die M Ackermann bringt (M, m) ist eine unäre rekursive Gesamtfunktion, die rekursiv nicht primitiv ist.
• Der Lehrsatz des Paris-Harrington schließt eine rekursive Gesamtfunktion ein, die rekursiv nicht primitiv ist. Weil diese Funktion durch die Theorie von Ramsey motiviert wird, wird es manchmal "natürlicher" betrachtet als die Funktion von Ackermann.
• Die Funktion von Sudan

Einige allgemeine primitive rekursive Funktionen

:The im Anschluss an Beispiele und Definitionen sind von Kleene (1952) Seiten 223-231 — viele erscheinen mit Beweisen. Erscheinen Sie am meisten auch mit ähnlichen Namen, entweder als Beweise oder als Beispiele, in Boolos-Burgess-Jeffrey 2002 Seiten 63-70; sie tragen #22 der Logarithmus lo (x, y) oder lg (x, y) abhängig von der genauen Abstammung bei.

Im folgenden bemerken wir, dass primitive rekursive Funktionen von vier Typen sein können:

1. Funktionen für den kurzen: "mit der Zahl theoretische Funktionen" von {0, 1, 2...} zu {0, 1, 2...},
2. Prädikate: von {0, 1, 2...} zu Wahrheitswerten {t =true, f =false},
3. Satzbindewörter: von Wahrheitswerten {t, f} zu Wahrheitswerten {t, f},
4. das Darstellen von Funktionen: von Wahrheitswerten {t, f} zu {0, 1, 2...}. Oft verlangt ein Prädikat eine Darstellen-Funktion, die Produktion des Prädikats {t, f} zu {0 umzuwandeln, 1} (bemerken Sie den Auftrag "t" zu "0" und "f" zu "1" Matchs mit ~ (sig ) definiert unten). Definitionsgemäß ist eine Funktion φ (x) eine "Darstellen-Funktion" des Prädikats P (x), wenn φ nur Werte 0 und 1 nimmt und 0 erzeugt, wenn P wahr ist".

Im folgenden ist das Zeichen "'", z.B', das primitive Zeichen, das "den Nachfolger dessen bedeutet," hat gewöhnlich als "+1", z.B ein +1 = gedacht'. Die Funktionen 16-21 und #G sind von besonderem Interesse in Bezug auf das Umwandeln primitiver rekursiver Prädikate zu, und das Extrahieren von ihnen von, ihre "arithmetische" als Zahlen von Gödel ausgedrückte Form.

:# Hinzufügung: a+b

:# Multiplikation: a×b

:# Exponentiation: ein

:# Factorial a!: 0! = 1,'! = a! ×a'

:# pred (a): Verminderung: "Vorgänger" definiert als "Wenn a> 0 dann a-1  ein sonst 0  a."

:# Richtige Subtraktion: ein  b definiert als "Wenn ein  b dann a-b sonst 0."

:# Minimum (a...)

:# Maximum (a...)

:# Absoluter Wert: | a-b | = ein  b + b  ein

:# ~sg (a): NICHT [Signum (a)]: Wenn a=0 dann sg (a) =1 sonst wenn a> 0 dann sg (a) =0

:# sg (a): Signum (a): Wenn a=0 dann sg (a) =0 sonst wenn a> 0 dann sg (a) =1

:# "b teilt sich" [| b]: Wenn sich der Rest (a, b) =0 dann [| b] sonst b "gleichmäßig" nicht teilt

:# Rest (a, b): Der Rest, wenn sich b "gleichmäßig" nicht teilt. Auch genannt MOD (a, b)

:# = b: sg | - b |

:# ein a> 1 & NICHT (Besteht c)

:# P: die i+1-st Primzahl

:# (a): Hochzahl p = μx [

:# lh (a): die "Länge" oder Zahl von nichtverschwindenden Hochzahlen in einem

:# a×b: In Anbetracht des Ausdrucks von a und b als Hauptfaktoren dann ist a×b der Ausdruck des Produktes als Hauptfaktoren

:# lo (x, y): Logarithmus von x zur Basis y

: Im folgenden, die Abkürzung 'x = x... x; Subschriften können angewandt werden, wenn die Bedeutung verlangt.

• #A: Eine Funktion φ definierbar ausführlich von Funktionen Ψ und Konstanten q... q ist rekursiv in Ψ primitiv.
• #B: Die begrenzte Summe Σ
• #C: Ein Prädikat P erhalten durch das Ersetzen von Funktionen χ..., χ für die jeweiligen Variablen eines Prädikats Q ist rekursiv in χ..., χ, Q primitiv.
• #D: Die folgenden Prädikate sind rekursiv in Q und R primitiv:

::* NOT_Q (x).

::* Q ODER R: Q (x) V R (x),

::* Q UND R: Q (x) & R (x),

::* Q BEZIEHT R EIN: Q (x)  R (x)

::* Q ist zu R gleichwertig: Q (x)  R (x)

• #E: Die folgenden Prädikate sind rekursiv im Prädikat R primitiv:

::* (Ey)

::* (y)

::* μy

• #F: Definition durch Fälle: Die Funktion hat so definiert, wo Q..., Q gegenseitig exklusive Prädikate sind (oder "ψ (x) den Wert durch die erste Klausel geben lassen wird, die gilt), ist rekursiv in φ..., Q primitiv... Q:

:: φ (x) =

::* φ (x), wenn Q (x), wahr

ist

::*...................

::* φ (x), wenn Q (x) wahrer ist

::* φ (x) sonst

• #G: Wenn φ die Gleichung befriedigt:

:: φ (y, x) = χ (y, NOT-φ (y; x... x), x... x dann ist φ rekursiv in χ primitiv. 'Also, Gewissermaßen die Kenntnisse des Werts NOT-φ (y; x) des Kurses Werte ist die Funktion zu den Kenntnissen der Folge von Werten φ (0, x)..., φ (y-1, x) der ursprünglichen Funktion gleichwertig."

Zusätzliche primitive rekursive Formen

Einige zusätzliche Formen von recursion definieren auch Funktionen, die tatsächlich sind

primitiv rekursiv. Definitionen in diesen Formen können leichter sein zu finden oder

natürlicher, um zu lesen oder zu schreiben.

Kurs der Werte recursion definiert primitive rekursive Funktionen.

Einige Formen von gegenseitigem recursion

definieren Sie auch primitive rekursive Funktionen.

Finitism und Konsistenz-Ergebnisse

Die primitiven rekursiven Funktionen sind nah mit mathematischem finitism verbunden, und werden in mehreren Zusammenhängen in der mathematischen Logik verwendet, wo ein besonders konstruktives System gewünscht wird. Primitive rekursive Arithmetik (PRA), ein formelles Axiom-System für die natürlichen Zahlen und die primitiven rekursiven Funktionen auf ihnen, wird häufig für diesen Zweck verwendet.

PRA ist viel schwächer als Arithmetik von Peano, die nicht ein finitistic System ist. Dennoch laufen viele auf Zahlentheorie hinaus, und im Beweis kann Theorie in PRA bewiesen werden. Zum Beispiel kann der Unvollständigkeitslehrsatz von Gödel in PRA formalisiert werden, den folgenden Lehrsatz gebend:

:If T ist eine Theorie der Arithmetik, die bestimmte Hypothesen mit Satz-G von Gödel befriedigt, dann beweist PRA die Implikation Con (T)

→G.

Ähnlich können viele der syntaktischen Ergebnisse in der Probetheorie in PRA bewiesen werden, der andeutet, dass es primitive rekursive Funktionen gibt, die die entsprechenden syntaktischen Transformationen von Beweisen ausführen.

In der Probetheorie und Mengenlehre gibt es ein Interesse an finitistic Konsistenz-Beweisen, d. h. Konsistenz-Beweise, die selbst annehmbar finitistically sind. Solch ein Beweis stellt fest, dass die Konsistenz einer Theorie T die Konsistenz einer Theorie S durch das Produzieren einer primitiven rekursiven Funktion einbezieht, die jeden Beweis einer Widersprüchlichkeit von S in einen Beweis einer Widersprüchlichkeit von T umgestalten kann. Eine genügend Bedingung für einen Konsistenz-Beweis, um finitistic zu sein, ist die Fähigkeit, es in PRA zu formalisieren. Zum Beispiel können viele Konsistenz läuft auf Mengenlehre hinaus, die durch das Zwingen erhalten werden, als syntaktische Beweise umgearbeitet werden, die in PRA formalisiert werden können.

Siehe auch

• Kurs der Werte recursion
• Hierarchie von Grzegorczyk
• Maschine, die immer hält
• Recursion (Informatik)
• Primitiver rekursiver funktioneller
• Verdoppeln Sie recursion
• Brainerd, W.S. Landweber, L.H. (1974), Theorie der Berechnung, Wileys, internationalen Standardbuchnummer 0-471-09585-0
• Robert I. Soare, Rekursiv Enumerable Sätze und Grade, Springer-Verlag, 1987. Internationale Standardbuchnummer 0-387-15299-7
• Stephen Kleene (1952) Einführung in Metamathematics, North-Holland Publishing Company, New York, 11. Nachdruck 1971: (2. Ausgabe-Zeichen haben 6. Nachdruck hinzugefügt). Im Kapitel XI. Allgemeine Rekursive Funktionen §57
• George Boolos, John Burgess, Richard Jeffrey (2002), Berechenbarkeit und Logik: Die Vierte Ausgabe, Universität von Cambridge Presse, Cambridge, das Vereinigte Königreich. Vgl Seiten 70-71.
• 1995-Berechenbarkeit von Robert I. Soare und Recursion

http://www.people.cs.uchicago.edu/~soare/History/compute.pdf

• Daniel Severin 2008, Unäre primitive rekursive Funktionen, J. Symbolischer Logikband 73, Ausgabe 4, Seiten 1122-1138 arXiv projecteuclid