Μ-Rekursion

Μ-Rekursion


Die Klasse Pr der μ-rekursiven Funktionen oder partiell-rekursiven Funktionen spielt in der Rekursionstheorie, einem Teilgebiet der theoretischen Informatik, eine wichtige Rolle. Sie beschreibt 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. Es stellt sich heraus, dass die unterschiedlichen entwickelten Berechenbarkeitsbegriffe (μ-rekursive Funktionen, Lambda-Kalkül, Turingmaschinen, Registermaschinen, WHILE-Programme etc.) übereinstimmen und den intuitiven Begriff der Berechenbarkeit vollständig erfassen (Churchsche These).

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.

Inhaltsverzeichnis

Definition des μ-Operators

Für eine partielle Funktion f:\mathbb{N}^{k+1} \to \mathbb{N} ist die partielle Funktion \mu f : \mathbb{N}^k \to \mathbb{N} definiert durch:

\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}

wobei die Menge M(f,x_1,\dots,x_k) definiert ist als

\{ n \geq 0 | f(x_1,\dots,x_k,n) = 0 \mbox{ und } f(x_1,\dots,x_k,m) \mbox{ ist definiert für alle } m < n \}

Insbesondere bildet der Operator μ eine (k + 1)-stellige partielle Funktion auf eine k-stellige partielle Funktion ab.

Das Programm μf kann verstanden werden als eine While-Schleife, die nach oben zählt, und die deswegen nicht terminieren muss:

Parameter: x1,...,xk.
Setze n auf 0;
Solange f(x_1,\dots,x_k,n) \not= 0 erhöhe n um Eins;
Ergebnis: n.

Definition der μ-rekursiven Funktionen

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

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

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

  1. Die Komposition: 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), falls g, h_1,\dots, h_m \in Pr
  2. Die Primitive Rekursion: f \left( 0, n_2,\dots, n_k \right) := g \left( n_2,\dots, n_k \right) und 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), falls h, g \in Pr
  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 a, b, c darstellen lässt. Genau so kann eine Funktion h(a,b,c) = y (eine bijektive Abbildung \mathbb{N}^3 \to \mathbb{N}) definiert werden, die eine geeignete Kodierung der TM ist.

Nehmen wir also eine primitiv-rekursive Funktion

f(n,x) = y,

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

und eine zweite primitiv-rekursive Funktion

g(y)=0 \lor g(y)=1,

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

Dann ergibt

Anzahl(x) = μ(g(f(n,x)))

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

Berechnung(x) = f(Anzahl(x),x)

die Berechnung der TM in einem Endzustand bei der Eingabe x.

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 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 \Omega:=\sum_{p}2^{-\left|p\right|}, wobei p ein haltendes Programm ist und \left| p\right| die Länge des Programms in Bit bezeichnet.

Literatur

  • H.-D. Ebbinghaus, J. Flum, W. Thomas: Einführung in die mathematische Logik. Spektrum, Akad. Verl., Heidelberg, Berlin 1996.
  • A. Oberschelp: Rekursionstheorie. BI-Wiss.-Verl., Mannheim, Leipzig, Wien, Zürich 1993.

Wikimedia Foundation.

См. также в других словарях:

  • Rekursion — in einem Bildschirm Aufnahmeprogramm. Als Rekursion (lat. recurrere „zurücklaufen“) bezeichnet man die Technik in Mathematik, Logik und Informatik, eine Funktion durch sich selbst zu definieren (rekursive Definition). Wenn man mehrere Funktionen… …   Deutsch Wikipedia

  • Rekursion — Re|kur|si|on 〈f. 20; Math.; EDV〉 Definition einer Funktion od. eines Verfahrens durch sich selbst, wie z. B. bei der Fakultätsfunktion n! 0! = 1 und für n > 0 gilt n! = n · (n 1)! * * * Rekursion   [spätlat. »das Zurücklaufen«], ein Verfahren …   Universal-Lexikon

  • Rekursion — formales Prinzip, demzufolge bei der Beschreibung eines Sachverhalts auf den zu beschreibenden Sachverhalt selbst Bezug genommen wird. Beispiel (mathematische Definition der Fakultät einer Zahl n): n! = (n – 1)! n. Häufig in der Mathematik und in …   Lexikon der Economics

  • Rekursion — Re|kur|si|on die; <aus spätlat. recursio »das Zurücklaufen«, zu lat. recursus, Part. Perf. von recurrere, vgl. ↑rekurrieren>: 1. Definition eines Problems od. eines Verfahrens durch sich selbst (Informatik, EDV). 2. die Zurückführung einer… …   Das große Fremdwörterbuch

  • Transfinite Rekursion — Transfinite Induktion ist eine Beweistechnik in der Mathematik, die die von den natürlichen Zahlen bekannte Induktion auf beliebige wohlgeordnete Mengen verallgemeinert, zum Beispiel auf Mengen von Ordinalzahlen oder Kardinalzahlen, oder sogar… …   Deutsch Wikipedia

  • Primitive Rekursion — 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. Der Begriff… …   Deutsch Wikipedia

  • Lineare Rekursion — Lineare Differenzengleichungen oder lineare Rekursionsgleichungen sind Beziehungen einer besonders einfachen Form zwischen den Gliedern einer Folge. Das bekannteste Beispiel ist die Fibonacci Folge für natürliche Zahlen n, konkret 0, 1, 1, 2, 3,… …   Deutsch Wikipedia

  • μ-Rekursion — Die Klasse Pr der μ rekursiven Funktionen oder partiell rekursiven Funktionen spielt in der Rekursionstheorie, einem Teilgebiet der theoretischen Informatik, eine wichtige Rolle. Sie beschreibt die Menge aller Funktionen, die im intuitiven Sinn… …   Deutsch Wikipedia

  • My-Rekursion — Die Klasse Pr der μ rekursiven Funktionen oder partiell rekursiven Funktionen spielt in der Rekursionstheorie, einem Teilgebiet der theoretischen Informatik, eine wichtige Rolle. Sie beschreibt die Menge aller Funktionen, die im intuitiven Sinn… …   Deutsch Wikipedia

  • Rekursionsanfang — Dieser Artikel erläutert die Technik der rekursiven Definition; zum Begriff rekursive Menge siehe entscheidbar. Als Rekursion (lat. recurrere „zurücklaufen“) bezeichnet man die Technik in Mathematik, Logik und Informatik, eine Funktion durch sich …   Deutsch Wikipedia


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»