Ein Direkter Beweis für die Allgemein-Rekursive Unlösbarkeit des Entscheidungsproblems des Prädikatenkalküls der Ersten Stufe mit Identität

✍ Scribed by László Kalmár

• Publisher: John Wiley and Sons
• Year: 1956
• Tongue: English
• Weight: 888 KB
• Volume: 2
• Category: Article
• ISSN: 0044-3050
• DOI: 10.1002/malq.19560020102

✦ Synopsis

Fur den zuerst von A. CHURCH^) bewiesenen Satz, wonach das Entscheidungsproblem des Pradikatenkalkiils der ersten Stufe (mit oder ohne Identitiit) 3, sich (bei Zugrundelegung der iiblichen Numerierungen der Formeln des Priidikatenkalkiils) nicht durch ein allgemein-rekursives Verfahren losen laBt,4) sind mehrere Beweise bekannt . 6, Die bisher publizierten Beweise sind meines Wissens shmtlich von der folgenden Struktur. Es wird zuniichst eine abzilhlbare Problemschar 6, P angegeben, wofiir bei Zugrundelegung einer festen Numerierung der zur Schar gehorigen Einzelprobleme gezeigt wird, daB sie sich nicht durch ein allgemein-rekursives Verfahren losen 1aBt. Dann wird die Problemschar P durch 1) Vorgetragen am 22. November 1954 vor dem Mathematischen Kolloquium an der Humboldt-Universitiit zu Berlin. 2) A. CWRCH, A note on the Entscheidungsproblem. J. Symb. Log. 1 , 4 0 4 1 (1936); Correction to A note on the Entscheidungsproblem. Ebenda, S. 101-102. a) Bei C H ~R ~H a. a. O., wird die allgemein-rekursive Unlosbarkeit des Entscheidungsproblems des Priidikatenkalkiils der ersten Stufe ohne Identitiit bewiesen; dasselbe Beweisverfahren kann jedoch unmittelbar (sogar noch etwas einfacher) auf das Entscheidungsproblem des Priidikatenkalkiils der ersten Stufe mit Identitiit angewandt werden. tfbrigens ist es bekmntlich fiir den Satz uber die allgemein-rekursive Unlosbarkeit des Entscheidungsproblems gleichgiiitig, ob es sich um das Entscheidungsproblem des Priidikatenkalkiils der ersten Stufe mit oder ohne Identitiit handelt. Das Wort ,,Entscheidungsproblem" werde ich weiter unten der Kiirze halber fur beide dieser Fassungen verwenden; ebenso nenne ich den Priidikatenkalkiil der ersten Stufe mit oder ohne Identitiit kurz ,,Priidikatenkalkul". *) Ob die iibliche Formulierung des CmRcHschen Satzes, daB niimlich das Entscheidungsproblem iiberhaupt nicht durch ein endliches Verfahren liisbar ist, richtig ist, hiingt 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. 356) ab, wonach eine arithmetische Funktion, deren Wert sich an jeder gegebenen StelIe in endlich vielen Schritten berechnen liiBt, notwendig allgemein-rekursiv ist. Ich gehe hier nicht auf die Frage des Zutreffens oder Nichtzutreffens diese: Vermutung ein, ich bemerke nur, daB es sichsolange man Berechenbarkeit nicht in einem mathematisch priizisierten, sondern, was fur die erwiihnte Formulierung des CHuRcHschen Satzes wichtig ist, im allgemeinsten Sinne versteht -, um eine erkenntnistheoretische Vermutung handelt, und daB man, wie ich an einer anderen Stelle niiher begriinden werde, gute (selbstverstiindlich philosophische) Griinde fur eine Bezweiflung dieser Vermutung hat. 5) Vgl. z. B., auBer CHURCH a. a. O., A. M. TURING, On computable numbers, with an application to the Entscheidungsproblem. Proc. of the London Math. SOC. (2) 42, 230-265 (1937), insbes. S. 259-263; On computable numbers, with an application to the Entscheidungsproblem. A correction. Ebenda (2) 48, 544-546 (1937).

6, Das heiBt ein Problem mit einem Parameter, der abziihlbar unendlich viele Werte anzunehmen fiihig ist, so daB zu jedem Parameterwert je ein Einzelproblem der Schar gehort, welches man mit ,,ja" oder ,,fiein" zu beantworten hat. In diesem Sinne ist auch das Entscheidungsproblem eine abziihlbare Problemschar mit einer Formel des Priidikatenkalkiils (deren Erfullbarkeit zu entscheiden ist) als Parameter.