~2025-37651-59: /* Definition der μ-rekursiven Funktionen */

2025-12-01T15:58:59Z

Definition der μ-rekursiven Funktionen

Neue Seite

{{SEITENTITEL:μ-Rekursion}}
Die Klasse ''Pr'' der '''μ-rekursiven Funktionen''' oder '''partiell-rekursiven Funktionen''' spielt in der [[Rekursionstheorie]], einem Teilgebiet der [[Theoretische Informatik|theoretischen Informatik]], eine wichtige Rolle ('''µ''' für {{elS|μικρότατος}} ‚das kleinste‘). Nach der [[Church-Turing-These]] beschreibt sie die Menge aller Funktionen, die im intuitiven Sinn [[Berechenbarkeit|berechenbar]] sind. Eine wichtige echte [[Teilmenge]] der μ-rekursiven Funktionen sind die [[Primitiv-rekursive Funktion|primitiv-rekursiven Funktionen]].

Die Klasse der μ-rekursiven Funktionen stimmt überein mit der Klasse der [[Turing-Berechenbarkeit|Turing-berechenbaren]] Funktionen sowie weiteren gleich mächtigen Berechenbarkeitsmodellen, wie dem [[Lambda-Kalkül]], [[Registermaschine]]n und [[WHILE-Programm]]en.

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 Funktion|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\colon\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\ \land\ \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ürliche Zahl|natürlicher Zahlen]] genau dann ein [[Größtes und kleinstes Element|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), & \text{falls } M(f,x_1,\dots,x_k) \neq \emptyset \\ \text{undefiniert} & \text{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 [[Terminiertheit|terminieren]] muss:
<div style="margin-left:2em; max-width:310px; border: 1px solid #448800; padding: 0.4em; background: #F2F2FF;">
Parameter: <math>x_1, \ldots, x_k</math>.<br>
Setze <math>n</math> auf <math>0</math>;<br>
Solange <math>f(x_1,\dots,x_k,n) \neq 0</math>, erhöhe <math>n</math> um <math>1</math>;<br>
Ergebnis: <math>n</math>.
</div>

== Definition der μ-rekursiven Funktionen ==
Die Klasse <math>Pr</math> der μ-rekursiven Funktionen (<math>\mathbb{N}^k \to \mathbb{N}</math>) umfasst die folgenden Grundfunktionen:
# konstante 0-Funktion: <math>f^k \left( n_1,\dots, n_k \right) := 0</math>
# 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>
# 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:
# der 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>
# der primitiven 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>
# des μ-Operators.

== Ä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.

<div style="margin-left:2em; max-width:700px; border: 1px solid #448800; padding: 0.4em; background: #F2FFF2;">
'''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.<br>
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,<br>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>.
</div>

== 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 ==
* [[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.
* {{Literatur |Autor=[[Wolfgang Rautenberg]] |Titel=Einführung in die Mathematische Logik. Ein Lehrbuch |Auflage=3., überarbeitete |Verlag=Vieweg + Teubner |Ort=Wiesbaden |Datum=2008 |ISBN=978-3-8348-0578-2 }}

{{SORTIERUNG:My-Rekursion}}
[[Kategorie:Berechenbarkeitstheorie]]
[[Kategorie:Rekursion]]

[[ru:Рекурсивная функция (теория вычислимости)#Частично рекурсивная функция]]

Μ-Rekursion - Versionsgeschichte

~2025-37651-59: /* Definition der μ-rekursiven Funktionen */