Deciding Arithmetic UsingSADComputers
Mark Hogarth · The British Journal for the Philosophy of Science · 2004
Presented here is a new result concerning the computational power of so-called SADn computers, a class of Turing-machine-based computers that can perform some non-Turing computable feats by utilising the geometry of a particular kind of general relativistic spacetime. It is shown that SADn can decide n-quantifier arithmetic but not (n+1)-quantifier arithmetic, a result that reveals how neatly the SADn family maps into the Kleene arithmetical hierarchy. 1. Introduction 2. Axiomatising computers 3. The power of SAD computers 4. Remarks regarding the concept of computability