Psa 1994:126--138 (1994)
|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|
|Keywords||No keywords specified (fix it)|
|Through your library||Configure|
Similar books and articles
Mark Hogarth (2004). Deciding Arithmetic Using SAD Computers. British Journal for the Philosophy of Science 55 (4):681-691.
Tim Button (2009). Sad Computers and Two Versions of the Church–Turing Thesis. British Journal for the Philosophy of Science 60 (4):765-792.
B. Jack Copeland (2002). Accelerating Turing Machines. Minds and Machines 12 (2):281-300.
Peter Kugel (2002). Computing Machines Can't Be Intelligent (...And Turing Said So). Minds and Machines 12 (4):563-579.
Gualtiero Piccinini (2003). Alan Turing and the Mathematical Objection. Minds and Machines 13 (1):23-48.
Michael Rescorla (2007). Church's Thesis and the Conceptual Analysis of Computability. Notre Dame Journal of Formal Logic 48 (2):253-280.
Guido Gherardi (2011). Alan Turing and the Foundations of Computable Analysis. Bulletin of Symbolic Logic 17 (3):394-430.
Robert I. Soare (1996). Computability and Recursion. Bulletin of Symbolic Logic 2 (3):284-321.
Paolo Cotogno (2003). Hypercomputation and the Physical Church-Turing Thesis. British Journal for the Philosophy of Science 54 (2):181-223.
Yaroslav Sergeyev & Alfredo Garro (2010). Observability of Turing Machines: A Refinement of the Theory of Computation. Informatica 21 (3):425–454.
Justin Leiber (2006). Turing's Golden: How Well Turing's Work Stands Today. Philosophical Psychology 19 (1):13-46.
Eli Dresner (2008). Turing-, Human- and Physical Computability: An Unasked Question. Minds and Machines 18 (3).
Saul A. Kripke (forthcoming). Another Approach: The Church-Turing ‘Thesis’ as a Special Corollary of Gödel’s Completeness Theorem. In B. J. Copeland, C. Posy & O. Shagrir (eds.), Computability: Gödel, Turing, Church, and beyond. MIT Press.
Added to index2011-03-20
Total downloads5 ( #160,284 of 549,065 )
Recent downloads (6 months)2 ( #37,252 of 549,065 )
How can I increase my downloads?