These von Church
Die Churchsche These besagt, dass die Klasse der Turing-berechenbaren Funktionen genau die Klasse der intuitiv berechenbaren Funktionen ist.
Dieser Satz ist nicht formal beweisbar, da der Begriff der intuitiven Berechenbarkeit undefiniert ist. Er wäre jedoch widerlegt, wenn ein mächtigeres Rechnerkonzept als die Turingmaschine vorgestellt werden würde.
Es wird bezug genommen auf die Turingmaschine, die lange Zeit für das grundlegende Berechenbarkeitsmodell gehalten wurde.