Church-Turing-These

Eine informelle grundlegende Behauptung, dass jede Funktion, die durch ein endliches mechanisches Verfahren (einen effektiven Algorithmus) berechnet werden kann, von einer Turing-Maschine berechnet werden kann; sie identifiziert Turing-Berechenbarkeit mit der intuitiven Vorstellung algorithmischer Berechenbarkeit.