Ranging from Alan Turing’s seminal 1936 paper to the latest work on Kolmogorov complexity and linear logic, this comprehensive new work clarifies the relationship between computability on the one hand and constructivity on the other. The authors argue that even though constructivists have largely shed Brouwer’s solipsistic attitude to logic, there remain points of disagreement to this day. Focusing on the growing pains computability experienced as it was forced to address the demands of rapidly expanding applications, the content maps the (...) developments following Turing’s ground-breaking linkage of computation and the machine, the resulting birth of complexity theory, the innovations of Kolmogorov complexity and resolving the dissonances between proof theoretical semantics and canonical proof feasibility. Finally, it explores one of the most fundamental questions concerning the interface between constructivity and computability: whether the theory of recursive functions is needed for a rigorous development of constructive mathematics. This volume contributes to the unity of science by overcoming disunities rather than offering an overarching framework. It posits that computability’s adoption of a classical, ontological point of view kept these imperatives separated. In studying the relationship between the two, it is a vital step forward in overcoming the disagreements and misunderstandings which stand in the way of a unifying view of logic. (shrink)

It is well known that Tarski proved a result which can be stated roughly as: no sufficiently rich, consistent, classical language can contain its own truth definition. Tarski's way around this problem is to deal with two languages at a time, an object language for which we are defining truth and a metalanguage in which the definition occurs. An obvious question then is: under what conditions can we construct a definition of truth for a given object language. Tarski claims that (...) it is necessary and sufficient that the metalanguage be "essentially richer". Our contention, put bluntly, is that this claim deserves more scrutiny from philosophers than it usually gets and in fact is false unless "essentially richer" means nothing else than "sufficient to contain a truth definition for the object language.". (shrink)

We analyze the representation of binary relations in general, and in particular of functions and of total antisymmetric relations, in monadic third order logic, that is, the simple typed theory of sets with three types. We show that there is no general representation of functions or of total antisymmetric relations in this theory. We present partial representations of functions and of total antisymmetric relations which work for large classes of these relations, and show that there is an adequate representation of (...) cardinality in this theory. The relation of our work to similar work by Henrard and Allen Hazen is discussed. This work can be understood as part of a program of assessing the capabilities of weak logical frameworks: our results are applicable for example, to the framework in David Lewis’s Parts of Classes. (shrink)