Berechenbarkeit
|
|
|
|
|
Veranstaltungsnummer: 18.222
Titel: Berechenbarkeit
Veranstalter: Manfred Kudlek
Ort und Zeit: Mi 10-12 C-221
Lernziel:
Betrachtung des Begriffs 'Algorithmus' von verschiedenen Gesichtspunkten.
Inhalt:
Primitiv-rekursive und rekursive Funktionen, Ackermann-Funktion, Turing-Maschine, Entscheidbarkeit und Unentscheidbarkeit, Berechenbare Funktionen; Grzegorczyk-Hierarchie; Semi-Thue- und Normale Systeme, Post-Maschine; Markov-Algorithmen; Lambda-Kalkül; Diophantische Gleichungen, 10. Hilbert-Problem; Prädikatenlogik 1. Stufe, Typ-1 und Typ-2-Berechenbarkeit.
Stellung im Studienplan: Hauptstudium; Vertiefungsgebiete Th2, Th3
Voraussetzung: Grundstudium
Vorgehen: Vorlesung
Literatur:
- H. Hermes: Aufzählbarkeit, Entscheidbarkeit, Berechenbarkeit
- Z. Manna: Mathematical Theory of Computation
- E. Engeler: Introduction to the Theory of Computation
- W.S. Brainerd, L.H. Landweber: Theory of Computation
- K. Weihrauch: Computability
Periodizität: unregelmäßig
Bemerkungen:
Für LehrerInnen / NebenfächlerInnen, insbesondere für Mathematiker, geeignet.
Last Change: 17:40 05/19/2011 Imprint/Disclaimer