On the physical possibility of ordinal computation (draft)
|Abstract||α-recursion lifts classical recursion theory from the first transfinite ordinal ω to an arbitrary admissible ordinal α . Idealized computational models for α-recursion analogous to Turing machine models for classical recursion have been proposed and studied  and  and are applicable in computational approaches to the foundations of logic and mathematics . They also provide a natural setting for modeling extensions of the algorithmic logic described in  and . On such models, an α-Turing machine can complete a θ-step computation for any ordinal θ < α. Here we consider constraints on the physical realization of α-Turing machines that arise from the structure of physical spacetime. In particular, we show that an α-Turing machine is realizable in a spacetime constructed from R only if α is countable. While there are spacetimes where uncountable computations are possible and while they may even be empirically distinguishable from a standard spacetime, there is good reason to suppose that such nonstandard spacetimes are nonphysical. We conclude with a suggestion for a revision of Church’s thesis appropriate as an upper bound for physical computation.|
|Keywords||No keywords specified (fix it)|
|Categories||categorize this paper)|
|External links||This entry has no external links. Add one.|
|Through your library||Only published papers are available at libraries|
Similar books and articles
P. D. Welch (2008). The Extent of Computation in Malament–Hogarth Spacetimes. British Journal for the Philosophy of Science 59 (4):659-674.
Peter Koepke (2005). Turing Computations on Ordinals. Bulletin of Symbolic Logic 11 (3):377-397.
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 & Oron Shagrir (2007). Physical Computation: How General Are Gandy's Principles for Mechanisms? [REVIEW] Minds and Machines 17 (2):217-231.
Edwin J. Beggs, José Félix Costa & John V. Tucker (2010). Physical Oracles: The Turing Machine and the Wheatstone Bridge. Studia Logica 95 (1/2):279 - 300.
B. Maclennan (2003). Transcending Turing Computability. Minds and Machines 13 (1):3-22.
Itamar Pitowsky (2002). Quantum Speed-Up of Computations. Proceedings of the Philosophy of Science Association 2002 (3):S168-S177.
Paolo Cotogno (2003). Hypercomputation and the Physical Church-Turing Thesis. British Journal for the Philosophy of Science 54 (2):181-223.
W. Aitken & J. A. Barrett (2010). A Note on the Physical Possibility of Transfinite Computation. British Journal for the Philosophy of Science 61 (4):867-874.
Added to index2009-03-21
Total downloads5 ( #169,891 of 722,704 )
Recent downloads (6 months)0
How can I increase my downloads?