nach oben

Erschienen in:

2015 | OriginalPaper | Buchkapitel

Kalmár and Péter: Undecidability as a Consequence of Incompleteness

verfasst von : Máté Szabó

Erschienen in: Evolving Computability

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

László Kalmár and Péter Rózsa “proved that the existence of (...) undecidable problems follows from Gödel’s Theorem on relatively undecidable problems” ([6], p. vii). Unfortunately, the only available document of their joint work is Kalmár’s sketch of the proof in his [3]. In the following, I assemble a paper from Kalmár’s manuscripts on this issue.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel On Computability of Navier-Stokes’ Equation

Nächstes Kapitel How to Compare Buchholz-Style Ordinal Notation Systems with Gordeev-Style Notation Systems

That is, the undecidability of predicate logic.

The year of the completion of the first Hungarian edition.

Even in cases where the wording is unusual.

Although Folder 221 also contains the result and is entirely in English, but its presentation is significantly different from that of Folder 156. I chose to use Folder 213, written in English, supplemented by my translation of the last one and a half pages of Folder 156, as the latter is easier to follow.

The title was given by me. I believe it is more indicative of the content than other titles of the manuscripts, such as: On the relation between Gödel’s and Church’s theorems, and On the application of Gödel’s theorem to a proof of Church’s Theorem.

The parenthetical comment was added by me. The quote is from ([3], p. 758).

János Surányi (1918–2006), mathematician working in the fields of logic and algebra.

Tamás Varga (1919–1987), educationist, expert in the education of mathematics.

Tibor Szele (1918–1955), mathematician working in the field of algebra.

György Alexits (1899–1978), mathematician working in the field of analysis.

István Fenyő (1917–1987), mathematician working in the field of analysis.

The first page of Folder 221 lists some additional information on the development of their results: “Idea of proof of Church’s theorem based on a general form of Gödel’s theorem: Rózsa Péter, letter to Bernays, 1945.” Sadly, the letters from Péter to Bernays which have been written around this time and are preserved in the library of ETH Zürich do not mention this result. About the development towards abstract forms of Gödel’s Theorem, Kalmár cites Chauvin’s [1] which led to [4] and [5], his early, abstract formulations of Gödel’s Theorem in French. Finally, he quotes Henkin’s review [2] of [4] and [5]: “The abstractions are not fruitful because no new particular cases which are of importance in themselves are brought by these means within the scope of Gödel’s theorems.” (p. 230).

It is called “Formal system” in Hungarian. Thus, in this paper “deductive theory” and “formal system” are interchangeable.

The parenthetical comment was added by me. The word ‘arbitrary’ occurs only in the Hungarian version.

In manuscripts written in English, Kalmár uses “thesis” instead of “theorem.” I conjecture that he uses “thesis” because of the unrestricted character of proofs in \(\theta \).

The parenthetical comment was added by me. In Folder 347 Kalmár mentions some instances of classes of functions that the terms \(T\) can range over: (1) general recursive functions; (2) primitive recursive functions; (3) elementary functions.

\(p_{k}\) is defined and is a diagonal proof means that \(\omega (p_{k})\) is a diagonal formula, thus \(\omega (p_{k})=\iota (t_{n},n)\) for some \(t\in T\), \(n\in N\) where \(t_{n}\) is defined. The index of \(p_{k}\) is the index of \(\omega (p_{k})\), thus \(n\).

Here the Hungarian version says that for suitable mappings \(\gamma \) is an elementary function (and thus representable) and adds the following remark: “From now on let \(\tau \) and \(\pi \) be such fixed mappings [that \(\gamma \) is an elementary function]. In theory it is easy but technically it is tedious to show that 2.2 holds for those formal (axiomatic) systems that are used in mathematics.” (Folder 156, p. 3).

\(\lnot \vdash \) should also here be understood as \(\nvdash \). Thus, in (ii) it is assumed \(\iota (t,n)\) is not provable, and depending on whether \(\overline{\iota }(t,n)\) is provable or not, it leads to \(2^{0}\) or \(3^{0}\), respectively. See the last two lines of the proof.

The parenthetical comment was added by me. As the Hungarian version deals only with elementary functions, \(E\) is used everywhere instead of \(T\). Hopefully, this will not lead to any confusion.

The word “method” (instead of procedure) comes from Folder 347. Although it is unusual wording I tried to incorporate as much of Kalmár’s original manuscripts in English as I could. In the following pages the words “application”, “good” and “regular” algorithm are also taken from Folder 347.

Here, once again, the wording comes from Folder 347. At a similar point of that folder Kalmár remarks that “instead of defining formally” what an algorithm or method is, “we formulate the facts needed in the sequel, concerning (...) their applications and results.” (p. 14).

In the Hungarian version Kalmár uses \(A\) instead of A because previously it was not used to denote deductive theories. This distinction between the two A-s almost disappears since in the next step a deductive theory is assigned to the algorithm.

In the English version 2.1 requires \(T\) and \(P\) to be enumerable. In the Hungarian version it requires only \(P\) to be enumerable. It does not lead to any problems, since the set \(E\) which is used here instead of \(T\) is clearly enumerable and thus satisfies the enumerability requirement. Thus, 2.1 is obviously satisfied.

2.2 is a “regularity condition” which requires that the relationship between the terms \(T\) and the applications (proofs) \(P\) is regular in some sense. In particular, here, it requires that there are such Gödel numberings of the elementary functions and of the applications of the algorithm that the Gödel function \(\gamma \) is an elementary function as well (and thus it is representable). In footnote 19 I already quoted Kalmár, claiming that 2.2 can be satisfied.

If instead of elementary functions some other class of arithmetical functions is used, e.g. the class of general recursive functions, then the task is to show that the corresponding Gödel function is a member of the class in question, and hence it is representable.

The last comment about Markov’s normal algorithms and partially recursive algorithms being regular claims that the usual notions of algorithms or procedures all fall under the above open ended informal definition.

Chauvin, A.: Structures logiques. CR Hebdomadaires Séances Acad. Sci. 228, 1085–1087 (1949)MATHMathSciNet

Henkin, L.: Review of Kalmár’s [4] and [5]. J. Symbolic Logic 15(3), 230 (1950)MathSciNetCrossRef

Kalmár, L.: On unsolvable mathematical problems. In: Beth, E.W., Pos, J., Hollak, J. (eds.) Proceedings of the Tenth International Congress of Philosophy (Amsterdam), pp. 756–758. North-Holland, Amsterdam (1949)

Kalmár, L.: Une forme du théorème de Gödel sous des hypothèses minimales. CR Hebdomadaires Séances Acad. Sci. 229, 963–965 (1949)MATH

Kalmár, L.: Quelques formes générales du théorème de Gödel. CR Hebdomadaires Séances Acad. Sci. 229, 1047–1049 (1949)MATH

Péter, R.: Playing with Infinity. Translated by Zoltan Dienes. Dover, New York (1976)

Titel: Kalmár and Péter: Undecidability as a Consequence of Incompleteness
verfasst von: Máté Szabó
Verlag: Springer International Publishing
Buch: Evolving Computability
Print ISBN: 978-3-319-20027-9

Electronic ISBN: 978-3-319-20028-6

Copyright-Jahr: 2015
DOI: https://doi.org/10.1007/978-3-319-20028-6_35

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"