Rechner beziehen sich trotz Ihrer vielfältigen Anwendungen im Kern auf Berechnung. Die Turing-Maschine kann als Modell der v.Neumannschen Rechnerarchitektur gesehen werden. Die Churchsche These versucht diese Erkenntnis zu verabsolutieren: Berechnebarkeit sei äquivalent der Turing-Berechenbarkeit. Im Laufe der Zeit sind andere Modelle Berechenbarkeit vorgeschlagen worden. Auch die Struktur, Architektur udn Verwendung von Computern hat sich erheblich verändert.

In den letzten Jahren hat Peter Wegner die Funktion der Berechenbarkeit im Kontext der Interaktion in mehreren Papieren zur Diskussion gestellt. Dies ist Kernthema des Seminars.

Das Seminar wird als gemeinsamer Lesekurs mit Vorträgen zu einzelnen Aspekten durchgeführt. Die Veranstaltung richtet sich an Diplomstudierende der Informatik, Magister- und Lehramtsstudenten. Für die erfolgreiche Leistung wird ein Vortrag und eine schriftliche Ausarbeitung (mit einer HTML-Version) sowie durchgängige aktive Teilnahme erwartet.

Wolfgang Coy/Lena Bonsiepen

Rekursive Funktionen

Turings paper machine

• A. K. Dewdney: The New Turing Omnibus, Computer Science Press 1993
  Kurze Artikel über die wichtigsten Aspekte der Turingmaschine (Universelle TM, Halteproblem, ...).
• R. Herken (ed.): The Universal Turing Machine - A Half-Century Survey, Springer 1994
  Aufsätze über die Bedeutung der TM für Mathematik, Logik und Informatik.
• Dotzler, Kittler: Alan Turing - Intelligence Service, Brinkmann und Bose 1987
  Aufsätze von Turing (in deutsch).

Andere Modelle der Berechenbarkeit

• Posts Ersetzungssysteme
• Schwellwertlogiken und Perzeptrone
• Neural Networks
• Petri Netze

Peter Wegners Interaktionsmodelle: http://www.cs.brown.edu/people/pw/

• Tutorial Notes (PDF)
• Interactive Foundations of Computing (PDF)
• The Paradigm Shift from Algorithms to Interaction (PDF)
• Interactive Software Technology (PDF)
• Robin Milner, Interaction, Turing Lecture 1993, CACM Jan 93, pp.79 ff.

Es sei auf die Hinweise für Seminararbeiten verwiesen.

Adresse:
Prof. Dr. Wolfgang Coy
Dipl. Inform. Lena Bonsiepen

Humboldt-Universität zu Berlin
Institut für Informatik
Unter den Linden 6
D-10099 Berlin

Tel +49 30 20181 303
Fax +49 30 20181 304

coy@informatik.hu-berlin.de
lena@informatik.hu-berlin.de

Gültig bis Februar 98 Letzte Änderung Oktober 97