Churchsche These/Registermaschine/Bemerkung
Die Churchsche These (nach Alonzo Church, manchmal auch Church-Turing-These) behauptet, dass die intuitiv berechenbaren Funktionen (bzw. die intuitiv entscheidbaren Prädikate) mit den Register-berechenbaren Funktionen übereinstimmt. Da es sich bei „intuitiv berechenbar“ um einen nicht präzisen Begriff handelt, lässt sich diese These nicht beweisen. Sie ist dennoch weitgehend akzeptiert, wobei die folgenden Gründe angeführt werden.
- Alle Präzisierungen des Berechenbarkeitsbegriffs, nämlich durch Registermaschine, Turingmaschine, -rekursive Funktionen, -Kalkül, führen zu einer übereinstimmenden Klasse von berechenbaren Funktionen. Dies beruht darauf, dass man diese algorithmischen Verfahren wechselseitig simulieren kann.
- Konkrete, intuitiv berechenbare Funktionen lassen sich stets durch ein Registerprogramm realisieren.
In der Praxis ist die Churchsche These vor allem eine Erleichterung, da man aufgrund eines häufig naheliegenden intuitiven Algorithmus auf die Existenz eines Registerprogramms schließen kann, und so die oft mühevolle „Programmier-Arbeit“ umgeht.