Non-Turing Computers and Non-Turing Computability

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

Abstract

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

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 93,031

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

Non-Turing Computers and Non-Turing Computability.Mark Hogarth - 1994 - PSA: Proceedings of the Biennial Meeting of the Philosophy of Science Association 1994:126-138.
Deciding arithmetic using SAD computers.Mark Hogarth - 2004 - British Journal for the Philosophy of Science 55 (4):681-691.
The Constructibility of Artificial Intelligence (as Defined by the Turing Test).Bruce Edmonds - 2000 - Journal of Logic, Language and Information 9 (4):419-424.
Accelerating Turing machines.B. Jack Copeland - 2002 - Minds and Machines 12 (2):281-300.
Physical Geometry.James P. Binkoski - 2016 - Dissertation, University of Massachusetts, Amherst

Analytics

Added to PP
2011-03-20

Downloads
74 (#228,603)

6 months
8 (#415,703)

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