Loesung Uebung 4

jak
Windoof-User
Windoof-User
Beiträge: 30
Registriert: 11. Nov 2004 15:42
Kontaktdaten:

Loesung Uebung 4

Beitrag von jak » 1. Mai 2008 12:32

Hier noch ein paar Ausfuehrungen zur Loseung der Aufgabe 1 auf Blatt 4 (das Quiz):

1. Jede totale Funktion ist berechenbar.
Falsch, die charakteristische Funktion des Selbstanwendungsproblems ist total aber nicht berechenbar. Man beachte, dass phi_n als ueberall undefinierte Funktion definiert ist falls das "n" kein gueltiges P-Programm darstellt.

2. Jede berechenbare Funktion ist total.
Falsch, Cycle ist nirgendwo definiert, ist aber berechenbar.

3. Jede Funktion mit endlichem Denitionsbereich ist berechenbar .
Richtig, man kann die Funktion durch eine endliche Fallunterscheidung in einem P-Programm darstellen. Hier sollte man vielleicht noch anmerken, dass man nicht unbedingt eine Funktion angeben kann, es aber beweisbar ist, dass sie existieren muss (siehe z.B. im Script das "endliche Halteproblem" H_{10^10} auf Seite 55 unten)

4. Jede Funktion mit endlichem Bildbereich ist berechenbar.
Falsch, die charakteristische Funktion des Selbstanwendungsproblems hat endlichen Bildbereich (entweder 0 oder 1) ist aber nicht berechenbar.

5. Jede Funktion f mit Bild(f) = N ist berechenbar.
Falsch, Beispiel hier waere eine Funktion, die n und n+1 vertauscht falls phi_{floor(n/2)} auf sich selbst angewendet terminiert und die Zahlen sonst unangetastet laesst. Hier laesst sich aus dem Bild leicht ablesen, ob phi_{floor(n/2)} terminiert oder nicht, was aber nicht sein kann, da man sonst das Selbstanwendungsproblem geloest haette. Diese Funktion ist surjektiv da sie ja entweder ein Paerchen vertauscht oder gleich laesst aber keine Zahl unerreicht laesst.

6. Jede Funktion f mit Def (f) = N ist berechenbar.
Falsch, das hier ist die gleiche Aussage wie 1. denn eine Funktion f gilt Def (f) = N genau dann wenn f ist total (per Definition).

7. Jede abzaehlbare Menge ist rek. aufzaehlbar.
Falsch, rek- aufzaehlbar gilt laut Script genau dann wenn semi-etscheidbar, d.h. betrachten wir "S quer" (also das Gegenproblem zum Selbstanwendungsproblem), dann gilt
(1) "S quer" ist abzaehlbar, da hier nur eine Teilmenge der natuerlichen Zahlen drinliegt
(2) "S quer" kann nicht rekursiv aufzaehlbar sein, da es sonst semi-entscheidbar waere und damit waeren dann S und "S quer" semi entscheidbar, also S selbst entscheidbar was aber nicht sein kann.

8. Die Vereinigung von zwei semi-entscheidbaren Mengen ist semi-entscheidbar.
Richtig, ein Semi-entscheidungsverfahren erhaelt man beispielsweise indem man wie im Beweis von Satz 8.7 auf Seite 66 die beiden Semi-entscheidungsverfahren "verzahnt" laufen laesst. Wenn m nun in M1 vereinigt M2 ist, dann ist es also in mindestens einem der beiden Mengen drin, sei das mal M1. Es gilt dann also, dass das Semi-entscheidungsverfahren von M1 terminiert und damit auch die verzahnte Abarbeitung. Ist m nicht in M1 vereinigt M2, so ist es ja in keinem der beiden Probleme enthalten und beide Semi-entscheidungsfunktionen terminieren nicht, also terminiert auch die verzahnte Funktion nicht.

9. Der Schnitt von zwei semi-entscheidbaren Mengen ist semi-entscheidbar.
Richtig, wie in 8.

10. Das Komplement einer semi-entscheidbaren Menge ist semi-entscheidbar.
Falsch, sonst waere ja jedes Problem welches semi-entscheidbar ist auch entscheidbar. Dies ist aber nicht der Fall, denn S oder H sind semi-entscheidbar aber nicht entscheidbar.


noch Fragen? :)

mfg

jak

Zurück zu „Archiv“