Μ-Rekursion - LinkFang.de





Μ-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 griech. μικρότατος = 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

Für eine partielle Funktion [math]f:\mathbb{N}^{k+1} \to \mathbb{N}[/math] und natürliche Zahlen [math]x_1;\dots;x_k \in \N[/math] sei die Menge

[math]M(f,x_1,\dots,x_k) = \{n \in \N \mid f(x_1,\dots,x_k,n) = 0\ \and\ \forall 0 \leq m \leq n \colon f(x_1,\dots,x_k,m) \downarrow \}[/math]

festgehalten, also die Gesamtheit aller [math]n[/math] derart, dass [math]f[/math] an der Stelle [math](x_1,\dots,x_k,n)[/math] identisch 0 verschwindet und zusätzlich für alle Punkte [math](x_1,\dots,x_k,m)[/math] mit [math]m \leq n[/math] definiert ist.

Zu beachten ist dabei, dass [math]M(f,x_1,\dots,x_k)[/math] als Menge natürlicher Zahlen genau dann ein Minimum besitzt, wenn sie nicht leer ist. (vgl. Wohlordnung)

Durch Anwendung des [math]\mu[/math]-Operators auf [math]f[/math] entstehe nun die partielle Funktion [math]\mu f \colon \N^k \to \N[/math] definiert durch:

[math]\mu f(x_1, \dots, x_k) = \begin{cases} \min M(f,x_1,\dots,x_k) & \mbox{falls } M(f,x_1,\dots,x_k) \not= \emptyset \\ \mbox{undefiniert} & \mbox{sonst}\\ \end{cases}[/math]

Insbesondere bildet der Operator [math]\mu[/math] also eine [math](k+1)[/math]-stellige partielle Funktion auf eine [math]k[/math]-stellige partielle Funktion ab.

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

Parameter: [math]x_1, ..., x_k[/math].
Setze [math]n[/math] auf [math]0[/math];
Solange [math]f(x_1,\dots,x_k,n) \not= 0[/math] erhöhe [math]n[/math] um [math]1[/math];
Ergebnis: [math]n[/math].

Definition der μ-rekursiven Funktionen

Die Klasse [math]Pr[/math] der μ-rekursiven Funktionen (von [math]\mathbb{N}^k \to \mathbb{N}[/math]) umfasst die folgenden Grundfunktionen:

  1. konstante 0-Funktion: [math]f^k \left( n_1,\dots, n_k \right) := 0[/math]
  2. Projektion auf ein Argument: [math]\pi_i^k \left( n_1,\dots, n_k \right) := n_i[/math], [math]1 \le i \le k[/math]
  3. Nachfolgefunktion: [math]\nu \left( n \right) := n + 1[/math]

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

  1. Die Komposition: [math]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)[/math], falls [math]g, h_1,\dots, h_m \in Pr[/math]
  2. Die Primitive Rekursion: [math]f \left( 0, n_2,\dots, n_k \right) := g \left( n_2,\dots, n_k \right)[/math] und [math]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)[/math], falls [math]h, g \in Pr[/math]
  3. Der μ-Operator.

Äquivalenz der μ-rekursiven Funktionen mit der Turingmaschine

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 [math]a[/math], [math]b[/math], [math]c[/math] darstellen lässt. Genau so kann eine Funktion [math]h(a,b,c)=y[/math] (eine bijektive Abbildung [math]\mathbb{N}^3 \to \mathbb{N}[/math]) definiert werden, die eine geeignete Kodierung der TM ist.

Nehmen wir also eine primitiv-rekursive Funktion

[math]f(n,x)= y[/math],

die eine geeignete Kodierung der TM liefert für die Eingabe [math]x[/math] nach [math]n[/math] Berechnungsschritten,

und eine zweite primitiv-rekursive Funktion

[math]g(y)=0 \lor g(y)=1[/math],

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

Dann ergibt

[math]\mathrm{Anzahl}(x)=\mu(g(f(n,x)))[/math]

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

[math]\mathrm{Berechnung}(x)=f(\mathrm{Anzahl}(x), x)[/math]

die Berechnung der TM in einem Endzustand bei der Eingabe [math]x[/math].

Bemerkung

  • 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

  • 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 [math]\Omega[/math]) ist nicht μ-rekursiv. Die Halte-Wahrscheinlichkeit ist definiert durch [math]\Omega:=\sum_{p}2^{-\left|p\right|}[/math], wobei [math]p[/math] ein haltendes Programm ist und [math]\left| p\right|[/math] die Länge des Programms in Bit bezeichnet.

Literatur


Kategorien: Keine Kategorien vorhanden!

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Μ-Rekursion (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.