www.wikidata.de-de.nina.az

μ Rekursion Die Klasse Pr der μ rekursiven Funktionen oder partiell rekursiven Funktionen spielt in der Rekursionstheori

μ-Rekursion

Die Klasse Pr der μ-rekursiven Funktionen oder partiell-rekursiven Funktionen spielt in der Rekursionstheorie, einem Teilgebiet der theoretischen Informatik, eine wichtige Rolle (µ für griechisch μικρότατος ‚das kleinste‘). Nach der Church-Turing-These beschreibt sie die Menge aller Funktionen, die im intuitiven Sinn berechenbar sind. Eine wichtige echte Teilmenge der μ-rekursiven Funktionen sind die primitiv-rekursiven Funktionen.

Die Klasse der μ-rekursiven Funktionen stimmt überein mit der Klasse der Turing-berechenbaren Funktionen sowie weiteren gleich mächtigen Berechenbarkeitsmodellen, wie dem Lambda-Kalkül, Registermaschinen und WHILE-Programmen.

Die primitiv-rekursiven Funktionen sind aus einfachen Grundfunktionen (konstante 0-Funktion, Projektionen auf ein Argument und Nachfolgerfunktion) durch Komposition und primitive Rekursion aufgebaut. Dadurch erhält man immer totale Funktionen, also Funktionen im eigentlichen Sinn. Die μ-rekursiven Funktionen sind demgegenüber partielle Funktionen, die aus denselben Konstrukten und zusätzlich durch die Anwendung des μ-Operators gebildet werden können. Durch die Anwendung des μ-Operators wird Partialität eingeführt. Jedoch ist nicht jede μ-rekursive Funktion nicht-total. Beispielsweise sind alle primitiv-rekursiven Funktionen auch μ-rekursiv. Ein Beispiel für eine nicht primitiv-rekursive, totale, μ-rekursive Funktion ist die Ackermannfunktion.

Definition des μ-Operators Bearbeiten

Für eine partielle Funktion und natürliche Zahlen sei die Menge

festgehalten, also die Gesamtheit aller derart, dass an der Stelle identisch 0 verschwindet und zusätzlich für alle Punkte mit definiert ist.

Zu beachten ist dabei, dass als Menge natürlicher Zahlen genau dann ein Minimum besitzt, wenn sie nicht leer ist. (vgl. Wohlordnung)

Durch Anwendung des -Operators auf entstehe nun die partielle Funktion definiert durch:

Insbesondere bildet der Operator also eine -stellige partielle Funktion auf eine -stellige partielle Funktion ab.

Für berechenbares kann das Programm zur Berechnung von verstanden werden als eine While-Schleife, die nach oben zählt, und die deswegen nicht terminieren muss:

Parameter: .
Setze auf ;
Solange erhöhe um ;
Ergebnis: .

Definition der μ-rekursiven Funktionen Bearbeiten

Die Klasse der μ-rekursiven Funktionen (von ) umfasst die folgenden Grundfunktionen:

  1. konstante 0-Funktion:
  2. Projektion auf ein Argument: ,
  3. Nachfolgefunktion:

Die μ-rekursiven Funktionen erhält man als Abschluss der Grundfunktionen bezüglich der drei folgenden Operationen:

  1. Die Komposition: , falls
  2. Die Primitive Rekursion: und , falls
  3. Der μ-Operator.

Äquivalenz der μ-rekursiven Funktionen mit der Turingmaschine Bearbeiten

Es lässt sich beweisen, dass eine Turingmaschine (TM) durch μ-rekursive Funktionen simuliert werden kann. Es lässt sich auch beweisen, dass die Menge der μ-rekursiven Funktionen genau der Menge der Turing-berechenbaren Funktionen entspricht.

Beweis-Skizze für die Simulation der TM mit μ-rekursiven Funktionen

Man kann zeigen, dass sich die Konfiguration einer TM durch drei Zahlen , , darstellen lässt.
Genau so kann eine Funktion (eine bijektive Abbildung ) definiert werden,
die eine geeignete Kodierung der TM ist.

Nehmen wir also eine primitiv-rekursive Funktion

die eine geeignete Kodierung der TM liefert für die Eingabe nach Berechnungsschritten,

und eine zweite primitiv-rekursive Funktion

die für eine Kodierung als Ergebnis 0 liefert, falls einen Endzustand der TM repräsentiert, und ansonsten 1.

Dann ergibt

die Anzahl der Schritte, die eine TM zur Berechnung bis zum Ende benötigt. Also bekommen wir mit

die Berechnung der TM in einem Endzustand bei der Eingabe .

Bemerkung Bearbeiten

  • Die Berechenbarkeit einer μ-rekursiven Funktion bezieht sich auf Werte aus ihrem Definitionsbereich. Es existiert kein allgemeines Verfahren, das alle Werte liefert, die nicht zum Definitionsbereich einer μ-rekursiven Funktion gehören.
  • Der μ-Operator realisiert einen Suchprozess, der genau dann abbricht, wenn der gesuchte Wert existiert.

Beispiele Bearbeiten

  • Alle primitiv-rekursiven Funktionen sind μ-rekursiv.
  • Die Ackermannfunktion und die Sudanfunktion sind totale μ-rekursive Funktionen, die nicht primitiv-rekursiv sind.
  • Die Funktion Fleißiger Biber (busy beaver) ist nicht μ-rekursiv.
  • Die Folge der Ziffern der Halte-Wahrscheinlichkeit (Chaitinsche Konstante ) ist nicht μ-rekursiv. Die Halte-Wahrscheinlichkeit ist definiert durch
wobei ein haltendes Programm ist und die Länge des Programms in Bit bezeichnet.

Literatur Bearbeiten

  • Heinz-Dieter Ebbinghaus, Jörg Flum, Wolfgang Thomas: Einführung in die mathematische Logik (= Spektrum-Hochschultaschenbuch.). 4. Auflage. Spektrum – Akademischer Verlag, Heidelberg u. a. 1996, ISBN 3-8274-0130-5.
  • Hans Hermes: Aufzählbarkeit, Entscheidbarkeit, Berechenbarkeit. Einführung in die Theorie der rekursiven Funktionen (= Heidelberger Taschenbücher. 87). 2. Auflage. Springer, Berlin u. a. 1971, ISBN 3-540-05334-4.
  • Arnold Oberschelp: Rekursionstheorie. BI-Wissenschaftlicher-Verlag, Mannheim u. a. 1993, ISBN 3-411-16171-X.
  • Wolfgang Rautenberg: Einführung in die Mathematische Logik. Ein Lehrbuch. 3., überarbeitete Auflage. Vieweg + Teubner, Wiesbaden 2008, ISBN 978-3-8348-0578-2.
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:
Die Klasse Pr der m rekursiven Funktionen oder partiell rekursiven Funktionen spielt in der Rekursionstheorie einem Teilgebiet der theoretischen Informatik eine wichtige Rolle µ fur griechisch mikrotatos das kleinste Nach der Church Turing These beschreibt sie die Menge aller Funktionen die im intuitiven Sinn berechenbar sind Eine wichtige echte Teilmenge der m rekursiven Funktionen sind die primitiv rekursiven Funktionen Die Klasse der m rekursiven Funktionen stimmt uberein mit der Klasse der Turing berechenbaren Funktionen sowie weiteren gleich machtigen Berechenbarkeitsmodellen wie dem Lambda Kalkul Registermaschinen und WHILE Programmen Die primitiv rekursiven Funktionen sind aus einfachen Grundfunktionen konstante 0 Funktion Projektionen auf ein Argument und Nachfolgerfunktion durch Komposition und primitive Rekursion aufgebaut Dadurch erhalt man immer totale Funktionen also Funktionen im eigentlichen Sinn Die m rekursiven Funktionen sind demgegenuber partielle Funktionen die aus denselben Konstrukten und zusatzlich durch die Anwendung des m Operators gebildet werden konnen Durch die Anwendung des m Operators wird Partialitat eingefuhrt Jedoch ist nicht jede m rekursive Funktion nicht total Beispielsweise sind alle primitiv rekursiven Funktionen auch m rekursiv Ein Beispiel fur eine nicht primitiv rekursive totale m rekursive Funktion ist die Ackermannfunktion Inhaltsverzeichnis 1 Definition des m Operators 2 Definition der m rekursiven Funktionen 3 Aquivalenz der m rekursiven Funktionen mit der Turingmaschine 4 Bemerkung 5 Beispiele 6 LiteraturDefinition des m Operators BearbeitenFur eine partielle Funktion f N k 1 N displaystyle f colon mathbb N k 1 to mathbb N nbsp und naturliche Zahlen x 1 x k N displaystyle x 1 dots x k in mathbb N nbsp sei die Menge M f x 1 x k n N f x 1 x k n 0 0 m n f x 1 x k m displaystyle M f x 1 dots x k n in mathbb N mid f x 1 dots x k n 0 land forall 0 leq m leq n colon f x 1 dots x k m downarrow nbsp festgehalten also die Gesamtheit aller n displaystyle n nbsp derart dass f displaystyle f nbsp an der Stelle x 1 x k n displaystyle x 1 dots x k n nbsp identisch 0 verschwindet und zusatzlich fur alle Punkte x 1 x k m displaystyle x 1 dots x k m nbsp mit m n displaystyle m leq n nbsp definiert ist Zu beachten ist dabei dass M f x 1 x k displaystyle M f x 1 dots x k nbsp als Menge naturlicher Zahlen genau dann ein Minimum besitzt wenn sie nicht leer ist vgl Wohlordnung Durch Anwendung des m displaystyle mu nbsp Operators auf f displaystyle f nbsp entstehe nun die partielle Funktion m f N k N displaystyle mu f colon mathbb N k to mathbb N nbsp definiert durch m f x 1 x k min M f x 1 x k falls M f x 1 x k undefiniert sonst displaystyle mu f x 1 dots x k begin cases min M f x 1 dots x k amp mbox falls M f x 1 dots x k not emptyset mbox undefiniert amp mbox sonst end cases nbsp Insbesondere bildet der Operator m displaystyle mu nbsp also eine k 1 displaystyle k 1 nbsp stellige partielle Funktion auf eine k displaystyle k nbsp stellige partielle Funktion ab Fur berechenbares f displaystyle f nbsp kann das Programm zur Berechnung von m f displaystyle mu f nbsp verstanden werden als eine While Schleife die nach oben zahlt und die deswegen nicht terminieren muss Parameter x 1 x k displaystyle x 1 x k nbsp Setze n displaystyle n nbsp auf 0 displaystyle 0 nbsp Solange f x 1 x k n 0 displaystyle f x 1 dots x k n not 0 nbsp erhohe n displaystyle n nbsp um 1 displaystyle 1 nbsp Ergebnis n displaystyle n nbsp Definition der m rekursiven Funktionen BearbeitenDie Klasse P r displaystyle Pr nbsp der m rekursiven Funktionen von N k N displaystyle mathbb N k to mathbb N nbsp umfasst die folgenden Grundfunktionen konstante 0 Funktion f k n 1 n k 0 displaystyle f k left n 1 dots n k right 0 nbsp Projektion auf ein Argument p i k n 1 n k n i displaystyle pi i k left n 1 dots n k right n i nbsp 1 i k displaystyle 1 leq i leq k nbsp Nachfolgefunktion n n n 1 displaystyle nu left n right n 1 nbsp Die m rekursiven Funktionen erhalt man als Abschluss der Grundfunktionen bezuglich der drei folgenden Operationen Die Komposition f n 1 n k g h 1 n 1 n k h m n 1 n k displaystyle f 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 falls g h 1 h m P r displaystyle g h 1 dots h m in Pr nbsp Die Primitive Rekursion f 0 n 2 n k g n 2 n k displaystyle f left 0 n 2 dots n k right g left n 2 dots n k right nbsp und f n 1 1 n 2 n k h f n 1 n k n 1 n k displaystyle f left n 1 1 n 2 dots n k right h left f left n 1 dots n k right n 1 dots n k right nbsp falls h g P r displaystyle h g in Pr nbsp Der m Operator Aquivalenz der m rekursiven Funktionen mit der Turingmaschine BearbeitenEs lasst sich beweisen dass eine Turingmaschine TM durch m rekursive Funktionen simuliert werden kann Es lasst sich auch beweisen dass die Menge der m rekursiven Funktionen genau der Menge der Turing berechenbaren Funktionen entspricht Beweis Skizze fur die Simulation der TM mit m rekursiven FunktionenMan kann zeigen dass sich die Konfiguration einer TM durch drei Zahlen a displaystyle a nbsp b displaystyle b nbsp c displaystyle c nbsp darstellen lasst Genau so kann eine Funktion h a b c y displaystyle h a b c y nbsp eine bijektive Abbildung N 3 N displaystyle mathbb N 3 to mathbb N nbsp definiert werden die eine geeignete Kodierung der TM ist Nehmen wir also eine primitiv rekursive Funktion f n x y displaystyle f n x y nbsp die eine geeignete Kodierung der TM liefert fur die Eingabe x displaystyle x nbsp nach n displaystyle n nbsp Berechnungsschritten und eine zweite primitiv rekursive Funktion g y 0 g y 1 displaystyle g y 0 lor g y 1 nbsp die fur eine Kodierung y displaystyle y nbsp als Ergebnis 0 liefert falls y displaystyle y nbsp einen Endzustand der TM reprasentiert und ansonsten 1 Dann ergibt A n z a h l x m g f n x displaystyle mathrm Anzahl x mu g f n x nbsp die Anzahl der Schritte die eine TM zur Berechnung bis zum Ende benotigt Also bekommen wir mit B e r e c h n u n g x f A n z a h l x x displaystyle mathrm Berechnung x f mathrm Anzahl x x nbsp die Berechnung der TM in einem Endzustand bei der Eingabe x displaystyle x nbsp Bemerkung BearbeitenDie Berechenbarkeit einer m rekursiven Funktion bezieht sich auf Werte aus ihrem Definitionsbereich Es existiert kein allgemeines Verfahren das alle Werte liefert die nicht zum Definitionsbereich einer m rekursiven Funktion gehoren Der m Operator realisiert einen Suchprozess der genau dann abbricht wenn der gesuchte Wert existiert Beispiele BearbeitenAlle primitiv rekursiven Funktionen sind m rekursiv Die Ackermannfunktion und die Sudanfunktion sind totale m rekursive Funktionen die nicht primitiv rekursiv sind Die Funktion Fleissiger Biber busy beaver ist nicht m rekursiv Die Folge der Ziffern der Halte Wahrscheinlichkeit Chaitinsche Konstante W displaystyle Omega nbsp ist nicht m rekursiv Die Halte Wahrscheinlichkeit ist definiert durchW p 2 p displaystyle Omega sum p 2 left p right nbsp dd wobei p displaystyle p nbsp ein haltendes Programm ist und p displaystyle left p right nbsp die Lange des Programms in Bit bezeichnet Literatur BearbeitenHeinz Dieter Ebbinghaus Jorg Flum Wolfgang Thomas Einfuhrung in die mathematische Logik Spektrum Hochschultaschenbuch 4 Auflage Spektrum Akademischer Verlag Heidelberg u a 1996 ISBN 3 8274 0130 5 Hans Hermes Aufzahlbarkeit Entscheidbarkeit Berechenbarkeit Einfuhrung in die Theorie der rekursiven Funktionen Heidelberger Taschenbucher 87 2 Auflage Springer Berlin u a 1971 ISBN 3 540 05334 4 Arnold Oberschelp Rekursionstheorie BI Wissenschaftlicher Verlag Mannheim u a 1993 ISBN 3 411 16171 X Wolfgang Rautenberg Einfuhrung in die Mathematische Logik Ein Lehrbuch 3 uberarbeitete Auflage Vieweg Teubner Wiesbaden 2008 ISBN 978 3 8348 0578 2 Abgerufen von https de wikipedia org w index php title M Rekursion amp oldid 238226384