Pénzes István (szerk.): Műszaki nagyjaink 6. Matematikusok, az oktatás, a gépészet és a villamos vontatás alkotói, kiváló lisztvegyészek (Budapest, 1986)
Dr. Ádám András - Dr. Dömösi Pál: Kalmár László
leit felír. f. math. Logik umI Grundlagen d. Math., lid. S. i—14 (1956) EIN DIREKTER BEWEIS FÜR DIE ALLGEMEIN-REKURSIVE UNLÖSBARKEIT DES ENTSCHEIDUNGSPROBLEMS DES PRÄDIKATENKALKÜLS DER ERSTEN STUFE MIT IDENTITÄT1) Von László Kalmár in Szeged, Ungarn 1. Für den zuerst von A. Church2) bewiesenen Satz, wonach das Entseneidungsproblem des Prädikatenkalküls der ersten Stufe (mit oder ohne Identität)3) sich (bei Zugrundelegung der üblichen Numerierungen der Formeln des Prädikatenkalküls) nicht durch ein allgemein-rekursives Verfahren lösen läßt,4) sind mehrere Beweise bekannt.5) Die bisher publizierten Beweise sind meines Wissens sämtlich von der folgenden Struktur. Es wird zunächst eine abzählbare Problemschar*) P angegeben, wofür bei Zugrundelegung einer festen Numerierung der zur Schar gehörigen Einzelprobleme gezeigt wird, daß sie sich nicht durch ein allgemein-rekursives Verfahren lösen läßt. Dann wird die Problemschar P durch *) Vorgetragen am 22. November 1954 vor dem Mathematischen Kolloquium an der Humboldt-Universität zu Berlin. *) A. Church, A note on the Entacheidungsproblem. J. Symb. Log. 1,40—41 (1930); Correction to A note on the Entscheidungsproblem. Ebenda, S. 101—102. s) Bei Church a. a O., wird die allgemein-rekursive Unlösbarkeit des Entscheidungsproblems des Prädikatenkalküls der ersten Stufe ohne Identität bewiesen; dasselbe Beweisverfahren kann jedoch unmittelbar (sogar noch etwas einfacher) auf das Entscheidungsproblem des Prädikatenkalküls der ersten Stufe mit Identität angewandt werden. Übrigens ist es bekanntlich für den Satz über die allgemein-rekursive Unlösbarkeit des Entscheidungsproblems gleichgültig, ob es sich um das Entscheidungsproblem des Prädikatenkalküls der ersten Stufe mit oder ohne Identität handelt. Das Wort „Entscheidungsproblem“ werde ich weiter unten der Kürze halber für beide dieser Fassungen verwenden; ebenso nenne ich den Prädikatenkalkül der ersten Stufe mit oder ohne Identität kurz „Prädikatenkalkül“. *) Ob die übliche Formulierung des CHURCHschen Satzes, daß nämlich das Entscheidungs- Problem überhaupt nicht durch ein endliches Verfahren lösbar ist, richtig ist, hängt vom Zutreffen oder Nichtzutreffen der CHURCHschen Vermutung (A. Church, An unsolvable problem of elementary number theory. Am. Journ. Math. 68, 345—363 (1936), insbes. S. 350) ab, wonach eine arithmetische Funktion, deren Wert sich au jeder gegebenen Stelle in endlich vielen Schritten berechnen läßt, notwendig allgemein-rekursiv ist. Ich gehe hier nicht auf die Frage des Zutreffens oder Nichtzutreffens dieser Vermutung ein, ich bemerke nur, daß es sich — solange man Berechenbarkeit nicht in einem mathematisch präzisierten, sondern, was für die erwähnte Formulierung des ChurchscKcu Satzes wichtig ist, im allgemeinsten Sinne versteht —, um eine erkenntnistheoretische Vermutung handelt, und daß man, wie ich an einer anderen Stelle näher begründen werde, gute (selbstverständlich philosophische) Gründe für eine Bezweiflung dieser Vermutung hat. s) Vgl. z. B., außer Church a. a. O., A. M. Turing, On computable numbers, with an application to the Entscheidungsproblem. Proc. of the London Math. Soe. (2) 42, 230—265 (1937), insbes. S. 259—263; On computable numbers, with an application to tho Entscheidungsproblem. A correction. Ebenda (2) 43, 544—546 (1937). *) Das heißt ein Problem mit einem Parameter, der abzählbar unendlich viele Werte anzuuehmen fähig ist, so daß zu jedem Parameterwert je ein Einzelproblem der Schar gehört, welches man mit „ja“ oder „nein“ zu beantworten hat. In diesem Sinne ist auch das Entscheidungsproblem eine abzahlbare Problem3char mit einer Formel des Prädikatenkalküls (deren Erfüllbarkeit zu entscheiden ist als Parameter. 1 Ztsclir. f. math. Logik 6. ábra Kalmár László írása az eldöntés-problémáról [A. 54]
