Calculations by man and machine: conceptual analysis*

Summary

Analysis & history To investigate calculations is to analyze symbolic processes carried out by calculators; that is a lesson we owe to Turing. Taking the lesson seriously, I will formulate restrictive conditions and well-motivated axioms for two types of calculators, namely, for human (computing) agents and mechanical (computing) devices. My objective is to resolve central foundational problems in logic and cognitive science that require a deeper understanding of the nature of calculations. Without such an understanding, neither the scope of undecidability and incompleteness results in logic nor the significance of computational models in cognitive science can be explored in their proper generality. The claim for logic is almost trivial and implies the claim for cognitive science; after all, the relevant logical notions have been used when striving to create artificial intelligence or to model mental processes in humans.

The foundational problems come to the fore in arguments for Church's or Turing's Thesis, asserting that an informal notion of effective calculability is captured fully by a particular precise mathematical concept. Church's Thesis, for example, claims in its original form that the effectively calculable number theoretic functions are exactly those functions whose values are computable in Gödel's equational calculus. My strategy, when arguing for the adequacy of a notion, is to bypass theses altogether and avoid the fruitless discussion of their (un-)provability. This can be achieved by conceptual analysis, i.e., by sharpening the informal notion, formulating its general features axiomatically, and investigating the axiomatic framework. Such an analysis will be provided for the two types of calculators I mentioned, examining closely and recasting thoroughly work of Turing and Gandy. My paper builds on systematic and historical work I have pursued for more than a decade, much of it in collaboration with John Byrnes, Daniele Mundici, and Guglielmo Tamburrini. The considerations presented here reshape and extend the earlier systematic work in a novel and, for me, unexpected way; their aim is nevertheless extremely classical, namely, to provide what Hilbert called eine Tieferlegung der Fundamente. It will also become evident that they are embedded in an illuminating historical context.

There is general agreement that Turing, in 1936, gave the most convincing analysis of effective calculability in his paper “On computable numbers - with an application to the Entscheidungsproblem”.