Church-Turing-These

Die Church-Turing-These geht von der formal bewiesenen Äquivalenz der Algorithmenbegriffe von Alonzo Church und Alan Turing aus. In ihrer verallgemeinerten Form vermutet sie, dass sämtliche formalen Algorithmenbegriffe, auch alle zukünftigen, maximal zu diesen beiden äquivalent sind (oder einen geringeren Geltungsanspruch besitzen). Dieser Satz ist natürlich nicht beweisbar, sondern eine Vermutung - die freilich seit vielen Jahrzehnten gilt. Es wäre also besser von einer Church-Turing-Vermutung zu sprechen.

Gegen die Church-Turing-These ist frühzeitig eingewendet worden, dass sie nicht beweisbar ist, aber wie alle mathematischen Beweise eine ahistorische Gültigkeit "für alle Zeiten" beansprucht, also den Algorithmenbegriff zu eng fasst. Andererseits werden mit der Turing-Maschine auch Verfahren als algorithmisch bezeichnet, die in der Praxis nicht berechenbar sind, z.B. weil sie Ressourcen erfordern, die die Grenzen menschlicher Zeitvorstellungen oder die vorstellbaren Möglichkeiten der Speicherung überschreiten.