Μ-Rekursion

aus Wikipedia, der freien Enzyklopädie

Du hast neue Nachrichten auf deiner Diskussionsseite.

Der korrekte Titel dieses Artikels lautet „μ-Rekursion“. Diese Schreibweise ist aufgrund technischer Einschränkungen nicht möglich.

Die Klasse P der μ-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 (μ-rekursiven Funktionen, Lambda-Kalkül, Turing-berechenbar, berechenbar durch Registermaschinen etc.) übereinstimmen und den intuitiven Begriff der Berechenbarkeit vollständig erfassen (Churchsche These).

Die μ-rekursiven Funktionen sind partielle Funktionen, die (analog zu den primitiv rekusiven Funktionen) aus einfachen Grundfunktionen (konstante 0-Funktion, Projektionen auf ein Argument und Nachfolgefunktion) durch Komposition und (primitiver) Rekursion und durch die Anwendung des μ-Operators gebildet werden können.

Die Klasse der μ-rekursiven Funktionen und der WHILE-berechenbaren (vgl. WHILE-Programm) Funktionen sind äquivalent.

Inhaltsverzeichnis

1 Definition des μ-Operators
2 Definition der μ-rekursiven Funktionen
3 Äquivalenz der μ-rekursiven Funktionen mit der TM
4 Bemerkung
5 Beispiele
6 Siehe auch:
7 Literatur
8 Weblinks

[Bearbeiten] Definition des μ-Operators

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

$\mu f(x) = \begin{cases} \min \{ n \geq 0 | f(n,x) = 0 \mbox{ und } f(m,x) \mbox{ ist definiert } \forall m < n \} & \mbox{falls das Minimum existiert} \\ \mbox{undefiniert} & \mbox{sonst.}\\ \end{cases}$

D. h. $μ$ bildet eine $(n + 1)$ -stellige Funktion auf eine $n$ -stellige Funktion ab und wird als μ-Operators bezeichnet.

[Bearbeiten] Definition der μ-rekursiven Funktionen

Die Klasse $P r$ der μ-rekursiven Funktionen (von $\mathbb{N}^k \rightarrow \mathbb{N}$ ) umfasst die folgenden Grundfunktionen:

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

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

Die Komposition: $f \left( n_1, ..., n_k \right) := g \left( h_1 \left( n_1, ..., n_k \right), ..., h_m \left( n_1, ..., n_k \right) \right)$ , falls $g, h_1, ..., h_m \in Pr$
Die Primitive Rekursion: $f \left( 0, n_2, ..., n_k \right) := g \left( n_2, ..., n_k \right)$ und $f \left( n_1 + 1, n_2, ..., n_k \right) := h \left( f \left( n_1, ..., n_k \right), n_1, ..., n_k \right)$ , falls $h, g \in Pr$
Den μ-Operator.

[Bearbeiten] Äquivalenz der μ-rekursiven Funktionen mit der TM

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-Idee 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 $N^3 \to 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$ .

[Bearbeiten] Bemerkung

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

[Bearbeiten] 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 $| p |$ die Länge des Programms in Bit bezeichnet.

[Bearbeiten] Siehe auch:

[Bearbeiten] Literatur

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

[Bearbeiten] Weblinks

Von „http://de.wikipedia.org../../../%CE%BC/-/r/%CE%9C-Rekursion_f3d5.html“

Kategorien: Berechenbarkeitstheorie | Theoretische Informatik | Rekursion

Μ-Rekursion

aus Wikipedia, der freien Enzyklopädie

Inhaltsverzeichnis

[Bearbeiten] Definition des μ-Operators

[Bearbeiten] Definition der μ-rekursiven Funktionen

[Bearbeiten] Äquivalenz der μ-rekursiven Funktionen mit der TM

[Bearbeiten] Bemerkung

[Bearbeiten] Beispiele

[Bearbeiten] Siehe auch:

[Bearbeiten] Literatur

[Bearbeiten] Weblinks

Views

Navigation

Mitmachen

Suche

Andere Sprachen