Gandy machine

In his 1980 paper Church's Thesis and Principles for Mechanisms, Robin Gandy sets out four principles for describing computing machines in terms of assemblies of parts; any such machine described in this way can be called a Gandy machine. The principles are summarized below.

One of Gandy's claims is apparently that any device which violates these principles would invalidate the Church-Turing thesis, as it would be capable of calculating a non-computable function (or as he colourfully puts it, "displaying free will".)

Interestingly, although Gandy's intent was to make the principles widely applicable in many different domains, he rules out Newtonian mechanics because it permits "rigid rods of arbitrary lengths" which violate Principle IV.

Gandy's Principles for Mechanisms

Principle I: The Form of Description

Gandy machines are described using hereditary finite sets with labels for their parts.

Principle II: Principle of Limitation of Hierarchy

The set theoretic rank of a Gandy machine is bounded. That is, there are no assemblies which contain infinite descending chains of subassemblies.

Principle III: Principle of Unique Reassembly

Any Gandy machine can be assembled from parts of bounded size. The labels of these parts uniquely determine the resulting machine.

Principle IV: Principle of Local Causality

Successive states of a Gandy machine can be reconstructed solely through local cause and effect. Each region of the machine has a neighbourhood of bounded size, and the region's next state is due only to the state of its neighbourhood.

External resources

• Gandy, R. O. 1980. Church's Thesis and Principles for Mechanisms. The Kleene Symposium, eds. J Barwise et al., pp 123-148. Amsterdam: North Holland Publ. Co. (1980; ISBN 0-444-85345-6)