Constructivity and Computability in Historical and Philosophical Perspective – DUBUCS; BOURDEAU (FU)

DUBUCS, J.; BOURDEAU, M. (Eds.). Constructivity and Computability in Historical and Philosophical Perspective. Dordrecht: Springer, 2014. (Series: Logic, Epistemology, and the Unity of Science). Resenha de: CARNIELLI1, Walter. Ser computável não é o mesmo que ser construtivo. Filosofia Unisinos, São Leopoldo, v.17, n.2, p.244-246, mai./ago., 2016

This book is a collection of essays focusing on the relationship between computability and constructivity. Taking into account the 80 years that have passed since Alan Turing’s seminal paper of 1936, the papers in the book examine two lines of development: on the one hand, the restrictions, generalizations and other modifications of the original Turing machines, resulting from the pressure that the notion of computability experienced from the explosive demand for applications, but also from encounters with concepts that are in principle stranger to Turing machines, such as Kolmogorov complexity and linear logic. On the other hand, some of the papers examine a more conceptual question, namely the interconnections between computability and constructivity. An especially important topic is whether the notion of computable function has to be taken as primitive, or can be founded on recursion theory.

Chapter 1, “Constructive Recursive Functions, Church’s Thesis, and Brouwers Theory of the Creating Subject: Afterthoughts on a Parisian Joint Session” by Göran Sundholm (p. 1-35) discusses the interdependence between recursive functions and constructivity, a topic that will also be examined in Chapter 6 by another author. It is argued that constructive functions cannot be replaced by recursive functions. Nonconstructive mathematics (apparently) fail to have a computational meaning. But what about the converse? Sundholm asks: “Is every function used in constructive mathematics recursive?” The answer has been negative since Heyting and Skolem: in constructivism, the primitive notion of a function cannot be replaced by that of a general recursive functions. The first part of this chapter explains why. A second topic discussed by Sundholm is the so-called Theory of the Creative Subject, which has already been called “provocative, attractive and dangerous” by A.S. Troelstra in his Principles of Intuitionism (1969).

The Theory of the Creative Subject, controversial even within intuitionism, was proposed by Brower as a method of constructing counterexamples for classical theorems based on the activity of an idealized mathematician. It is well known that this method, in a version formulated by G. Kreisel and J. Myhill, can be reconstructed in a certain kind of Kripke model. By analyzing the controversy regarding the Theory of the Creative Subject, and the related Kripke’s Schema (which basically asserts for each statement A the existence of a sequence that witnesses the validity of A) Sundholm shows, in this dense paper, how Kripke’s Schema can be used as a replacement for the Theory of the Creative Subject, and how this theory can be proved to be classically consistent, despite some of its apparent paradoxical unfoldings.

Chapter 2, “The Developments of the Concept of Machine Computability from 1936 to the 1960s” by Jean Mosconi (p. 37-56) investigates the relation between computation and machines, explaining how Turing’s ideas were gradually adopted and conveniently modified, leading to a close model of contemporary computers. Although Mosconi emphasizes the notion of constructive objects and the general notion of an algorithm on the light of Turing machines, I think that the reader should also take into consideration an illuminating paper by E.G. Daylight (2015), which explains why a certain group of scholars somehow associated with the Association for Computing Machinery (ACM) became interested in Turing’s work and made him, in retrospect, ‘the father of computer science.’ It seems instructive to read this chapter keeping in mind the misleading conception that Turing’s ideas were immediately appreciated by people involved in computing, after his 1936 inception of Turing machines.

Chapter 3, “Kolmogorov Complexity in Perspective Part I: Information Theory and Randomness” by Marie Ferbus-Zanda and Serge Grigorieff (p. 57-94) studies Kolmogorov complexity and the related notion of randomness. Kolmogorov complexity theory, or algorithmic information theory, was independently introduced by R.J. Solomonoff, A.N. Kolmogorov, and G. Chaitin, in parallel with C.E. Shannon’s information theory, but with different motivations. Both theories are intimately connected to computers, as they aim to provide measures of information by using the idea of the bit as a unity. As proposed by Chaitin, the notion of complexity can be used to provide a notion of randomness, via the so-called algorithmic definition of randomness, by relying on the capabilities and limitations of digital computers. This chapter, with a more technical nature, explains the main concepts and proofs related to these topics, also expounding other related notions of complexity, such as L. Levin’s monotone complexity and K.P. Schnorr’s process complexity.

Though not directly emphasized in this chapter, it is worth noting the intimate connection between the famous Gödel’s incompleteness proof and the theory of random numbers, as made clear in several works by Chaitin (the most relevant papers in this respect are cited in the chapter’s bibliography). As far as the most known proofs of Gödel’s incompleteness theorem are based on a version of the paradox of Epimenides, there is a similar proof of randomic incompleteness based on a variant of Berry’s paradox. This relevant result on measuring randomness, together with other results such as P. Martin-Löf’s, showing that randomness is equivalent to incompressibility, points to the possibility of using randomness as a foundation for probability theory, as explained in the chapter.

Chapter 4, “Kolmogorov Complexity in Perspective Part II: Classification, Information Processing and Duality” by Marie Ferbus-Zanda (p. 95-134) is a sequel to the previous chapter, with a more conceptual look at Kolmogorov algorithmic information theory. The chapter proposes to take this theory seriously as a mathematical foundation of information classification, discussing how the notions of compression and information content are related to classification and structure, and more generally to database and information systems. Google’s method of extracting information from the gigantic, unstructured databank represented by the World Wide Web (bottom-up model) and the relational database method based on pure logic (top-down model) to organize data, as proposed by E.F. Codd in 1970, are paradigmatic cases of classification and structure of information studied in this intricate chapter. Such models are the basis for the duality between the two modes of definition of mathematical objects: iterative definitions, and inductive (or recursive) definitions. The chapter makes clear how foundations of mathematics, information theory, and real-world applications are closely connected.

Chapter 5, “Proof-Theoretic Semantics and Feasibility” by Jean Fichot (p. 135-157) deals with foundations of constructibility by examining interpretations of constructive reasoning according to which the meaning of logical constants is determined by the way they are used in a language, or in other words that the meaning of the logical constants can be specified in terms of the introduction rules governing theman idea that amounts to G. Gentzen’s proof-theoretical investigations, complemented with the view that elimination rules are strictly unnecessary and can be obtained as a consequence of introduction definitions. This involves, however, the idealization behind canonical proofs, with dangers to feasibility. By examining the notions of polytime functions (introduced by S. Bellantoni and S. Cook in 1979), and a modification of linear logic, the light affine logic, introduced by A. Asperti in 1998, Fichot outlines a proof-theoretic semantics for feasible logic and for first-order light affine logic, evaluating their consequences.

Chapter 6, “Recursive Functions and Constructive Mathematics” by Thierry Coquand (p. 159-167) again takes up a fundamental question already treated in Chapter 1: is the theory of recursive functions necessary for a rigorous treatment of constructible mathematics? The chapter explains that, from the point of view of constructive mathematics, recursive functions are not needed for the foundations of constructible mathematics, and that mathematics done from an intuitionistic viewpoint does not rely on any notion of algorithm. This is hardly a novelty: in our book, Computability: Computable Functions, Logic, and the Foundations of Mathematics (Epstein and Carnielli, 2008, Chapter 26)2, it is explained in clear terms that recursive analysis is quite different from Brower’s intuitionism, and also how Bishop criticizes Brower’s work as too imprecise and infinitistic, and recursive analysis as too formal and limited. Indeed, it is well known that Bishop takes the notion of constructive function as primitive, refusing to identify it with any formal notion. This chapter, however, enriches its arguments with some brief accounts on the work of Heyting, Skolem, Novikoff, and Lorenzen, besides Bishop.

Chapter 7, “Gödel and Intuitionism” by Mark Atten (p. 169-214) closes the book, discussing how Brouwer’s intuitionism inspired the work of Gödel, with reflections in his famous Dialectica Interpretation. The interest of Gödel for Husserl and Brouwer is comparable to Gödel’s fascination with Leibniz, and can explain Gödel’s belief that the phenomenology of Husserl would prove useful for his program of “developing philosophy as an exact science” and the Dialectica Interpretation as a phenomenological contribution to intuitionism. An appendix to Gödel’s archives shows how he anticipated the concept of autonomous transfinite progressions of theories (the idea of generating a hierarchy of theories via a bootstrapping process, introduced in the literature by G. Kreisel in 1958) while working on his incompleteness proof.

The present book is the result of a meeting under the same name, “Constructivity and Computability in Historical and Philosophical Perspective”, held at the École Normale Supérieure in Paris, in December 2006. As the back cover states, this book contributes to the unity of science by aiming to overcome disagreements and misunderstandings that stand in the way of a unifying view of logic, and I believe it reaches its aims by weaving a deep and detailed account linking the mathematical and philosophical aspects of constructibility and recursivity, showing the limitations of both constructivist and classical mathematics.

Although at some points it is a bit difficult to read, as often happens with collections of texts sewing together pieces with different patterns and styles, this book is highly recommendable for logicians, philosophers, mathematicians, and computer scientists who want to understand how their fields interact.

Notas

1 Universidade Estadual de Campinas, Instituto de Filosofia e Ciências Humanas. Centro de Lógica, Epistemologia e História da Ciência. Barão Geraldo,13083-859, Caixa postal: 6133, Campinas, SP, Brasil. E-mail: walter.carnielli@cle.unicamp.br

2 See also the Brazilian edition, Computabilidade: Funções Computáveis, Lógica e os Fundamentos da Matemática (Carnielli and Epstein, 2009).

Referências

CARNIELLI, W.A.; EPSTEIN, R.L. 2009. Computabilidade: Funções Computáveis, Lógica e os Fundamentos da Matemática. São Paulo, Editora UNESP, 415 p.

DAYLIGHT, E.G. 2015. Towards a Historical Notion of ‘Turing the Father of Computer Science’. History and Philosophy of Logic, 36(3):205-228. https://doi.org/10.1080/01445340.2015.1082050

EPSTEIN, R.L.; CARNIELLI, W.A. 2008. Computability: Computable Functions, Logic, and the Foundations of Mathematics. Socorro, Advanced Reasoning Forum, 370 p.

TROELSTRA, A.S. 1969. Principles of Intuitionism. Berlin, Springer, 111 p. (Lecture Notes, no. 95). https://doi.org/10.1007/BFb0080643

Walter Carnielli – Universidade Estadual de Campinas. Instituto de Filosofia e Ciências Humanas. Centro de Lógica, Epistemologia e História da Ciência. Campinas, SP, Brasil. E-mail: walter.carnielli@cle.unicamp.br

Acessar publicação original

[DR]