Berechenbarkeit

Berechenbarkeit





Allgemeines:


Die erste Übungsstunde findet am 10.10. statt.
Die Übungsstunde am 17.10.03 findet wie üblich statt!


Stundentausch:
Freitag, 7.11.03, 13:00: (statt Übung) Vorlesung
Montag, 10.11.03, 13 h: (statt Vorlesung) Übung.

Mittwoch, 12.11.03, 10 h: Vorlesung Berechenbarkeit (statt Datenbanken)
Montag, 17.11.03, 13 h, und Freitag, 21.11.03, 13 h: Vorlesung Datenbanken (statt Berechenbarkeit V/ Ü)
Montag, 24.11.03, 13 h: (statt Vorlesung Berechenbarkeit) Übung Berechenbarkeit

(Räume jeweils wie für die ursprünglich vorgesehene Veranstaltung)





Material zur Vorlesung:


Hier finden Sie künftig die in der Vorlesung verwendeten Folien und ggf. weiteres Material. Siehe auch Literatur.
 
 
Folien 1 - 5 (oder: 1/Seite ) Definitionen Abschnitt 2.1 (Version 1.0.2)
Folien 6-8 (oder: 1/Seite ) Folien 9-11 (oder: 1/Seite )
Folien 12-18 (oder: 1/Seite )












Übungsblätter:



 
Übungsblatt 1 Übungsblatt 2 Übungsblatt 3 Übungsblatt 4
Übungsblatt 5 Übungsblatt 6 Übungsblatt 7/8 Übungsblatt 9
Übungsblatt 10 Übungsblatt 11  












Literatur:


  1. W. Pohlers. Mathematische Grundlagen der Informatik. Handbuch der Informatik Band 1.5. Oldenbourg Verlag 1993.
  2. U. Schöning. Theoretische Informatik - kurzgefaßt. Spektrum Akademischer Verlag, 3. Auflage 1997.

Weitere Literatur wird in der Vorlesung angegeben.





Kurzbeschreibung:


Gegenstand der Vorlesung sind Präzisierungen des Begriffs der "berechenbaren'' Funktionen, der Nachweis der Äquivalenz verschiedener Ansätze hierzu und die Untersuchung der dadurch festgelegten Klasse der (partiell) rekursiven Funktionen.

Inhalte sind insbesondere:
  • abstrakte Maschinen allgemein, speziell Turingmaschinen und Registermaschinen
  • LOOP- und WHILE-Berechenbarkeit
  • Definitionsprinzipien: primitive Rekursion, beschränkte Minimierung, unbeschränkter Suchoperator
  • primitiv rekursive, rekursive, partiell rekursive Funktionen; rekursive und rekursiv aufzählbare Mengen
  • Kleenes Normalformtheorem, universelle Funktionen, Rekursionstheorem, Satz von Rice
  • kurze Einführung in die Komplexitätstheorie





Links:


Nachfolgende Seiten passen zum Thema. Es handelt sich durchwegs um ergänzendes bzw. Hintergrundmaterial, das von Dritten bereitgestellt wird, und nicht um einen Bestandteil der Vorlesung.
Insbesondere wird selbstverständlich keinerlei Verantwortung für den Inhalt übernommen!
The MacTutor History of Mathematics archive (siehe Gödel, Church, Turing, Kleene, ...)
Die Pi-Seite
Mehr über fleißige Biber findet man hier oder hier.
Die "Stanford Encyclopedia of Philosophy" enthält einen Eintrag über Turingmaschinen mit Links auf Simulatoren;

hier ein weiterer Simulator mit vorbereiteten fleißigen Bibern




Weitere Informationen zu Lehrveranstaltungen unseres Instituts

Institut für Theoretische Informatik und Mathematik 


Birgit Elbl