Deciding arithmetic using SAD computers

British Journal for the Philosophy of Science 55 (4):681-691 (2004)
  Copy   BIBTEX


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. Introduction Axiomatising computers The power of SAD computers Remarks regarding the concept of computability.



    Upload a copy of this work     Papers currently archived: 77,952

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles


Added to PP

64 (#192,394)

6 months
1 (#485,425)

Historical graph of downloads
How can I increase my downloads?

Author's Profile

Mark Hogarth
Cambridge University

Citations of this work

Computation in physical systems.Gualtiero Piccinini - 2010 - Stanford Encyclopedia of Philosophy.
The Physical Church–Turing Thesis: Modest or Bold?Gualtiero Piccinini - 2011 - British Journal for the Philosophy of Science 62 (4):733-769.
SAD computers and two versions of the Church–Turing thesis.Tim Button - 2009 - British Journal for the Philosophy of Science 60 (4):765-792.

View all 20 citations / Add more citations