Rekursiv Aufzählbar, Partiell < Logik < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 01:58 Mi 05.06.2013 | | Autor: | Lu- |
| Aufgabe | Zeige:
A ist rekursiv aufzählbar gdw A der Definitionsbereich einer partiellen berechenbaren Funktion ist (D.h: Wenn es ein Compterprogramm P gibt, dass auf Input n terminiert wenn n [mm] \in [/mm] A und sonst nicht, d.h. P sagt einem nicht ob n in A ist oder nicht, sondern es bestätigt einen nur wenn n in A ist) |
A Aufzählbar : A ist Projektion einer rekursiven menge [mm] \overline{A}
[/mm]
A= [mm] \{ \overline{x} \in \IN^k | \exists y : (\overline{x}, y) \in \overline{A}\}
[/mm]
Wir hatten eine Proposition:
A ist rekursiv <=> A = [mm] \emptyset [/mm] oder A ist das Bild einer komponentenweise rekursiven Funktion f: [mm] \IN [/mm] -> [mm] \IN^k.
[/mm]
=>
A aufzählbar
-) A = [mm] \emptyset [/mm] klar
-) A [mm] \not= \emptyset
[/mm]
[mm] \exists [/mm] totale rek Funktion mit A = [mm] W_f
[/mm]
Definiere [mm] \phi(x) [/mm] = [mm] \{y : (f(y)=x)\}
[/mm]
[mm] \phi [/mm] rekursiv = entscheidbar für bel zahlenpaare da ich einsetzte und Gleichheit überprüfen kann.
[mm] D_{\phi} [/mm] = [mm] W_f [/mm] =A
<=
A= Def(f)
f.. partiell rekursive Funktion
Nach Kleenesche Normalform:
Es gibt prim rekursive Funktionen U, [mm] \tau_k:
[/mm]
Wenn P ein Goto-programm codiert, dann hat die durch das Programm definierte partielle k-stellige Funktion [mm] f:\IN^k [/mm] --> [mm] \IN [/mm] die Form
[mm] f(x_1 [/mm] ,.., [mm] x_k) [/mm] = U [mm] (\mu y(\tau_k (P,x_1,..,x_k,y)>0))
[/mm]
Insbesondere existiert [mm] \mu [/mm] y [mm] (\tau_K [/mm] (P, [mm] x_1 [/mm] ,.., [mm] x_k, [/mm] y) >0 ) genau dann wenn [mm] f(x_1 [/mm] ,.., [mm] x_k) [/mm] definiert ist.
Die partiell rekursiven Funktionen = goto berechenbaren Funktionen.
P.. Goto-Programm für die partiell rekursive Funktion
[mm] \exists [/mm] y s.d. [mm] \tau_k [/mm] (P, [mm] \overline{x},y)>0 [/mm] <=> [mm] f(\overline{x}) [/mm] definiert <=> [mm] \overline{x} \in [/mm] A
Erste <=> (Kleenesche Normalform)
Zweite <=> (Def(f)=A)
A projektion: A= [mm] \{ \overline{x} \in \IN^k | \exists y : \tau_k(P,\overline{x},y)>0)\}
[/mm]
Bedingung sogar primitiv rekursiv
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 02:20 Fr 07.06.2013 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
