Automatentheorie

In diesem Grundlagenseminar soll ein konkretes Verstehen der wichtigsten Begriffe aus der Computer- und Netztheorie erarbeitet werden. Was ist eine Maschine und was eine Turing-Maschine? Was sind Algorithmen und was ist eine Struktur? Was ist der Unterschied zwischen universell und universal, zwischen effektiv und effizient? Warum reichen zwei Zeichen für eine Berechnung (binäres Stellenwertsystem) aus? Wo liegen die Grenzen der Berechenbarkeit (Halte- bzw. Entscheidungsproblem) und wie stehen diese Grenzen zu unserem Denken und künstlerischen Handeln (Kreativität) in Beziehung?

Einführende Literatur:
Wiener, Oswald u.a., 1998, Eine elementare Einführung in die Theorie der Turing-Maschinen, Wien, New York;
Hopcroft, John E., Jeffrey D. Ullmann, 1979, 1994, Introduction to Automata Theory, Languages, and Computation. Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie, Bonn u.a.;
Krämer, Sybille, 1988, Symbolische Maschinen. Die Idee der Formalisierung in geschichtlichem Abriß, Darmstadt.