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:

 

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