Church-Turing-These
Die Church-Turing-These geht von der formal bewiesenen Äquivalenz der Algorithmenbegriffe von Alonzo Church und Alan Turing aus: sie setzt also den intuitiven Begriff der Berechenbarkeit mit dem gleich, was eine Turingmaschine zu leisten vermag. 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, oder, wie es in der Informatik zum Teil praktiziert wird, statt von Berechenbarkeit von Turingberechenbarkeit oder Turingmächtigkeit.
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. Eine theoretische möglichkeit, eine Maschine zu schaffen, die mächtiger wäre als die Turingmaschine, wäre der Quantencomputer: er könnte theoretisch in endlicher Zeit leisten, wofür eine Turingmaschine unendlich lange brauchen würde.