welt-verstehen/Church, stw1605C
Unsere Welt zu verstehen: Church
Beitrag 0-305
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:
aus Notizen zu
Berechenbar ist, was eine Turingmaschine berechnen kann
Impressum
B
G
E
— hmsgnr0305z
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.
tags: stw1283C: Church
Berechenbar ist, was eine Turingmaschine berechnen kann
Impressum