Um einige der heute verwendeten Berechnungsmodelle (wie Turingmaschinen, klassische Random-Access-Maschinen, Real-RAMs) ausreichend berücksichtigen zu können, wird ausgehend von einem weit gefassten Algorithmenbegriff ein uniformes Berechnungsmodell eingeführt, in dem die direkte Ausführung jeder Operation einer beliebigen festgehaltenen algebraischen Struktur möglich ist. Dabei werden wir als Basisstrukturen sowohl die Peano-Struktur als auch den Ring der reellen Zahlen betrachten und unter diesen Voraussetzungen Begriffe wie Berechenbarkeit, Entscheidbarkeit und Reduzierbarkeit diskutieren. Zu den Schwerpunkten gehört die Arithmetischen Hierarchie zur Klassifizierung von Mengen natürlicher Zahlen, während auf andere mögliche Schwerpunkte wie den Gödelschen Unvollständigkeitssatz und die Analytische Hierarchie nur am Rande eingegangen wird.
Weitere Themen: Schaltkreise (ein nichtuniformes Berechnungsmodell), zelluläre Automaten, neuronale Netze, DNA-Computing (Sticker-Systeme, Watson-Crick-Automaten).
- Dozent/in: Christine Gaßner