| Veranstalter: |
Prof. Dr. Wolfram Pohlers, Zi. 810 (Sekretariat Frau Pfeifer, Zi. 811),
Christoph Heinatsch, Zi. 812, Tel. 83-33766 |
| Zeit und Ort der Vorlesung: |
Montag und Donnerstag 14-16 Uhr, M4 |
| Beginn: |
Die erste Vorlesung findet am 15.10. statt;
der Übungsbetrieb startet am 24.10.
|
| Belegnummern: |
Vorlesung: 104.171, Übungen: 104.190 |
| Inhalt: |
Die Vorlesung gibt eine Einführung in die Theorie der
Berechenbarkeit und der Prädikatenlogik der ersten Stufe. Beginnend
mit einem abstrakten Maschinenmodell entwickeln wir die Theorie der
Berechenbarkeit bis zum Satz von Rice, zu dessen Konsequenzen die
Unmöglichkeit einer generellen automatischen Verifikation von
Programmen gehört. Wir wenden dann die entwickelte Theorie auf formale
Sprachen an und studieren die Chomsky-Hierarchie. Im letzten Teil
befassen wir uns mit der Prädikatenlogik und zeigen, dass jeder
beweisbare Satz bereits formal beweisbar ist. Mit den erarbeiteten
Mitteln der Berechenbarkeitstheorie zeigen wir dann, dass die formale
Beweisbarkeit von Sätzen jedoch nicht durch einen Algorithmus
entschieden werden kann. |
| Literatur: |
- Skript zur Vorlesung als pdf-Datei oder ps-Datei
- H. Enderton: A mathematical introduction to logic, Academic Press (2001)
- T. Glaß; W. Pohlers: An introduction to mathematical logic, Münster, Skript (1992)
- H. Rogers Jr.: Theory of recursive functions and effective computability, MacGraw Hill (1967) |
| Übungen: |
Mittwoch 8-10 SR8 bei Irene Thesing, BK 91,
Mittwoch 10-12 SR8 bei Dominik Adolf, BK 176,
Mittwoch 10-12 702 bei Malte Kließ, BK 177,
Mittwoch 12-14 M6 bei Jan-Carl Stegert, BK 178,
Mittwoch 14-16 SR8 bei Jan-Carl Stegert, BK 178 und
Mittwoch 16-18 SR 8 bei Tobias Förster, BK 179. |
| Tutorium: |
Das Tutorium findet dienstags um 18 Uhr im M4 statt. |
| Leistungsnachweis: |
Einen Leistungsnachweis erhält man nach Bestehen der Abschlussklausur. |
| Aufgaben: |
Die Aufgaben werden jeweils montags in der Vorlesung ausgegeben, die Lösungen können
dann bis zum folgenden Montag, 14:15 Uhr abgegeben werden.
|
| Klausurrückgabe: |
Die Klausuren können im Sekretariat (Raum 811) abgeholt bzw. eingesehen werden. |
| Rückgabe der Nachklausur: |
Die Nachklausur kann ab Mittwoch, den 16.4. im Sekretariat (Raum 811) eingesehen bzw. abgeholt werden. |
| Bei Problemen: |
Sprechen Sie die Veranstalter an oder schicken Sie eine Email an
Christoph Heinatsch. |
