Lösung algorithmischer Probleme - die Church’sche These

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.

HIER geht es zur Homepage des Projekts

• 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.

• http://en.wikipedia.org/wiki/Church%E2%80%93Turing_thesis