Non-Turing Computers and Non-Turing Computability

Psa 1994:126--138 (1994)
  Copy   BIBTEX


A true Turing machine (TM) requires an infinitely long paper tape. Thus a TM can be housed in the infinite world of Newtonian spacetime (the spacetime of common sense), 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 ("close") 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 (e.g. intuitive, finitely programmed, limited in computational capability), 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: 77,869

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

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.
Alan Turing and the mathematical objection.Gualtiero Piccinini - 2003 - Minds and Machines 13 (1):23-48.
Church's Thesis and the Conceptual Analysis of Computability.Michael Rescorla - 2007 - Notre Dame Journal of Formal Logic 48 (2):253-280.
Alan Turing and the foundations of computable analysis.Guido Gherardi - 2011 - Bulletin of Symbolic Logic 17 (3):394-430.
Computability and recursion.Robert I. Soare - 1996 - Bulletin of Symbolic Logic 2 (3):284-321.
Turing's golden: How well Turing's work stands today.Justin Leiber - 2006 - Philosophical Psychology 19 (1):13-46.


Added to PP

57 (#213,362)

6 months
3 (#246,091)

Historical graph of downloads
How can I increase my downloads?

Author's Profile

Mark Hogarth
Cambridge University

References found in this work

No references found.

Add more references