Non-Turing Computers and Non-Turing Computability

Mark Hogarth
Cambridge University
A true Turing machine requires an infinitely long paper tape. Thus a TM can be housed in the infinite world of Newtonian spacetime, but not necessarily in our world, because our world-at least according to our best spacetime theory, general relativity-may be finite. All the same, one can argue for the "existence" of a TM on the basis that there is no such housing problem in some other relativistic worlds that are similar to our world. But curiously enough-and this is the main point of this paper-some of these close worlds have a special spacetime structure that allows TMs to perform certain Turing unsolvable tasks. For example, in one kind of spacetime a TM can be used to solve first-order predicate logic and the halting problem. And in a more complicated spacetime, TMs can be used to decide arithmetic. These new computers serve to show that Church's thesis is a thoroughly contingent claim. Moreover, since these new computers share the fundamental properties of a TM in ordinary operation, a computability theory based on these non-Turing computers is no less worthy of investigation than orthodox computability theory. Some ideas about this new mathematical theory are given.
Keywords No keywords specified (fix it)
Categories No categories specified
(categorize this paper)
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 70,192
External links

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library

References found in this work BETA

No references found.

Add more references

Citations of this work BETA

Computation in Physical Systems.Gualtiero Piccinini - 2010 - Stanford Encyclopedia of Philosophy.
Why We View the Brain as a Computer.Oron Shagrir - 2006 - Synthese 153 (3):393-416.

View all 41 citations / Add more citations

Similar books and articles

Deciding Arithmetic Using SAD Computers.Mark Hogarth - 2004 - British Journal for the Philosophy of Science 55 (4):681-691.
SAD Computers and Two Versions of the Church–Turing Thesis.Tim Button - 2009 - British Journal for the Philosophy of Science 60 (4):765-792.
Accelerating Turing Machines.B. Jack Copeland - 2002 - Minds and Machines 12 (2):281-300.
Deviant Encodings and Turing’s Analysis of Computability.B. Jack Copeland & Diane Proudfoot - 2010 - Studies in History and Philosophy of Science Part A 41 (3):247-252.
Omnibus Review. [REVIEW]John Crossley - 1991 - Journal of Symbolic Logic 56 (3):1089-1090.
[Omnibus Review].John N. Crossley - 1991 - Journal of Symbolic Logic 56 (3):1089-1090.
Alan Turing and the Mathematical Objection.Gualtiero Piccinini - 2003 - Minds and Machines 13 (1):23-48.
Infinite Time Turing Machines.Joel David Hamkins & Andy Lewis - 2000 - Journal of Symbolic Logic 65 (2):567-604.
Infinite Time Turing Machines.Joel David Hamkins - 2002 - Minds and Machines 12 (4):567-604.
Computable Diagonalizations and Turing’s Cardinality Paradox.Dale Jacquette - 2014 - Journal for General Philosophy of Science / Zeitschrift für Allgemeine Wissenschaftstheorie 45 (2):239-262.


Added to PP index

Total views

Recent downloads (6 months)

How can I increase my downloads?


Sorry, there are not enough data points to plot this chart.

My notes