Einfacher Beweis der Unmöglichkeit eines allgemeinen Lösungsverfahrens für arithmetische Probleme. (Q2585746): Difference between revisions

Es wird ein einfacher Beweis dafür gegeben, daß es kein allgemeines Lösungsverfahren für arithmetische Probleme geben kann. Die arithmetischen Klassen lassen sich nämlich leicht abzählen, und ein allgemeines Lösungsverfahren für arithmetische Probleme würde in der Angabe einer rekursiven Funktion bestehen, die für eine natürliche Zahl den Wert 0 oder 1 annimmt, je nachdem die der Zahl entsprechende Klasse leer ist oder nicht. Nun ist jede Gleichung zwischen rekursiven Funktionen mit einer arithmetischen Aussage gleichwertig. Dieser Satz wurde für primitive rekursive Funktionen von \textit{Gödel} (Mh. Math. Physik 38 (1931), 173-198; F.~d.~M. 57\(_{\text{I}}\), 54) bewiesen. Die Ausdehnung auf beliebige rekursive Funktionen erhält Verf. auf Grund der von \textit{Kleene} (Math. Ann., Berlin, 112 (1936), 727-742; F.~d.~M. 62\(_{\text{I}}\), 44) bewiesenen Tatsache, daß jede allgemein rekursive Funktion \(f(x_1, \ldots \!, x_n)\) die Form \(\psi(\varepsilon_y[\varrho(x_1, \ldots \!, x_n, \,y)=0])\) hat, wo \(\psi\) und \(\varrho\) primitive rekursive Funktionen sind und \(\varepsilon_y A(y)\) die kleinste Zahl \(y\) bedeutet, für die \(A(y)\) richtig ist. Durch einen Schluß nach Art des Diagonalverfahrens zeigt Verf. dann, daß die Annahme der Existenz einer einem allgemeinen Lösungsverfahren gleichwertigen rekursiven Funktion auf einen Widerspruch führt.