Uni Wien:Einführung in die Theorie der Berechenbarkeit SE (Hafner)

Hard Facts

• LV-Nr.: 180394
• Studienprogrammleitung: Philosophie
• Vortragender: Mag. Dr. Johannes Hafner
• Institut: Institut für Philosophie
• ECTS: 5 (SWS: 2)
• Empfohlenes Semester: nach Belieben

Ziel

• Den Begriff der Berechenbarkeit mittels Turingmaschinen und Rekursiven Funktionen explizieren. Es wird die Frage (und der Status der Frage) erörtert, ob der intuitive Berechenbarkeitsbegriff mit den formalen Explikationen deckungsgleich ist.
• (für einen Informatiker)
  

Es spricht für sich, dass ich in diesem Seminar mehr über die theoretischen Grundlagen der Informatik gelernt habe, als bislang in meinen 4 Semestern Informatik. Der Zugang in diesem Seminar ist eher ein mathematisch-logischer (und am Ende auch philosophischer); von daher mehr an Grundlegung interessiert als die Informatik. Der Besuch lohnt auf alle Fälle, da man einen anderen Blickwinkel auf Turingmaschinen, Rekursionen und Algorithmen im Allgemeinen mitbekommt, der für einen Informatiker sehr bereichernd sein kann, um prinzipielle Grenzen seiner Disziplin berücksichtigen zu können.

Themen

• Mengen, Funktionen, Listen
• das (Anti-)Diagonalargument (Diagonalisierung)
• Turingmaschinen und Zustandsdiagramme
  • Busy Beaver / Produktivitätsfunktion
  • Halteproblem
  • Grenzen von Turingmaschinen
• Rekursionen
  • offizielle Notation
  • primitiv rekursive Funktionen
  • allgemein rekursive Funktionen
• Die Church-Turing-These
• Der Satz von Rice

Empfehlenswerte Vorkenntnisse

• Ein wenig Vertrautheit mit mathematischer Terminologie (Definitionen, Funktionen, Mengen, ...) ist ganz hilfreich, jedoch erklärt Prof. Hafner alle Terminologie, die er einführt, verständlich. Man könnte diese LV also durchaus auch schon als Erstsemester-Student besuchen, wenn man bereit ist, zuzuhören.

Ablauf

• Das Seminar fand geblockt ab Ende Mai/Anfang Juni (Fr,Sa) statt
• Den Großteil der Einheiten ist Prof. Hafner damit beschäftigt, die Grundlagen von Diagonalargument, Turingmaschine und Rekursiven Funktionen vorzutragen
• Es werden per Mail Übungsaufgaben verschickt, die bis zur nächsten Einheit zu lösen und freiwillig vorzutragen sind (JedeR sollte mindestens ein Beispiel vorgetragen haben). Die Beispiele werden nicht abgegeben.
• Die letzten 2 Einheiten sind Referate (alleine oder im Team) zu halten, wobei die Themen vorgegeben sind (und sich Großteils um philosophische Auswege/Interpretationen der Church-Turing-These drehen).
• Nach der letzten Blockeinheit ist ein Take-Home-Test binnen einiger Wochen zu lösen und per Mail abzugeben. Im Grunde geht es dabei um das Lösen von Beispielen, die denen der Übung ähneln.

Zeitaufwand

• Neben der Anwesenheit im Seminar sind die Übungsbeispiele zu lösen. Es gab drei oder vier Übungsblätter. Falls man gedenkt, alle Beispiele durchzuarbeiten, sind für einen Informatiker ca. 1-2 Stunden pro Blatt einzuplanen.
• Außerdem hat man für das Referat den Text zu lesen (die Texte sind in Englisch) und aufzubereiten. Dauert auch ca. einen halben bis einen ganzen Tag.
• Der Take-Home-Test ist relativ einfach und in 1-2 Stunden gelöst, wenn man die Übungsbeispiele verstanden hat.

Vortrag

• Verständlicher, ruhiger Vortrag. Man erkennt bei Prof. Hafner deutlich den (trockenen) Humor eines Mathematikers, den ich köstlich fand.
• Zwischenfragen werden kompetent und verständlich beantwortet - auch wenn die Frage bereits zweimal behandelt wurde. Für viele StudentInnen der Philosophie war der Umgang mit so viel Formalismus und so vielen Algorithmen nicht immer einfach

Benotung

Für eine positive Note müssen folgende 3 Benotungsgrundlagen erfüllt sein (nach Wichtigkeit geordnet):

• Die Aufgaben des "Take-Home-Tests" müssen eigenständig und korrekt gelöst werden (Es waren ca. 7 obligatorische + 2 optionale Beispiele)
• Teilnahme an einem Referat
• Es sollte mindestens eine Lösung eines Beispiels an der Tafel präsentiert werde

Materialien

• Ich habe die Ausarbeitung meines Referats zu den Materialien hinzugefügt.

Literatur

• Mitschrift (Jede Definition und jede wichtige Bemerkung wird an die Tafel geschrieben)

Ein gutes Lehrbuch zum Thema (war im Handapparat als Kopiervorlage verfügbar):

• G.S. Boolos & R.C. Jeffrey: Computability and Logic. 3rd edition, Cambridge etc. (CUP) 1989.

Texte für die Referate:

• Marvin Minsky: Berechnung: Endliche und Unendliche Maschinen. Stuttgart etc. (Berliner Union, Kohlhammer) 1971.
• Eintrag "Craig's Theorem" In: P.Edwards (Hrsg.): The Encyclopedia of Philosophy. 1967.
• Hilary Putnam: Craig's Theorem. In: H.Putnam: Mathematics Matter and Method. Philosophical Papers, vol. 1, 2nd edition, Cambridge etc. (CUP) 1979.
• Michael Friedman: Wissenschaftslogik: The Role of Logic in the Philosophy of Science. (wird erscheinen in Synthese)
• A. Olszewsky et al.: Church's Thesis After 70 Years. Frankfurt etc. (Ontos Verlag) 2006.
• A. Hodges: did Church and Turing Have a Thesis about Machines? In: Olszewski et al. (2006), S.243-352.
• Stewart Shapiro: Computability, Proof, and Open-Texture. In: Olszewski et al. (2006), S.420-455.
• E. Mendelson: On the Impossibility of Proving the "Hard-Half" of Chruch's Thesis. In: Olszewski et al. (2006), S.304-309.
• R. Murawski & J. Wolenski: The Status of Chruch's Thesis. In: Olszewski et al. (2006), S.310-330.
• Stewart Shapiro: Computability, Proof, and Open-Texture. In: Olszewski et al. (2006), S.420-455
• Cregory Chaitin: Meta Math! The Quest for Omega. New York (Vintage Books) 2006.

Materialien

Neues Material hinzufügen

R

• Referat 2008-06.doc (details)