On the physical possibility of ordinal computation (draft)
α-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)|
References found in this work BETA
No references found.
Citations of this work BETA
No citations found.
Similar books and articles
The Extent of Computation in Malament–Hogarth Spacetimes.P. D. Welch - 2008 - British Journal for the Philosophy of Science 59 (4):659-674.
SAD Computers and Two Versions of the Church–Turing Thesis.Tim Button - 2009 - British Journal for the Philosophy of Science 60 (4):765-792.
Physical Computation: How General Are Gandy's Principles for Mechanisms?B. Jack Copeland & Oron Shagrir - 2007 - Minds and Machines 17 (2):217-231.
Quantum Speed-Up of Computations.Itamar Pitowsky - 2002 - Proceedings of the Philosophy of Science Association 2002 (3):S168-S177.
Hypercomputation and the Physical Church-Turing Thesis.Paolo Cotogno - 2003 - British Journal for the Philosophy of Science 54 (2):181-223.
A Note on the Physical Possibility of Transfinite Computation.W. Aitken & J. A. Barrett - 2010 - British Journal for the Philosophy of Science 61 (4):867-874.
Added to index2009-03-21
Total downloads5 ( #601,285 of 2,172,876 )
Recent downloads (6 months)0
How can I increase my downloads?