Antworten
Die Church-Turing-These besagt, dass alle Probleme, die auf einer Turingmaschine lösbar sind, auch auf jedem modernen Computer gelöst werden können. Das bedeutet, dass die Leistungsfähigkeit von Computern durch Turingmaschinen begrenzt ist. In anderen Worten: Alles, was intuitiv berechenbar ist – also von einem Menschen berechnet werden kann –, kann auch von einer Turingmaschine berechnet werden. Ebenso gilt, dass alles, was eine andere Maschine berechnen kann, auch von einer Turingmaschine berechenbar ist. Diese These hat weitreichende Implikationen für die theoretische Informatik und die Grenzen der Berechenbarkeit.
Die Church-Turing-These (benannt nach Alonzo Church und Alan Turing, auch Churchsche These genannt) trifft Aussagen über die Fähigkeiten einer Rechenmaschine. Sie lautet:
„Die Klasse der Turing-berechenbaren Funktionen stimmt mit der Klasse der intuitiv berechenbaren Funktionen überein.“
Diese These ist nicht beweisbar, da der Begriff „intuitiv berechenbare Funktion“ nicht exakt formalisiert werden kann. Man versteht darunter alle Funktionen, die prinzipiell auf irgendeine Weise berechnet werden könnten. Damit setzt man insbesondere keine Vorstellung voraus, welche Funktionen auf den natürlichen Zahlen berechenbar sind. Es wird in der Informatik üblicherweise angenommen, dass die These stimmt. Dadurch wird es möglich, für eine Funktion nachzuweisen, dass sie nicht berechenbar ist.
