General recursive functions of natural numbers. (Q5923140)

Bekanntlich gibt es verschiedene Definitionen des Begriffes ``rekursive Funktion''. Man hat z. B. die primitiven Rekursionen, nämlich Rekursionen nach bloß einer Variablen, und die simultanen Rekursionen nach mehreren Variablen, welche nicht auf die primitiven zurückführbar sind. Deshalb ist es wünschenswert, einen allgemeinen Begriff ``rekursive Funktion'' zu definieren. In vorliegender Arbeit wird in \S\,1 eine solche allgemeine von \textit{J. Herbrand} und \textit{K. Gödel} herrührende Definition aufgestellt. Weiter wird in \S\,1 unter Anwendung der bekannten \textit{Gödel}schen Numerierung aller Formeln der Satz bewiesen: Jede rekursive Funktion, und zwar in dem hier definierten allgemeinen Sinn, kann in der Form \[ \psi(\varepsilon y[\varrho(x_1, \dots, x_n, y) = 0]) \] geschrieben werden, wo \(\psi\) und \(\varrho\) primitiv-rekursive Funktionen sind und \[ (x_1, \dots, x_n] (Ey) [\varrho (x_1, \dots, x_n, y) = 0] \] gilt, während \(\varepsilon y [\varrho (x_1, \dots, x_n, y) = 0]\) \ die kleinste Zahl \(y\) \ bedeutet, für welche \linebreak \(\varrho (x_1, \dots, x_n, y) = 0\) \ stattfindet. Die Umkehrung dieses Satzes gilt auch; Verf. zeigt nämlich, daß \ \(\varepsilon y[R(x_1, \dots, x_n, y)]\) \ rekursiv ist, wenn \ \(R(x_1, \dots, x_n, y)\) \ eine solche rekursive Relation ist, daß \ \((x_1, \dots, x_n) (Ey)R(x_1, \dots, x_n, y)\) \ gilt. In \S\,2 wird die Frage studiert, welche Gleichungssysteme rekursive Funktionen definieren. Die wichtigsten Ergebnisse sind: Diejenigen Systeme, welche das tun, können nicht rekursiv abgezählt werden, d. h. es ist nicht möglich, daß die Zahlen, welche bei der \textit{Gödel}schen Numerierung diesen Systemen zugeordnet werden, die sukzessiven Werte einer rekursiven Funktion darstellen. Hätte man nämlich eine solche Abzählung, so könnte man mit Hilfe des Diagonalverfahrens eine neue Funktion rekursiv definieren. Ebenso ist ein rekursives Verfahren nicht möglich zur Entscheidung darüber, welche Gleichungssysteme rekursive Funktionen definieren, d. h. es ist nicht möglich, eine rekursive Funktion der Systemnummer zu bilden, welche die Werte 0 oder 1 annimmt, je nachdem das System eine rekursive Funktion definiert oder nicht. Es wird weiter gezeigt, daß gewisse formallogische Systeme unentschuldbare Sätze der Form \[ (x)(Ey)[\varrho(x, y) = 0] \] enthalten, wo \(\varrho\) primitiv-rekursiv ist. Verf. beweist auch, daß es nicht-rekursive Funktionen \(\tau(x)\) gibt, die so definierbar sind: \(\tau(x) = 0\) oder 1, je nachdem \((y) [\varrho(x, y) = 0]\) gilt oder nicht, wobei \(\varrho\) primitiv-rekursiv ist.