Empfehlenswerte Bücher

• J. Hopcroft, R. Motwani, J. Ullman: Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie. Pearson 2002 Dieses Buch bildet den Leittext für diese Veranstaltung. Manche Themen werden alledings etwas zu vereinfacht dargestellt. Es gibt eine ätere Version des Buches im Oldenbourg Verlag, in dem die Themen deutlich knapper, aus unserer Sicht aber auch klarer abgehandelt werden. Dafür fehlen einige modernere Ergebnisse.
• G. Vossen, K.-U. Witt: Grundkurs Theoretische Informatik. 3. Auflage, Vieweg 2004 Einige Themen der abstrakten Berechenbarkeitstheorie werden in diesem Buch sehr gut abgehandelt.
• Michael Sipser: Introduction to the Theory of Computation. 2. Auflage, PWS 2005 Aus Sicht eines Theoretikers eine der besten Einführungen in die theoretische Informatik. Es verwendet in der abstrakten Berechenbarkeitstheorie allerdings eine Notation, die unserer Erfahrung nach nicht sehr intuitiv ist. Leider ist es in Deutschland recht teuer, aber vielleicht gebraucht zu bekommen (die erste Auflage von 1997 ist übrigens fast identisch).
• Folien der Vorlesung.

Auch lesenswert:

• P. Leypold: Schneller Studieren. Pearson 2005 Lesenswertes zur Selbstorganisation im Informatikstudium
• K.-U. Witt: Vorkurs Mathematik. Fachhochschule Bonn-Rhein-Sieg 2004
• John Martin: Introduction to Languages and the Theory of Computation. 3. Auflage, McGraw-Hill 2002 Ein gutes Buch, das alle Standardthemen abdeckt.
• A. Asteroth, C. Baier: Theoretische Informatik. Pearson 2002
• H. Ehrig: Mathematisch-strukturelle Grundlagen der Informatik. Springer 2001
• I. Wegener: Theoretische Informatik. Teubner Verlag 1993
• Uwe Schöning: Theoretische Informatik - kurzgefasst. 4. Auflage, Spektrum Akademischer Verlag 2001 Eine knappe, aber angenehm zu lesende Einführung in die theoretische Informatik.
• K. Erk, L. Priese: Theoretische Informatik. Springer 2000
• H. Lewis, C. Papadimitriou: Elements of the Theory of Computation. Prentice-Hall 1998
• K. Weihrauch: Computability. Springer Verlag 1987 Technisch etwas anspruchsvoll, aber eines der wenigen Bücher mit einem Kapitel zu rekursiven Funktionen

Weitere Materialien zur Vorlesung

• Die Unentscheidbarkeit extensionaler Eigenschaften von Turingmaschinen — der Satz von Rice Ein Einführungstext zur funktionalen Reduktion von Sprachen und zum Satz von Rice.
• Grundbegriffe der Graphentheorie: Ein kurzer Handout fasst die wesentlichen Begriffe in der Notation zusammen, die in der Vorlesung verwendet wird.

Referenzen zu Rekursiven Funktionen

• Es gibt eine Reihe guter Skripten im Web, z.B. an den Universitäten Hamburg (HAW), Erlangen. Weitere Skripten kann man durch Goodle Suche finden.

Referenzen zum Lambda-Kalkül

Im Folgenden finden Sie einige von uns empfohlene Referenzen zu diesem Thema:

• Introduction to Functional Programming (John Harrison) Ein sehr guter Kurs zur funktionalen Programmierung, der auch eine Einführung in den Lambda-Kalkül umfasst. Für die Vorlesung sind die Kapitel 2 (Lambda calculus) und 3 (Lambda calculus as a programming language) relevant.
• Einführung in den Lambda-Kalkül (André Metzner) Ein guter Einführungstext in den Lambda-Kalkül, der alle Themen behandelt, die Sie über den Lambda-Kalkül wissen sollten (und noch etwas mehr). Für die Vorlesung spielt nur der Abschnitt über untypisierte Lambda-Kalküle eine Rolle.
• Das gefürchtete Lambda-Kalkül (Fabian Nilius) Eine Einführung in den Lambda-Kalkül in Form eines Vortrags. Der Y-Kombinator wird recht gut erklärt. Allerdings enthält der Text ein paar kleinere Fehler und einige Details kommen etwas zu kurz.
• Zwei Wikipedia Artikel zu Fixpunktkombinatoren und zum Lambda-Kalkül sind ebenfalls lesenswert.
• Auszug aus einem Skript einer weiterführenden Veranstaltung, die den Lambda-Kalkül etwas umfangreicher behandelt.
• Hier ist ein (komprimiertes tar file) Tool, das die Auswertung von Lambda-Ausdruecken schrittweise animiert. Es wurde im Rahmen eines TI Projektes entwickelt und funktioniert in Windows und Linux. Eine kurze Anleitung liegt bei.

Referenzen zum Arithmetischen Repräsentierbarkeit

• George S. Boolos, John P. Burgess & Richard C. Jeffrey: Computability and Logic (Kapitel 14). 4th edition, Cambridge University Press 2002
• Notizen einer Lehrveranstaltung zur Angewandten Logik an der Cornell University.
  Axiomatizing Integer Arithmetic, Arithmetic Representability
  Unsolvable Problems in Logic, The theory Q and the undecidability of logic

Lesenswertes zur Arbeitsethik

• Code of Academic Integrity (Cornell University)
• Missverständnisse zum Urheberrecht