On computable numbers, with an application to the Entscheidungsproblem. (Q2608913): Difference between revisions

Unter einer \textit{berechenbaren Zahl} versteht Verf. zunächst eine reelle Zahl, für die gilt, daß man -- anschaulich gesprochen -- die Ziffern ihrer Dezimaldarstellung sukzessive mit ``endlichen Mitteln'' berechnen kann. Die Analyse des Verhaltens eines Rechners, der diese Berechnung effektiv ausführt, legt dem Verf. eine gewisse strenge Erklärung der Berechenbarkeit nahe: Eine Zahl soll berechenbar heißen, wenn sie durch eine zirkelfreie automatische \textit{Rechenmaschine} berechnet werden kann. Hierbei ist eine derartige Rechenmaschine eine spezielle automatische Maschine, deren genaue Definition vom Verf. gegeben wird. Das Verhalten einer solchen Maschine wird durch eine endliche Tafel gegeben. Hieraus schließt man, daß es nur abzählbar viele Maschinen und deshalb auch nur abzählbar viele berechenbare Zahlen geben kann. Berechenbar sind z. B. alle reellen algebraischen Zahlen, die reellen Nullstellen der \textit{Bessel}funktionen, \(e\), \(\pi\). Diese Resultate gewinnt Verf. dadurch, daß er den Hilfsbegriff der berechenbaren Funktion einführt. Verf. zeigt dann, daß es eine ``Universalmaschine'' \(U\) gibt, die dieselbe Zahl berechnet wie irgendeine zirkelfreie Rechenmaschine, falls sie mit der (modifizierten) Tafel der letzteren ``versehen'' wird. -- Mit Hilfe von \(U\) und unter Anwendung eines Diagonalverfahrens gelingt der Nachweis, daß es gewisse Maschinen nicht geben kann, u. a. auch keine solche, die für eine beliebige Formel des beschränkten \textit{Hilbert}schen Funktionenkalküls die Ableitbarkeit ``entscheidet''. Hinsichtlich der vom Verf. vorgeschlagenen Definition der ``allgemeinen Methode, gewisse Dinge finit zu entscheiden,'' ist damit die Unlösbarkeit des \textit{Hilbert}schen Entscheidungsproblems gezeigt. In einem Anhang wird die Äquivalenz der \textit{Turing}schen ``Berechenbarkeit'' mit der \textit{Church}schen ``effective calculability'' bewiesen.