1. Skip to Menu
  2. Skip to Content
  3. Skip to Footer

Logik und Berechenbarkeit: Rekursive Funktionen und Turing-Maschinen

Im Sommersemester 2011 wird am Lehrstuhl für Logik und Sprachphilosophie folgende Veranstaltung als BA-Seminar in der formalen Logik angeboten (Termin jeden Donnerstag, 12-14h, Raum 028, Ludwigstr. 31), Teilnahme auch für MA-Studenten möglich:

Logik und Berechenbarkeit: Rekursive Funktionen und Turing-Maschinen (Dozent: Roland Poellinger)

Ausgehend von formalen Sprachen und deren Behandlung in der Automatentheorie befasst sich das Seminar mit der Theorie der Berechenbarkeit (elementare Theorie der "rekursiven Funktionen") und gibt Ausblick auf weitere Anwendungen in der Logik und Philosophie.

Einzelne Themen

  1. Reguläre Sprachen
  2. Endliche Automaten
  3. Chomsky-Hierarchie
  4. Abzählbarkeit, Diagonalisierung
  5. Turing-Maschinen und Turing-Berechenbarkeit
  6. Implementierung von Turing-Maschinen
  7. Abacus-Maschinen
  8. Primitiv-rekursive und mü-rekursive Funktionen
  9. Äquivalenz von mü-Rekursivität und Turing-Berechenbarkeit
  10. Grenzen der Berechenbarkeit: Busy-Beaver-Problem, Halteproblem, Postsches Korrespondenzproblem

Literatur

[1] Barwise, J. und J. Etchemendy (1993), Turing's World 3.0: An Introduction to Computability Theory (Center for the Study of Language and Information - Lecture Notes), Cambrigde: CUP.

[2] Boolos, G., J. Burgess und R. Jeffrey (1980), Computability and Logic, 4th/5th ed.,

Cambridge: CUP.

[3] Hofstaedter, D. (1980), Gödel, Escher, Bach. Penguin. (Auch auf Deutsch)

[4] Kapitel "Rekursive Funktionen" in: Link, G., Collegium Logicum - Logische Grundlagen der Philosophie und der Wissenschaften. (Dieses Kapitel liegt nicht in Druck vor und wird zu Beginn der Veranstaltung zu Verfügung stehen)

Schein

Ein Leistungsnachweis kann erzielt werden mit einer Kurzpräsentation und der Bearbeitung eines Übungsblattes

Semester-Übungsblatt

Die Bearbeitung des Übungsblattes ist bis zum 11. August 2011 (12:00 Uhr) im Sekretariat MCMP (Frau Pöhlmann) einzureichen bzw. digital an r.poellinger [at] lmu.de. Download der Angabe hier.

Voraussetzungen

Vorkenntnisse bzgl. klassischer Prädikatenlogik (z.B. im Umfang des "Collegium Logicum") sind hilfreich und wünschenswert, aber nicht erforderlich

Downloads

Zusätzliche Dokumente und Dateien können hier heruntergeladen werden. Das Passwort wird in der Veranstaltung ausgegeben. Für Link (Kap. 1-12) und Boolos/Burgess/Jeffrey (3. ed.) siehe Handapparat in der Bibliothek Theologie/Philosophie.