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 ist genau die Klasse der intuitiv berechenbaren Funktionen.Diese
These ist nicht beweisbar, da der Begriff intuitiv berechenbare Funktion nicht exakt formalisiert werden kann. Man versteht darunter alle Funktionen, die prinzipiell auch von einem Menschen ausgerechnet 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 kann es ermöglicht werden, von einer Funktion nachzuweisen, dass sie nicht berechenbar ist.
Mehr unter Wikipedia.org...
Free Download Now!
