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


 

tags: Turingmaschine1gegreit Problem1gegreit Maschine1gegreit