Penn Arts & Sciences Logo

Logic and Computation Seminar

Monday, March 31, 2014 - 3:00pm

Maté Szabo

Carnegie Mellon University

Location

University of Pennsylvania

2C4

In his famous paper from 1936, An Unsolvable Problem of Elementary Number Theory, Alonzo Church identified the intuitive notion of effective calculability with the mathematically precise notion of recursiveness. This proposal, known as Church's Thesis, has been widely accepted. Only a few people have argued against it. One of them is Laszlo Kalmar, who, in 1957 gave a talk in Amsterdam at the International Colloquium "Constructivity in Mathematics," entitled An Argument Against the Plausibility of Church's Thesis. The talk was published in the conference proceedings in 1959. The aim of this paper is to present and analyze Kalmar's argument in detail.

It is very useful to have an insight into Kalmár's general, sometimes peculiar, views on the foundations of mathematics. According to him, mathematics not only stems from experience and empirical facts, but even its justification is in part empirical. The development of mathematics, mathematical methods and notions is endless. As a consequence, mathematics cannot have a fixed foundation once and for all. Finally, presenting mathematical results in given, fixed frameworks is useful for precision and clarity, but mathematics is always done on an intuitive level, not in one or many of these frameworks.

Kalmar considers Church's Thesis as a pre-mathematical statement: it cannot be a mathematical theorem or definition, as it identifies a mathematically precise notion with an intuitive one. Thus, his argument against the plausibility of the thesis is also pre-mathematical. Kalmar begins by discussing his understanding of effective calculability, which is less restrictive than Church's, and questions the "objective meaning" of the notion of uniformity. That allows him to draw some "very unplausible" consequences of the thesis. It "implies the existence of an absolutely undecidable proposition which can be decided." This proposition is absolute in the sense that it is not undecidable relative to a fixed framework as the Gödel sentence is, but it is only one proposition and not an infinite set of propositions as Church's undecidable problems are. However, the proposition can be decided on an intuitive level.

Kalmar's different understanding of the notions of effective calculability and uniformity were not only motivated by his general views on the foundations of mathematics. His epistemological as well as his political views played a significant role in it. He expressed these views in his talks on the same topic in Hungarian in the 1950s. Within this broader context, Kalmar's rather short and peculiar paper appears a bit more appealing. However, in the end his argument does not affect Church's Thesis, given the usual understanding of effective calculability as mechanical procedures.