Die Church-Turing-These trifft Aussagen über die Fähigkeit einer Rechenmaschine:
Die Klasse der Turing-berechenbaren Funktionen stimmt mit der Klasse der intuitiv berechenbaren Funktionen überein.
Einfach gesagt
Jede Funktion, die überhaupt in irgendeiner Weise berechenbar ist, kann durch eine Turingmaschine berechnet werden
Anmerkungen
- Anerkanntes Rechenmodell: Von-Neumann-Rechner
- Idealisierte Von-Neumann-Rechner: Registermaschinen