Rekursive Funktionen < Komplex. & Berechnb. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 19:36 Do 30.04.2015 | | Autor: | mariem |
Hallo,
ich lese gerade die Definitionen der primitiv rekursiven Funktionen und der rekursiven Funktionen.
Die Definition von [mm] \mu-rekursive [/mm] Funktionen ist die folgende:
1. The constant, projection, and successor functions are all [mm] \mu-recursive. [/mm]
2. If [mm] g_1, \dots [/mm] , [mm] g_m [/mm] are n-variable [mm] \mu-recursive [/mm] functions and h is an m-variable [mm] \mu-recursive [/mm] function, then the composite function f=h [mm] \circ (g_1, \dots [/mm] , [mm] g_m) [/mm] is also [mm] \mu-recursive. [/mm]
3. If g and h are n- and (n+2)-variable [mm] \mu-recursive [/mm] functions, then the function f defined from g and h by primitive recursion is also [mm] \mu-recursive. [/mm]
4. If g is a total (n+1)-variable [mm] \mu-recursive [/mm] function, then the function f defined from g by unbounded minimalization is also [mm] \mu-recursive. [/mm]
Die Definition von primitiv rekursive Funktionen ist die folgende:
1. The constant, projection, and successor functions are all primitive recursive functions.
2. If [mm] g_1, \dots [/mm] , [mm] g_m [/mm] are n-variable primitive recursive functions, and if h is an m-variable primitve recursive function, then the composite function h [mm] \circ (g_1, \dots [/mm] , [mm] g_m) [/mm] is also a primitive recursive function.
3. If g and h are n- and (n+1)-variable primitive recursive functions, then (n+1)-variable function f defined from g and h by primitive recursion is also a primitive recursive function.
Der Unterschied zwischen den zwei Definitionen ist der [mm] \mu-Operator, [/mm] oder nicht?
Er ist folgenderweise definiert:
[mm] f(\overline{x})= \left\{\begin{matrix}
\mu z(g(z,\overline{x})=0)=\min \{z \in \mathbb{N}_0 \mid g(z, \overline{x})=0\} & \text{ wenn } ( \exists z) (g(z,\overline{x})=0)\\
\text{ undefiniert } & \text{ anderesfalls }
\end{matrix}\right. [/mm]
richtig?
Also wegen den [mm] \mu-Operator [/mm] gibt es Funktionen die rekursiv sind aber nicht primitiv rekursiv?
Warum ist es so? Könnt ihr mir das erklären?
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 20:21 Do 07.05.2015 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
