Journal Article

Deciding Arithmetic Using <i>SAD</i> Computers

Mark Hogarth

in The British Journal for the Philosophy of Science

Published on behalf of British Society for the Philosophy of Science

Volume 55, issue 4, pages 681-691
Published in print December 2004 | ISSN: 0007-0882
Published online December 2004 | e-ISSN: 1464-3537 | DOI:
Deciding Arithmetic Using SAD Computers

More Like This

Show all results sharing these subjects:

  • Philosophy of Science
  • Science and Mathematics


Show Summary Details


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.


Axiomatising computers

The power of SAD computers

Remarks regarding the concept of computability

Journal Article.  0 words. 

Subjects: Philosophy of Science ; Science and Mathematics

Full text: subscription required

How to subscribe Recommend to my Librarian

Users without a subscription are not able to see the full content. Please, subscribe or login to access all content.