(Un)entscheidbare Mengen < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 20:08 Mo 18.02.2008 | | Autor: | Gilga |
| Aufgabe | Sind folgende Mengen rekursiv?:
Menge aller Funktionen mit endlichem Urbild
Menge aller Funktionen mit rekursiv aufzählbarem Urbild |
Funktionen sind von [mm] \IN [/mm] nach [mm] \IN
[/mm]
Ich vermute es handelt sich um partiell berechenbare Funktionen.
Weiß jemand wie es für alle Funktionen aussieht
Urbild=Teilmenge aller [mm] \IN [/mm] für die die Funktion definiert ist.
Meine Idee: Die zweite ist unentscheidbar, da man damit die Menge aller berechenbare Funktionen rekursiv aufzählen könnte, die nach endlich vielen Schritte terminieren (bzgl. entsprechender Turingmaschine) und damit das HAlteproblem lösbar ist
Die erste könnte nach dem Satz von Rice unentscheidbar sein. Weiß aber nicht wie ich beweisen kann das die Menge Funktionen respektiert.
Bräuchte dringend Hilfe. Danke!
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 17:04 Di 19.02.2008 | | Autor: | Gilga |
Die erste habe ich rausbekommen. Was haltet ihr von meiner Lösung von der 2.?
Menge aller berechenbaren Funktionen mit rekursiv aufzählbarem Urbild:
Urbild rekursiv aufzählbar gdw. Funktion nicht überall undefiniert (Duff-tailing)
=> Nicht rekursiv da nicht überall undefiniert trivilaerweise nicht berechenbar.
=> aber rekursiv aufzählbar mit duff-tailing in 3 Dim.
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 15:07 Do 21.02.2008 | | Autor: | freki |
> Sind folgende Mengen rekursiv?:
>
>
> Menge aller Funktionen mit endlichem Urbild (1)
> Menge aller Funktionen mit rekursiv aufzählbarem Urbild (2)
(1) Alle endlichen Mengen sind rekursiv, also ist jede Funktion mit endlichem Urbild (total) berechenbar, also ist die Menge (1) eine Teilmenge der total-berechenbaren Funktionen. Vielleicht hilft hier, dass die Menge der totalen Funktionen nicht nummerierbar, also nicht einmal aufzählbar ist.
(2) ist genau die Menge aller (partiell) berechenbaren Funktionen (Abschlusseigenschaft). Diese ist rekursiv-aufzählbar, aber nicht rekursiv. Möglicher Ansatz: Eine berechenbare Funktion [mm] \phi [/mm] (Standardnummerierung), deren Bild die Menge (2) ist.
Dies mal als möglichen Ansatz in den Raum geworfen - bin mir aber nicht ganz sicher. Wenn's nicht eh schon zu spät ist.
|
|
|
| |
|
| Status: |
(Frage) überfällig  | | Datum: | 16:30 Do 21.02.2008 | | Autor: | Gilga |
1) Nein. Endliches Urbild heißt dass die Funktion an allen ausser endlich vielen Stellen undef. ist. Also keine totalen Funktionen enthält.
Nach dem Satz von Rice Var. 1 ist die Menge nicht rekursiv aufzählbar.
2) Nach Def. heißt rekursiv aufzählbar dass die Menge Im Bild einer totalen berechenbaren Funktion liegt. Ist die Funktion aber überall undef. so kann sie nicht rekursiv aufzählbar sein. Sie ist dann aber partiell berechenbar.
PS: Prüfung war heute. Ich mag das Themengebiet.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 17:21 Sa 23.02.2008 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
