www.wikidata.de-de.nina.az

Primitiv rekursive Funktion en sind totale Funktionen die aus einfachen Grundfunktionen konstante 0 Funktion Projektione

Primitiv-rekursive Funktion

Primitiv-rekursive Funktionen sind totale Funktionen, die aus einfachen Grundfunktionen (konstante 0-Funktion, Projektionen auf ein Argument und Nachfolgefunktion) durch Komposition und (primitive) Rekursion gebildet werden können. Die primitive Rekursion lässt sich auf Richard Dedekinds 126. Theorem in Was sind und was sollen die Zahlen? (1888) zurückführen. Die primitiv rekursive Arithmetik geht auf Thoralf Skolem (1923) zurück. Der Begriff primitiv-rekursive Funktion wurde von der ungarischen Mathematikerin Rózsa Péter geprägt. Primitiv-rekursive Funktionen spielen in der Rekursionstheorie, einem Teilgebiet der theoretischen Informatik, eine Rolle. Sie treten im Zusammenhang mit der Explikation des Berechenbarkeitsbegriffs auf.

Alle primitiv-rekursiven Funktionen sind im intuitiven Sinn berechenbar. Sie schöpfen aber nicht alle intuitiv berechenbaren Funktionen aus, Beispiele dafür sind die Ackermannfunktion und die Sudanfunktion, welche beide berechenbar, aber nicht primitiv-rekursiv sind. Eine vollständige Erfassung des Berechenbarkeitsbegriffs gelingt erst durch die µ-rekursiven Funktionen.

Für primitiv-rekursive Funktionen ist es möglich, ein Komplexitätsmaß zu definieren, d. h., es kann die Dauer der Berechnung eines ihrer Funktionswerte vorab ermittelt werden.

Die Klasse der primitiv-rekursiven Funktionen und die der LOOP-berechenbaren (vgl. LOOP-Programm) Funktionen sind äquivalent.

Definition Bearbeiten

  1. Für ein beliebiges ist die k-stellige 0-Funktion definiert durch .
  2. Für ein beliebiges und ein beliebiges ist die k-stellige Projektion auf den i-ten Parameter definiert durch .
  3. Die Nachfolgerfunktion ist definiert durch .
  4. Für beliebige ist die Komposition einer Funktion mit m Funktionen definiert als die Funktion mit .
  5. Für ein beliebiges ist die primitive Rekursion zweier Funktionen und definiert als die Funktion mit

Die Menge der primitiv-rekursiven Funktionen ist dann definiert als die kleinste Menge, die alle Nullfunktionen, alle Projektionen und die Nachfolgerfunktion enthält und die unter Komposition und primitiver Rekursion abgeschlossen ist. Alltäglicher ausgedrückt heißt das: Eine Funktion ist genau dann primitiv-rekursiv, wenn man sie als Ausdruck mit den genannten Mitteln hinschreiben kann. Bereits als primitiv-rekursiv nachgewiesene Funktionen dürfen in dem Ausdruck vorkommen, denn sie können ja durch Einsetzen ihres Ausdrucks eliminiert werden.

Jede k-stellige primitiv-rekursive Funktion ist insbesondere immer auf ganz definiert. Funktionen mit kleinerem Definitionsbereich müssen erst geeignet auf ganz fortgesetzt werden, damit man primitiv-rekursive Funktionen erhält.

Beispiele Bearbeiten

Addition Bearbeiten

Die Addition ist rekursiv definiert durch

für alle . Es gilt also , die Addition ist damit primitiv-rekursiv.

Multiplikation Bearbeiten

Die Multiplikation ist rekursiv über die Addition definiert:

für alle . Die Multiplikation ist primitiv-rekursiv, denn es gilt .

Potenz Bearbeiten

Die Potenz mit der Bedeutung ist rekursiv über die Multiplikation definiert:

für alle . Die Potenz ist primitiv-rekursiv, denn es gilt . Der Kontext hat hierbei den Zweck, die beiden Parameter und miteinander zu vertauschen.

Vorgängerfunktion Bearbeiten

Die Vorgängerfunktion ist nicht an der Stelle 0 definiert. Sie ist also nicht primitiv-rekursiv. Durch Fortsetzung an der Stelle 0 zum Beispiel mit dem Wert 0 kann man jedoch eine primitiv-rekursive Funktion daraus machen.

Die modifizierte Vorgängerfunktion , definiert durch

für alle ist primitiv-rekursiv, denn es gilt .

Subtraktion Bearbeiten

Auch die Subtraktion ist nicht auf allen Paaren natürlicher Zahlen definiert. Man setzt also die Subtraktion durch Auffüllen mit Nullen fort auf ganz . Diese totale Subtraktion kann rekursiv charakterisiert werden durch

für alle . Für die totale Subtraktion gilt ; sie ist also primitiv-rekursiv. Man nennt diese modifizierte Differenz auch arithmetische Differenz.

Weitere Beispiele Bearbeiten

  • Die zweistelligen Funktionen und sind primitiv rekursiv.
  • Die Folge der Primzahlen ist eine primitiv rekursive Funktion.
  • Die Funktion, die zu einer natürlichen Zahl und einer Primzahl die Anzahl der Primfaktoren von in ermittelt, ist primitiv rekursiv.
  • Es existieren primitiv rekursive Arithmetisierungen endlicher Folgen natürlicher Zahlen.
  • Die Ackermannfunktion und die Sudanfunktion sind nicht primitiv rekursiv, aber µ-rekursiv.
  • Die Funktion Fleißiger Biber (busy beaver) ist nicht primitiv rekursiv und nicht µ-rekursiv.

Siehe auch Bearbeiten

Literatur Bearbeiten

  • Hans Hermes: Aufzählbarkeit, Entscheidbarkeit, Berechenbarkeit. 2. Auflage. Springer Berlin, Heidelberg, New York, 1971, ISBN 3-540-05334-4.
  • Heinz-Dieter Ebbinghaus, Jörg Flum, Wolfgang Thomas: Einführung in die mathematische Logik. 4. Auflage. Spektrum, Akademischer Verlag, Heidelberg u. a. 1996, ISBN 3-8274-0130-5 (Hochschultaschenbuch).
  • Arnold Oberschelp: Rekursionstheorie. BI-Wissenschaftlicher-Verlag, Mannheim u. a. 1993, ISBN 3-411-16171-X.
  • Wolfgang Rautenberg: Einführung in die Mathematische Logik. 3. Auflage. Vieweg+Teubner, Wiesbaden, ISBN 978-3-8348-0578-2.

Einzelnachweise Bearbeiten

  1. Peter Schroeder-Heister, Mathematische Logik II (Gödelsche Unvollständigkeitssätze), Skript, S. 39
wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
Primitiv rekursive Funktionen sind totale Funktionen die aus einfachen Grundfunktionen konstante 0 Funktion Projektionen auf ein Argument und Nachfolgefunktion durch Komposition und primitive Rekursion gebildet werden konnen Die primitive Rekursion lasst sich auf Richard Dedekinds 126 Theorem in Was sind und was sollen die Zahlen 1888 zuruckfuhren Die primitiv rekursive Arithmetik geht auf Thoralf Skolem 1923 zuruck 1 Der Begriff primitiv rekursive Funktion wurde von der ungarischen Mathematikerin Rozsa Peter gepragt Primitiv rekursive Funktionen spielen in der Rekursionstheorie einem Teilgebiet der theoretischen Informatik eine Rolle Sie treten im Zusammenhang mit der Explikation des Berechenbarkeitsbegriffs auf Alle primitiv rekursiven Funktionen sind im intuitiven Sinn berechenbar Sie schopfen aber nicht alle intuitiv berechenbaren Funktionen aus Beispiele dafur sind die Ackermannfunktion und die Sudanfunktion welche beide berechenbar aber nicht primitiv rekursiv sind Eine vollstandige Erfassung des Berechenbarkeitsbegriffs gelingt erst durch die µ rekursiven Funktionen Fur primitiv rekursive Funktionen ist es moglich ein Komplexitatsmass zu definieren d h es kann die Dauer der Berechnung eines ihrer Funktionswerte vorab ermittelt werden Die Klasse der primitiv rekursiven Funktionen und die der LOOP berechenbaren vgl LOOP Programm Funktionen sind aquivalent Inhaltsverzeichnis 1 Definition 2 Beispiele 2 1 Addition 2 2 Multiplikation 2 3 Potenz 2 4 Vorgangerfunktion 2 5 Subtraktion 2 6 Weitere Beispiele 3 Siehe auch 4 Literatur 5 EinzelnachweiseDefinition BearbeitenFur ein beliebiges k N displaystyle k in mathbb N nbsp ist die k stellige 0 Funktion 0 k N k N displaystyle 0 k colon mathbb N k to mathbb N nbsp definiert durch 0 k n 1 n k 0 displaystyle 0 k left n 1 dots n k right 0 nbsp Fur ein beliebiges k N displaystyle k in mathbb N nbsp und ein beliebiges 1 i k displaystyle 1 leq i leq k nbsp ist die k stellige Projektion auf den i ten Parameter p i k N k N displaystyle pi i k colon mathbb N k to mathbb N nbsp definiert durch p i k n 1 n k n i displaystyle pi i k left n 1 dots n k right n i nbsp Die Nachfolgerfunktion n N N displaystyle nu colon mathbb N to mathbb N nbsp ist definiert durch n n n 1 displaystyle nu left n right n 1 nbsp Fur beliebige k m N displaystyle k m in mathbb N nbsp ist die Komposition einer Funktion g N m N displaystyle g colon mathbb N m to mathbb N nbsp mit m Funktionen h 1 h m N k N displaystyle h 1 dots h m colon mathbb N k to mathbb N nbsp definiert als die Funktion C g h 1 h m N k N displaystyle C g h 1 dots h m colon mathbb N k to mathbb N nbsp mit C g h 1 h m n 1 n k g h 1 n 1 n k h m n 1 n k displaystyle C g h 1 dots h m left n 1 dots n k right g left h 1 left n 1 dots n k right dots h m left n 1 dots n k right right nbsp Fur ein beliebiges k N 0 displaystyle k in mathbb N setminus 0 nbsp ist die primitive Rekursion zweier Funktionen g N k 1 N displaystyle g colon mathbb N k 1 to mathbb N nbsp und h N k 1 N displaystyle h colon mathbb N k 1 to mathbb N nbsp definiert als die Funktion R g h N k N displaystyle R g h colon mathbb N k to mathbb N nbsp mitR g h n 1 n 2 n k g n 2 n k falls n 1 0 h R g h n 1 1 n 2 n k n 1 1 n 2 n k sonst displaystyle R g h left n 1 n 2 dots n k right begin cases g left n 2 dots n k right amp mbox falls n 1 0 h left R g h left n 1 1 n 2 dots n k right n 1 1 n 2 dots n k right amp mbox sonst end cases nbsp Die Menge P r displaystyle Pr nbsp der primitiv rekursiven Funktionen ist dann definiert als die kleinste Menge die alle Nullfunktionen alle Projektionen und die Nachfolgerfunktion enthalt und die unter Komposition und primitiver Rekursion abgeschlossen ist Alltaglicher ausgedruckt heisst das Eine Funktion ist genau dann primitiv rekursiv wenn man sie als Ausdruck mit den genannten Mitteln hinschreiben kann Bereits als primitiv rekursiv nachgewiesene Funktionen durfen in dem Ausdruck vorkommen denn sie konnen ja durch Einsetzen ihres Ausdrucks eliminiert werden Jede k stellige primitiv rekursive Funktion ist insbesondere immer auf ganz N k displaystyle mathbb N k nbsp definiert Funktionen mit kleinerem Definitionsbereich mussen erst geeignet auf ganz N k displaystyle mathbb N k nbsp fortgesetzt werden damit man primitiv rekursive Funktionen erhalt Beispiele BearbeitenAddition Bearbeiten Die Addition N 2 N displaystyle colon mathbb N 2 to mathbb N nbsp ist rekursiv definiert durch m n n falls m 0 n m 1 n sonst displaystyle m n begin cases n amp mbox falls m 0 nu m 1 n amp mbox sonst end cases nbsp fur alle m n N displaystyle m n in mathbb N nbsp Es gilt also R p 1 1 C n p 1 3 displaystyle R pi 1 1 C nu pi 1 3 nbsp die Addition ist damit primitiv rekursiv Multiplikation Bearbeiten Die Multiplikation N 2 N displaystyle cdot colon mathbb N 2 to mathbb N nbsp ist rekursiv uber die Addition definiert m n 0 falls m 0 m 1 n n sonst displaystyle m cdot n begin cases 0 amp mbox falls m 0 m 1 cdot n n amp mbox sonst end cases nbsp fur alle m n N displaystyle m n in mathbb N nbsp Die Multiplikation ist primitiv rekursiv denn es gilt R 0 1 C p 1 3 p 3 3 displaystyle cdot R 0 1 C pi 1 3 pi 3 3 nbsp Potenz Bearbeiten Die Potenz pot N 2 N displaystyle operatorname pot colon mathbb N 2 to mathbb N nbsp mit der Bedeutung pot m n m n displaystyle operatorname pot m n m n nbsp ist rekursiv uber die Multiplikation definiert pot m n 1 falls n 0 pot m n 1 m sonst displaystyle operatorname pot m n begin cases 1 amp mbox falls n 0 operatorname pot m n 1 cdot m amp mbox sonst end cases nbsp fur alle m n N displaystyle m n in mathbb N nbsp Die Potenz ist primitiv rekursiv denn es gilt pot C R C n 0 1 C p 1 3 p 3 3 p 2 2 p 1 2 displaystyle operatorname pot C R C nu 0 1 C cdot pi 1 3 pi 3 3 pi 2 2 pi 1 2 nbsp Der Kontext C p 2 2 p 1 2 displaystyle C pi 2 2 pi 1 2 nbsp hat hierbei den Zweck die beiden Parameter m displaystyle m nbsp und n displaystyle n nbsp miteinander zu vertauschen Vorgangerfunktion Bearbeiten Die Vorgangerfunktion ist nicht an der Stelle 0 definiert Sie ist also nicht primitiv rekursiv Durch Fortsetzung an der Stelle 0 zum Beispiel mit dem Wert 0 kann man jedoch eine primitiv rekursive Funktion daraus machen Die modifizierte Vorgangerfunktion p N N displaystyle p colon mathbb N to mathbb N nbsp definiert durch p n 0 falls n 0 n 1 sonst displaystyle p n begin cases 0 amp mbox falls n 0 n 1 amp mbox sonst end cases nbsp fur alle n N displaystyle n in mathbb N nbsp ist primitiv rekursiv denn es gilt p R 0 0 p 2 2 displaystyle p R 0 0 pi 2 2 nbsp Subtraktion Bearbeiten Auch die Subtraktion ist nicht auf allen Paaren naturlicher Zahlen definiert Man setzt also die Subtraktion durch Auffullen mit Nullen fort auf ganz N 2 displaystyle mathbb N 2 nbsp Diese totale Subtraktion sub N 2 N displaystyle operatorname sub colon mathbb N 2 to mathbb N nbsp kann rekursiv charakterisiert werden durch sub m n m falls n 0 p sub m n 1 sonst displaystyle operatorname sub m n begin cases m amp mbox falls n 0 p operatorname sub m n 1 amp mbox sonst end cases nbsp fur alle m n N displaystyle m n in mathbb N nbsp Fur die totale Subtraktion gilt s u b C R p 1 1 C p p 1 3 p 2 2 p 1 2 displaystyle sub C R pi 1 1 C p pi 1 3 pi 2 2 pi 1 2 nbsp sie ist also primitiv rekursiv Man nennt diese modifizierte Differenz auch arithmetische Differenz Weitere Beispiele Bearbeiten Die zweistelligen Funktionen max displaystyle max nbsp und min displaystyle min nbsp sind primitiv rekursiv Die Folge der Primzahlen ist eine primitiv rekursive Funktion Die Funktion die zu einer naturlichen Zahl n displaystyle n nbsp und einer Primzahl p displaystyle p nbsp die Anzahl der Primfaktoren von p displaystyle p nbsp in n displaystyle n nbsp ermittelt ist primitiv rekursiv Es existieren primitiv rekursive Arithmetisierungen endlicher Folgen naturlicher Zahlen Die Ackermannfunktion und die Sudanfunktion sind nicht primitiv rekursiv aber µ rekursiv Die Funktion Fleissiger Biber busy beaver ist nicht primitiv rekursiv und nicht µ rekursiv Siehe auch Bearbeitenµ Rekursion TuringmaschineLiteratur BearbeitenHans Hermes Aufzahlbarkeit Entscheidbarkeit Berechenbarkeit 2 Auflage Springer Berlin Heidelberg New York 1971 ISBN 3 540 05334 4 Heinz Dieter Ebbinghaus Jorg Flum Wolfgang Thomas Einfuhrung in die mathematische Logik 4 Auflage Spektrum Akademischer Verlag Heidelberg u a 1996 ISBN 3 8274 0130 5 Hochschultaschenbuch Arnold Oberschelp Rekursionstheorie BI Wissenschaftlicher Verlag Mannheim u a 1993 ISBN 3 411 16171 X Wolfgang Rautenberg Einfuhrung in die Mathematische Logik 3 Auflage Vieweg Teubner Wiesbaden ISBN 978 3 8348 0578 2 Einzelnachweise Bearbeiten Peter Schroeder Heister Mathematische Logik II Godelsche Unvollstandigkeitssatze Skript S 39 Abgerufen von https de wikipedia org w index php title Primitiv rekursive Funktion amp oldid 239201152