Non-Turing Computers and Non-Turing Computability

PSA: Proceedings of the Biennial Meeting of the Philosophy of Science Association 1994:126-138 (1994)
  Copy   BIBTEX


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.



    Upload a copy of this work     Papers currently archived: 84,049

External links

  • This entry has no external links. Add one.
Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

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


6 months

Historical graph of downloads

Sorry, there are not enough data points to plot this chart.
How can I increase my downloads?

Author's Profile

Mark Hogarth
Cambridge University

References found in this work

No references found.

Add more references