Berechenbarkeit FT06

Vorlesung Berechenbarkeit - FT06


Die Vorlesung Berechenbarkeit im Wintertrimester 2006 wird von Prof. Dr. Peter Hertling gehalten und findet zu den folgenden Zeiten statt:

Mo. 13.00 - 15.00 Uhr, Hörsaal 1201
Do. 11.00 - 12.00 Uhr, Hörsaal 0301

Achtung! Die Zeiten der Vorlesung und der Übung am Montag haben sich geändert!

Zur Vorlesung wird ein Skript erstellt. Dieses wird jeweils kurz vor oder nach der Vorlesung auf dem Dokumentenserver der Universität der Bundeswehr München bereitgestellt, und zwar hier:

Dokumente zur Berechenbarkeit
Auf dem Dokumentenserver werden auch die Übungsblätter bereitgestellt.

An dem Skript auf dem Dokumentenserver sind nach dem ersten Ins-Netz-Stellen an den folgenden Tagen die folgenden Korrekturen und Änderungen vorgenommen worden:
  • 24.04.2006:
    • Abschnitt 1.3, drei Zeilen vor Lemma 1.12: Das Wort "berechenbar" musste durch "LOOP-berechenbar" ersetzt werden.
    • Abschnitt 1.4, vier Zeilen vor Lemma 1.18: Das Wort "Wie" musste ersetzt werden durch "Wir". Der Satz in den Zeilen 5 bis 7 des Beweises von Lemma 1.18 enthielt einen Tippfehler und musste etwas verschärft werden.
    • Abschnitt 1.5, Zeile 7 (ohne die Überschrift): Statt "sind" musste es heißen "sein". Definition 1.21: In der Definition der nullstelligen Nullfunktion wurde ein Gleichheitszeichen durch ":=" ersetzt. Drei Zeilen nach Definition 1.22 fehlte in einer Formel eine schließende Klammer. In Beispiel 1.25.4 war die Funktion add einmal versehentlich kursiv geschrieben worden. Die in Lemma 1.28.2 definierten Umkehrfunktionen $\pi^{(2)}_i$ waren falsch definiert worden: statt $\pi^{(2)}$ musste zuerst die Umkehrung $(\pi^{(2)})^{-1}$ angewendet werden.
    • Abschnitt 1.6. In den beiden Zeilen vor Bemerkung 1.34 musste zweimal f durch g ersetzt werden. Tippfehler in Definition 1.35: Statt "der primitive Rekursion" heißt es "der primitiven Rekursion". Im Beweis von Satz 1.37 sollte in der viertletzten Zeile des Beweises der zuerst bewiesenen Richtung nicht "WHILE-Programm für Q", sondern "WHILE-Programm für g" stehen. In der Zeile der Hilfsbehauptung einige Zeilen später sollte es nicht "Variablen in p", sondern "Variablen in P" heißen.
  • 15.05.2006: In Definition 1.16 gab es einen Tippfehler in der Bezeichnung der neu definierten Funktion f_P,k.
  • 18.05.2006: In Definition 1.53 ist bei der Definition der Übergangsfunktion "möglicherweise partielle" durch "(möglicherweise nicht totale)" ersetzt worden. In Beispiel 1.57 musste hinter "Sobald er auf eine 0 trifft, ersetzt er sie" ergänzt werden: "durch eine 1". In Übung 1.58 ist die Funktion equal natürlich eine zweistellige Funktion. In Zeile 8 des Beweises von Satz 1.60 muss M' stehen, nicht M. Elf Zeilen tiefer musste "ungeraden Spur" durch "geraden Spur" ersetzt werden, da Sterne nur auf geraden Spuren stehen. Im Beweis von Satz 1.62 musste der Satz vor der Behandlung der Anweisung "x_i:=S(x:i)" korrigiert werden. Außerdem wurde bei der Behandlung dieser Anweisung und am Schluss des Beweises jeweils ein erläuternder Satz eingefügt. Bei der Behandlung der bedingten Sprunganweisung oben auf Seite 42 fehlte die Sprungmarke j. Im Beweis von Satz 1.63 wird jetzt angenommen, dass das Alphabet Gamma die Elemente von 0 bis |Gamma|-1 hat statt wie bisher von 1 bis |Gamma|. Entsprechend wurde das Programmstück zur Simulation des Verhaltens im Zustand q auf der nächsten Seite korrigiert. Zwei Zeilen weiter fehlte einmal das Wort "man". Auf Seite 44 wurde nach der Definition der Menge P^(k) und R^(k) ein erläuternder Satz eingefügt. Schließlich wurde sechs Zeilen vor Ende des Abschnitt 1.9 noch ein Tippfehler korrigiert.
  • 22.05.2006: Am Ende des Beweises von Satz 1.68 muss es "...=1]" heißen, nicht "...=0]". Im zweiten Teil von Definition 1.70, in der dritten Bedingung von Satz 1.71 und in der Bedingung 3' in der vierten Zeile des Beweises von Satz 1.71 musste jeweils pi^(k) durch pi^(k)^{-1} ersetzt werden.
  • 29.05.2006: Zwei Zeilen nach Def. 1.64 ist ein überflüssiges Wort "gibt" entfernt worden. Im Schluss von 1 auf 3' im Beweis von Satz 1.71 ist der Einheitlichkeit der Notation wegen der Funktionsbezeichner f durch g ersetzt worden. In Bemerkung 1.72 ist ein überflüssiger Bindestrich entfernt worden.
  • 01.06.2006: Im Beweis von Satz 1.85 musste das Sprungziel in der ersten Anweisung im GOTO-Programm gleich 5 sein, nicht gleich 4. Entsprechend musste auch die Gödelnummer des Programms korrigiert werden.
  • 08.06.2006: Das in Definition 1.94 definierte Halteproblem wird mit H_\phi abgekürzt, nicht mit K_\phi.
  • 19.0.2006: In der Erläuterung zu Schritt 7 im Algorithmus im Beweis von Satzu 1.83 musste eine 3 durch eine 4 ersetzt werden. Am Anfang des Beweises der ersten Aussage in Satz 1.102 ist eine Formulierung etwas geändert worden.

  • Übungen


    Die Übungen werden von Herrn Dr. Christoph Spandl betreut. Termin und Raum:

    Mo. 15.00 - 16.00 Uhr, Hörsaal 1201


    Letzte Änderung: 19. Juni 2006