Computability and \(\lambda\)-definability. (Q2603370)

Verf. hat früher (Proc. London math. Soc. (2), 42 (1936), 230-265; F.~d.~M. 62\(_{\text{II}}\), 1059) den Begriff der berechenbaren Funktion aufgestellt. Der Zweck der vorliegenden Abhandlung ist, zu zeigen, daß die berechenbaren Funktionen sowohl mit den \textit{Church}schen \(\lambda\)-definierbaren Funktionen (\textit{A.~Church}, Amer. J. Math., 58 (1936), 345-363; F.~d.~M. 62\(_{\text{I}}\), 46) wie mit den allgemein-rekursiven Funktionen von \textit{Herbrand} und \textit{Gödel} (vgl. \textit{S.~C.~Kleene}, Math. Ann. 112 (1936), 727-742; F.~d.~M. 62\(_{\text{I}}\), 44) identisch sind. Es wird hier bewiesen, daß jede \(\lambda\)-\(K\)-definierbare Funktion berechenbar ist, und daß jede berechenbare Funktion allgemeinrekursiv ist. Nun ist jede \(\lambda\)-definierbare Funktion auch \(\lambda\)-\(K\)-definierbar, und früher hat \textit{S.~C.~Kleene} (Duke math. J. 2 (1936), 340-353; F.~d.~M. 62\(_{\text{I}}\), 45) bewiesen, daß jede allgemein-rekursive Funktion \(\lambda\)-definierbar ist. Hieraus folgt dann die Äquivalenz aller vier Funktionsbegriffe. In Art.~1 gibt Verf. die Definition der \(\lambda\)-\(K\)-Definierbarkeit; der Begriff ``conversion'' ist hier besonders wichtig. In 2.~folgen Erklärungen über die Anwendung von Maschinen zur Ausführung von Schlüssen formal-logischer Theorien. In 3. wird die mechanische Ausführung der ``conversion'' erklärt. In 4. wird dann gezeigt, daß, wenn \(f(n)\) \(\lambda\)-\(K\)-definierbar ist, die aus Nullen und Einsen bestehende Zeichenreihe mit \(f(n)\) Einsen zwischen der \(n\)-ten und der \((n+1)\)-ten Null berechenbar ist. In 5. folgt der Beweis dafür, daß jede berechenbare Funktion allgemein-rekursiv ist.