| 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, M3 |
| Beginn: |
Die erste Vorlesung findet am 16.10. statt;
der Übungsbetrieb startet am 25.10;
das Tutorium findet erstmals am 23.10 statt. |
| Belegnummern: |
Vorlesung: 104.184, Übungen: 104.218 |
| 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)
(als .ps Datei hier)
- H. Rogers Jr.: Theory of recursive functions and effective computability, MacGraw Hill (1967) |
| Übungen: |
Mittwoch 8-10 M3 bei Dominik Adolf, BK 89
Mittwoch 10-12 M2 bei Malte Kließ, BK 88
Mittwoch 12-14 M3 bei Arthur Penkala, BK 86
Mittwoch 14-16 M3 bei Marek Wyszkowski, BK 87
Freitag 10-12, SR 1, bei Arthur Penkala, BK 86 und
Freitag 14-16, SR 8, bei Mathias Meczele, BK F60. |
| Tutorium: |
Das Tutorium findet montags 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.
|
| Scheine: |
Die Scheine können bei Frau Pfeifer in Raum 811 abgeholt werden. |
| Rückgabe der Nachklausur: |
Die Nachklausur wird am Mittwoch, den 4.4. um 15 Uhr c.t. im M1 zurückgegeben. |
| Bei Problemen: |
Sprechen Sie die Veranstalter an oder schicken Sie eine Email an
Christoph Heinatsch. |
