Inhalt

Das Proseminar vertieft Inhalte aus den Grundvorlesungen der Arbeitsgruppe Theoretische Informatik. In diesem Semester werden weiterführende Themen aus der Berechenbarkeitstheorie behandelt, nämlich sogenannte "universelle" Systeme (zum Beispiel gewisse zelluläre Netze), die so allgemein sind, dass man jeden beliebigen Algorithmus damit ausführen kann.

Ablauf

Im Gegensatz zum üblichen Ablauf, wo die TeilnehmerInnen unabhängige Vorträge ausarbeiten, wollen wir diesmal ein Thema gemeinsam erarbeiten. Alle TeilnehmerInnen bereiten sich durch Lesen eines entsprechenden Abschnitts aus der Arbeit oder aus dem Buch auf das Treffen vor. Im wöchentlichen Treffen nehmen wir diesen Abschnitt gemeinsam durch, überlegen Beispiele und Gegenbeispiele zu den eingeführten Begriffen, und wollen die Argumente nachvollziehen. Gegebenenfalls müssen wir weitere Literatur zu Rate ziehen. Das Ziel ist, dass wir am Ende ein vertieftes Verständnis des Themengebiets haben. Ein/e jeweils designierte/r Protokollant oder Protokollantin bereitet sich besonders vor und kann die Diskussion führen, auf Schwierigkeiten hinweisen, und schreibt im Nachhinein eine stichwortartige schriftliche Zusammenfassung von ca. 3 Seiten Länge. Die Ausarbeitung kann bei den Aufgaben hochgeladen werden.

Literatur: Stephen Wolfram, A New Kind of Science, Wolfram Media, 2002.

Vorbesprechung

Die Vorbesprechung findet beim ersten Treffen in der ersten Vorlesungswoche, am Freitag, den 19. März, statt. Die üblichen Zeiten der Treffen sind freitags 10 Uhr s.t. im Raum 053.

Voraussetzung

Vertrautheit mit dem Begriff der Turingmaschine, entweder aus der Vorlesung Funktionale Algorithmen oder aus Grundlagen der Theoretischen Informatik.

Literatur

• Stephen Wolfram, A New Kind of Science, Wolfram Media, 2002
• Alex Smith, Universality of Wolfram’s 2, 3 Turing Machine. Complex Systems, 29:1–44, 2020. doi:10.25088/ComplexSystems.29.1.1.