Strict finitism and feasibility

Abstract

We examine the relation between predicative recurrence and strictly finitistic tenets in the philosophy of mathematics, primarily by focusing on the rôle of numerical notations in computing. After an overview of Wittgenstein's ideas on the “surveyability” of notations, we analyze a subtle form of circularity in the usual justification of the primitive recursive definition of exponentiation (Isles 1992), and suggest connections with recent works on predicative recurrence (Leivant 1993b, Bellantoni & Cook 1993).

This is an expanded version of my talk for the Logic and Computational Complexity Meeting, and is part of a larger project analyzing the confluence of mathematical results and philosophical arguments in the analysis of feasible computations that will be described in a future joint paper with Daniel Leivant, to whom I am greatly indebted for stimulating my interest in this field and for prompting me to write this preliminary account. It will be apparent from the text that his views, and also those of David Isles, have been quite influential on the present paper (of course they are not at all responsible for any of my mistakes). I am grateful also to Stephen Bellantoni, Paolo Boldi, Gabriele Lolli, Diego Marconi, Piergiorgio Odifreddi and Nicoletta Sabadini for criticisms and suggestions, and to Roberta Mari for playing both as Proponent and Opponent in the design of the games described in the last section. Finally, I would like to thank my friend, Miss Claudia Bonino, for betting long ago that this paper would eventually have been written. The research was supported by CNR Cooperation Project “Linguaggi Applicativi e Dimostrazioni Costruttive” and MURST 40%.