welt-verstehen/Church, stw1605C
Berechenbar ist, was eine Turingmaschine berechnen kann
|
|
D i s k u s s i o n
Beitrag 0-305
Das Konzept » Turingmaschine « definiert den Begriff der Berechenbarkeit
Die Church-Turing-These
Sie besagt:
Die Klasse aller turing-berechenbaren Funktionen stimmt mit der Klasse aller intuitiv berechenbaren Funktionen überein.
In anderen Worten:
Die Church-Turing-These besagt, dass keine Maschine — kein Computer —
ein Problem lösen kann, welches nicht auch durch eine Turing-Maschine lösbar ist.
Die Bedeutung dieser These — von der man ausgeht, dass sie zutrifft — ist:
Um zu sehen, ob ein gegebenes Problem mit Hilfe eines Computers und geeigneter Software lösbar ist,
braucht man sich nur zu überlegen, ob es durch eine Turingmaschine lösbar ist.
Eine Turingmaschine heißt u n i v e r s e l l , wenn sie jede andere Turingmaschine simulieren kann.
Man kann beweisen:
Sie besagt:
In anderen Worten:
Die Church-Turing-These besagt, dass keine Maschine — kein Computer —
ein Problem lösen kann, welches nicht auch durch eine Turing-Maschine lösbar ist.
Die Bedeutung dieser These — von der man ausgeht, dass sie zutrifft — ist:
braucht man sich nur zu überlegen, ob es durch eine Turingmaschine lösbar ist.
Eine Turingmaschine heißt u n i v e r s e l l , wenn sie jede andere Turingmaschine simulieren kann.
Man kann beweisen:
- Es gibt universelle Turingmaschinen, und:
- Es gibt Probleme, die keine Turing-Maschine lösen kann.
Ein solches Problem ist das sog. Halteproblem für Turingmaschinen, die Frage also, ob — gegeben eine Turingmaschine T und ein Problem P — die Maschine T angesetzt auf das Problem P zum Halten kommt.
- Selbst jeder Quantencomputer ist durch eine Turingmaschine simulierbar.
Nach oben