bei uns gehört der ganze kram von kabel zum grundstudium! :)

Meines Wissen sind aber die Begriffe "total rekursiv" und "berechenbar" äquivalent, heißt also

Eine Funktion f ist total rekursiv (berechenbar), wenn es eine Tutingmaschine ( TM ) gibt, die auf die Eingabe x den Funktionswert f(x) berechnet.

Für überall definierte Funktionen heißt eine Funktion turing-berechenbar, wenn sie total rekursiv ist. Für parziell definierte Funktionen wird erlaubt, dass die TM für Eingaben, die nicht im Definitionsberech liegen, in eine unendliche Schleife gerät. Wenn das jedoch ausgeschlossen werden soll, ist wohl ausreichend, den Bildbereich der Funktion um ein neues Element # zu erweitern und alle Eingaben außerhalb des Definitionsbereiches auf # abzubilden.

zur "Churchschen These": die formale Definition der turing-Berechenbarkeit erfaßte Klasse von Funktionen stimmt mit der Klasse der intuitiv berechenbaren Funktionen überein.
Die These beinhaltet die Folgerung, dass es keinen umfassenden Berechenbarkeitsbegriff gibt, der nicht außerhalb unserer Intuition liegt. Die These wird dadurch untermauert, dass alle anderen Versuche, den Begriff "berecehnbar" formal zu erfassen, keine größere Klasse berechnbarer Funktionen ergeben haben. Dass andererseits die turing-berecehnbaren Funktionen "berecehnbar" sind, stößt wohl nicht auf Widerspruch. Die These kann (wei kabel schon erwähnt hat) prinzipiell nicht bewiesen werden. Sie könnte höchstens (was aber nirmand glaubt und hofft) falsifiziert werden, indem nicht turing-berechenbare Funktionen als berechenbar "nachgewiesen" werden.
Heutzutage geht man sogar noch einen Schritt weiter und glaubt, dass TMs sogar die Rechenzeit bis auf polynomielle Faktoren "richtig" erfassen. Ein Problem heißt dadurch genau dann effizient lösbar, wenn es von TMs in polynomieller Zeit gelöst werden kann.\n\n

<!--EDIT|esskar|1089794598-->