Lösung algorithmischer Probleme - die Church’sche These
Kurzbeschreibung des Forschungsprojekts
Die Berechenbarkeitstheorie beschäftigt sich mit der prinzipiellen Frage, ob bestimmte Probleme algorithmisch lösbar sind. Dieses Gebiet ist schon sehr alt und geht der Erfindung des Computers wie wir ihn heute kennen (weit) voraus. Die Church’sche These – nach Alonzo Church benannt – besagt, dass jeder Algorithmus auch auf einer Turingmaschine ausgeführt werden kann, einem besonderen abstrakten Maschinenmodell, welches auf Alan Turing zurückgeht.
Zum Anschauen
HIER geht es zur Homepage des Projekts
Themenanregungen für VWA und Diplomarbeit
- Die Churchsche These (oder auch These von Church und Turing) gilt allgemein als unumstößlicher Basissatz der Informatik, der weder bewiesen noch widerlegt werden kann. Trotzdem ist die These derzeit wieder verstärkt im Gespräch. Einerseits wurden kürzlich Untersuchungen begonnen diese These zu beweisen, andererseits sind bestimmte Varianten der These nicht konsistent mit der Existenz von Quantenrechnern. Die Herausforderung der Arbeit besteht darin die These in einem modernen Kontext zu betrachten.
Einstiegsliteratur
Spezialisierung
Berechenbarkeitstheorie
Schlüsselwörter: Informatik, Anfänge der Computer
Übermittler der Themenanregung:
Universität Innsbruck