Goto-berechenbar/partiell < Logik < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 04:31 Mi 15.05.2013 | | Autor: | Lu- |
| Aufgabe | Wie kann ich zeigen, dass die partiell rekursiven Funktionen genau die goto-berechenbaren partielle Funktionen sind.
Wenn ich weiß:Die rekursiven Funktionen sind genau die GoTo-berechenbaren (totalen) Funktionen. |
Hi,
Partielle Funktionen sind Funktionen deren Definitionsbereich nur Teilmenge von [mm] \IN^k [/mm] sind.
Def.:
Eine partielle Funktion f: [mm] \IN^k [/mm] --> [mm] \IN [/mm] geißt GoTo-berechnbera, fall es ein GoTo Programm gibt welches die Funktion im folgenden Sinn berechnet:
Falls das programm zu beginn in den Registern [mm] input_1 [/mm] ,.., [mm] input_k [/mm] die Zahlen [mm] x_1 [/mm] ,.., [mm] x_k \in \In [/mm] stehen hat und in allen anderen Registern die zahl 0, dann passiert folgendes:
-> Falls [mm] f(x_1 [/mm] ,., [mm] x_k) [/mm] definiert ist, dann hält das Programm an, und am Ende steht in Regsieter output die Zahl [mm] f(x_1 [/mm] ,.., [mm] x_k)
[/mm]
-> Falls [mm] f(x_1 [/mm] ,.., [mm] x_k) [/mm] nicht definiert ist, dann hält das Programm nicht an.
Der unterschied zur partiellen Rekursion und zur Rekursion war das die Regel der [mm] \mu [/mm] Reksursion uneingeschränkt durchgeführt werden kann und bei Rekursion nur wenn [mm] \forall \overline{x} \in \IN^k \exists [/mm] y [mm] \in \IN. f(\overline{x} [/mm] , y) >0.
Oder ist das klar, weil Fall 2) gar nicht eintritt bei den partielle Funkt?
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 05:20 Fr 17.05.2013 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
