Lösung algorithmischer Probleme - die Church’sche These
Abstract
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.
Links
HIER geht es zur Homepage des Projekts
Ideas for articles
- 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.
Fundamental Literature
Special Offers
Berechenbarkeitstheorie
Keywords: Informatik, Anfänge der Computer
Offering Institution:
Universität Innsbruck