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
