Church Without Dogma: Axioms for Computability

Church’s and Turing’s theses assert dogmatically that an informal notion of effective calculability is captured adequately by a particular mathematical concept of computabilty. I present analyses of calculability that are embedded in a rich historical and philosophical context, lead to precise concepts, and dispense with theses.

To investigate effective calculability is to analyze processes that can in principle be carried out by calculators. This is a philosophical lesson we owe to Turing. Drawing on that lesson and recasting work of Gandy, I formulate boundedness and locality conditions for two types of calculators, namely, human computing agents and mechanical computing devices (or discrete machines). The distinctive feature of the latter is that they can carry out parallel computations.

Representing human and machine computations by discrete dynamical systems, the boundedness and locality conditions can be captured through axioms for Turing computors and Gandy machines; models of these axioms are all reducible to Turing machines. Cellular automata and a variety of artificial neural nets can be shown to satisfy the axioms for machine computations.