Seite 1 von 1

Fragen zum Skript und Übungen

Verfasst: 9. Aug 2007 15:57
von kechler
Hallo zusammen,

ich habe mal ein paar Fragen bezüglich des Skripts und den Übungen gesammelt, auf die ich bisher leider keine Antwort finden konnte:

Skript:
1.) S. 62: Wieso darf die step-Funktion nicht gleich 0 sein bzw. warum gilt b > step > 0, obwohl step(0, Mp, STA) = 0 definiert ist? Ist auch wichtig für den Beweis von Satz 11.39.

2.) S. 72: Warum muss man noch [[ENUMERATE_M]](N) = M zeigen? Reicht es nicht aus, dass [[ENUMERATE_M]](N) Teilmenge von M ist?

3.) S. 87: Was bedeutet die 1 bei CYCLE? Dasselbe kommt auch nochmal bei Übung 5.4c) vor.

4.) S. 94: Aus welchem Grund ist "plus'" nicht primitiv-rekusriv definiert?

5.) S. 124: Wie genau müssen wir den Beweis von Satz 11.39 reproduzieren können?

Übungen:
1.) 1. Übung:
- Aufgabe 1.3,f: Kann man hier auch schlussfolgern, dass eine Funktion berechenbar ist, obwohl man einen Algorithmus angeben kann, der unter Umständen nicht berechenbar ist?

2.) 1. Hausübung:
- Aufgabe 1.4,d: Wieso ist hier keine Fallunterscheidung angebracht:
1. Fall: g(n) != 0 -> f4 berechenbar
2. Fall: g(n) = 0 -> f4 nicht berechenbar, da h(n) unbekannt ist?

3.) 6. Übung:
- Aufgabe 6.3, e: Müsste im Lösungsvorschlag nicht exp'(0, x) = C^1_1(x) ergeben? Da x^0 = 1 ist?

Allgemeine Verständnisfragen:
1.) Was ist der Unterschied zwischen der self-Funktion (S. 47, Selbstanwendbarkeitsfunktion) und der S-Funktion (S. 53, Selbstanwendbarkeitsproblem)?

2.) Was ist genau der Unterschied zwischen primitiver Rekursion (Def. 11.3) und struktureller Rekursion (Satz 11.7)?

3.) Müssen wir in der Klausur benutze Sätze mit den entsprchenden Nummern angeben? Bsp.: Können wir einfach so sagen, dass jede primitiv-rekursive Funktion total ist oder müssen wir dazu noch Satz 11.24 angeben? Entsprechend mehr wäre hier der Lernaufwand...

4.) Könnte mir jemand nochmal genau die "Diagonalisierung" erklären? Wann und wie benutze ich dieses Beweisschema? Ich konnte da leider keine Verallgemeinerung ausmachen und auch der Einsatz erschien mir eher willkürlich?

Ich hoffe, dass es nicht allzu viel Fragen auf einmal sind und bin für jeden Lösungsvorschlag oder auch Kritik sehr dankbar!

Verfasst: 10. Aug 2007 15:29
von AhGuGu
Hi,

okay, dann will ich mal ein bisschen was dazu schreiben:

Skript:
zu 1.): Ich verstehe nicht genau was du meinst. Allerdings ahne ich es: Das b (die Schrittvorgabe) kann beliebig sein. Deswegen fordern wir, dass b nach Ausführung echt größer als 0 sein muss. Und zwar damit wir unterscheiden können, ob es "gerade so" gereicht hat, oder ob die Schrittzahl nicht gereicht hat.

zu 2.): Zu zeigen, dass es bloß eine Teilmenge ist reicht einfach nicht aus. Rekursive Aufzählbarkeit bedeutet ja, dass es eine Abbildung gibt, die surjektiv ist. D.h. das Semi-Entscheidungsverfahren muss für jedes Element mit einer positiven Antwort anhalten. Vgl. Semi-Entscheidungsverfahren für die Menge 1 gegenüber den natürlichen Zahlen.

zu 3.): Schau dir mal die Definition von CYCLE auf Seite 24 an. Dort wird CYCLE ganz allgemein mit k Parametern definiert. Ich nehme an, man übergibt dort den Parameter, damit er nicht ganz "nutzlos" ist. Allerdings muss man das nicht machen.
Vorsicht: Wenn man streng nach der Definition bei den primitiv-rekursiven Funktionen geht, darf man u. U. nur Funktionen mit derselben Parameteranzahl aufrufen. Evtl. spielt so eine Überlegung da auch rein.

zu 4.): Bei der primitiven Rekursion darf der nur der erste Parameter verändert werden. Die nächsten Parameter müssen unverändert übergeben werden. Dort wird aber mittels S(x) der Parameter verändert.

zu 5.): Ich denke nicht, dass wir den Beweis reproduzieren müssen. Die Aussagen von den meisten Sätzen sind das relevante. Bei manchen Beweisen tauchen noch "nette" Verfahren auf (z.B. Diagonalisierung). Aber das war ja soweit ich mich erinnere nichts Wildes. Es war "nur" viel und anstrengend wegen der geschachtelten Induktionsbeweise.

Übungen:
zu 1.): Nein. Der Algorithmus muss natürlich berechenbar sein. Allerdings kann es sein, dass wir im Moment nicht wissen, welchen "Teil" des Algorithmuses wir verwenden müssen. Beispiel aus der Vorlesung von Prof. Walther: Das Halteproblem ist berechenbar: Algorithmus ist ganz einfach; 1 wenn ein Programm Entscheidbar ist, 0 wenn es nicht Entscheidbar ist. Das ist eine ähnliche Argumentation wie in manchen Beweisen: "Wir wissen, dass ein Programm das gewünschte leistet, allerdings nicht genau welches".

zu 2.): Bis eben stand das noch auf meinem Zettel mit zu klärenden Fragen drauf. Aber jetzt ist es mir eingefallen:
g(n) + h(n) = 0 kann nur gelten, wenn g(n) = 0 und h(n) = 0 ist. Lassen wir h(n) mal außen vor: Dann wird 0 zurückgegeben, wenn g(n) = 0 gilt und sonst g(n). Damit erübrigt sich die Fallunterscheidung doch und wir brauchen uns über h(n) einfach keine Gedanken mehr zu machen.

zu 3.): Ja, ich denke, da hast du Recht.

Allgemeine Verständnisfragen:
zu 1.): Naja, einmal ist von einer bestimmten Funktion die Rede. Und einmal wird ein Problem in Form der Zugehörigkeit einer Menge definiert. Lies dir doch kurz die Einleitung von Abschnitt 7.1 nochmal durch. Oder habe ich dir hier falsch verstanden?

zu 2.): Schau dir doch mal die Beispielprogramme an, die jeweils dazu angegeben wurden. Letzten Endes gewinnst du aber nichts an Funktionalität hinzu. Denn im Satz 11.7 steht ja dran, dass strukturelle Rekursion durch primitive Rekursion u. a. dargestellt werden kann. Ich würde fast so weit gehen und es in die Kategorie "syntactical sugar" einordnen.

zu 3.): Würde mich auch interessieren. Ich denke, da wird aber auf von offizieller Seite noch eine verbindliche Antwort kommen.

zu 4.): Wie mit allen Beweisenschemata wird es keine befriedigende Antwort für dich geben, die genau definiert wann du dieses oder jenes anwenden solltest. Getreu dem Motto "Viele Wege führen nach Rom." Hast du eine konkrete Frage dazu?

So, jetzt habe ich zu allem meinen Senf dazugegeben. Hoffe, es hilft dir ein klein wenig weiter und vor allem hoffe ich, dass ich hier keinen allzugroßen Blödsinn verzapft habe. ;)

Weiterhin viel Erfolg beim Lernen.

gruß Ahgugu

Verfasst: 10. Aug 2007 17:17
von Simon Siegler
Fragen zum Skript:
  1. Natürlich darf die Step-Funktion 0 sein, nämlich genau dann, wenn die gegebene Beschränkung nicht zur vollständigen Abarbeitung ausreicht.
  2. Zu zeigen ist insgesamt, dass M rekursiv aufzählbar ist. Dazu reicht es nicht aus, nur ein Aufzählverfahren für eine Teilmenge von M anzugeben. Ansonsten wäre ja jede Menge rekursiv aufzählbar, da die leere Menge rekursiv aufzählbar ist.
  3. Die Programme \(\mathtt{CYCLE}_k\) sind wie beschrieben auf Seite 24 definiert. Zu beachten ist, dass durch das Schema für jede natürliche Zahl k genau ein Programm definiert wird, das für genau k Argumente die überall undefinierten Funktion \(\omega_{\mathbb{N}^k\rightarrow\mathbb{N}\) berechnet (siehe auch Satz 3.2).

    Auf Seite 87 wird mit \(\mathtt{CYCLE}_1\) eines dieser abzählbar vielen Programme verwendet.
  4. Wie auf Seite 94 beschrieben erfüllt die Definition von plus' nicht die Forderungen aus Definition 11.4. Im Beispiel wird im rekursiven Fall das zweite Argument verändet, während das starre Schema der primitiven Rekursion nur eine Änderung des ersten Arguments zulässt.

    Das Beispiel soll vor allem verdeutlichen, wie starr dieses Schema ist. In den folgenden Definitionen werden dann wesentlich flexiblere Definitionsschemata beschrieben, mit denen man die gleiche Menge von Funktionen definieren kann.
  5. Sie sollten den Beweis verstanden haben. Prinzipiell sollten Sie in der Lage sein, einen Beweis durch strukturelle Induktion über Programmanweisungen oder Ausdrücke zu führen. Doch einen Beweis "nur" reproduzieren zu können zählt nicht zu den Zielen der Veranstaltung.
Fragen zur Übung
  1. Der Begriff der Berechenbarkeit ist für Funktionen definiert, nicht für Algorithmen. Ein Algorihmus ist ein Berechnungsverfahren. Zu jeder berechenbaren Funktion gibt es (mindestens einen) Algorithmus, zu einer nicht berechenbaren kann es keinen geben.
  2. Eine Fallunterscheidung bezüglich "g(n)=0" ist unnötig, denn wie Ihr Kommilitone bereits beschrieben hat und auch im Lösungsvorschlag steht, impliziert "g(n) + h(n) = 0" bereits "g(n)=0" und somit ist die Funktion gleich g.

    Im Fall "g(n)=0" folgt eben auch die Berechenbarkeit: Ist "h(n)=0", so ist "f(n) = 0 =g(n)". Ansonsten muss "h(n)!=0" sein, damit ist "f(n)=g(n)"
  3. Da haben Sie Recht, da hat jemand beim Editieren der Kopie von times nicht aufgepasst ;)
Allgemeine Fragen
  1. Die Selbstanwendungsfunktion self gibt an, ob das durch die gegebene Zahl kodierte Programm angewendet auf eben diese Zahl terminiert.

    Das Problem S auf Seite 54 ist die Menge aller Programme, die angewendet auf ihren eigenen Kode terminieren. Damit ist self gerade die charakteristische Funktion dieser Menge.
  2. Das Schema der strukturellen Induktion ist weniger eingeschränkt als das der primitiven Rekursion. Um dem strengen Schema der primitiven Rekursion zu genügen, sind zahlreiche Hilfsfunktionen nötig, im Reihenfolge oder Anzahl von Parametern anzupassen u.ä. In den Übungen gab es einige Aufgaben, in denen das strikte Schema einzuhalten war. Meist erfüllte die gegebene Definition bereits das Schema der strukturellen Induktion.
  3. Die Satznummern auswendig zu lernen ist kein Lernziel der Veranstaltung. Bei den benannten Sätzen ist es mitunter praktischer, in der Klausur den Namen anzugeben als den Inhalt des Satzes wiederzugeben, doch auch das soll nicht verpflichten sein.
  4. Schauen Sie sich die Übungen, die alten Klausuren zu "Grundlagen der Informatik IV" sowie die Vordiplome "Informatik C" an, so können Sie vielleicht eine Heuristik für die Verwendung des Diagonalisierungsverfahrens ableiten.
    Generell ist das Verfahren geeignet, um die Unvollständigkeit einer Aufzählung zu zeigen.