Wann ist eine Funktion (über den natürlichen Zahlen) berechenbar?
Intuitiv: wenn es einen Algorithmus gibt, der sie berechnet
Was heißt, eine Elementaroperation ist maschinell ausführbar?
Was verstehen wir unter einer Rechenmaschine?
verschiedene Ansätze zur Präzisierung des Berechenbarkeitsbegriffs:
All diese Präzisierungen (und weitere) beschreiben exakt dieselbe
Churchsche These: die so erfaßte Klasse von Funktionen ist identisch
mit der Klasse der intuitiv berechenbaren Funktionen