B. Jack Copeland
Skip Abstract Section
Abstract
Accelerating Turing machines are Turing machines of a sort able to perform tasks that are commonly regarded as impossible for Turing machines. For example, they can determine whether or not the decimal representation of π contains n consecutive 7s, for any n; solve the Turing-machine halting problem; and decide the predicate calculus. Are accelerating Turing machines, then, logically impossible devices? I argue that they are not. There are implications concerning the nature of effective procedures and the theoretical limits of computability. Contrary to a recent paper by Bringsjord, Bello and Ferrucci, however, the concept of an accelerating Turing machine cannot be used to shove up Searle's Chinese room argument.
- Ambrose, A. (1935), 'Finitism in Mathematics (I and II)', Mind 35, pp. 186-203, pp. 317-340.Google Scholar
Cross Ref
- Benacerraf, P. (1962), 'Tasks, Super-Tasks, and the Modern Eleatics', Journal of Philosophy 59, pp. 765-784.Google ScholarCross Ref
- Black, M. (1951), 'Achilles and the Tortoise', Analysis 11, pp. 91-101.Google ScholarCross Ref
- Blake, R.M. (1926), 'The Paradox of Temporal Process', Journal of Philosophy 23, pp. 645-654.Google ScholarCross Ref
- Boolos, G.S., Jeffrey, R.C. (1980), Computability and Logic, 2nd edition, Cambridge: Cambridge University Press. Google ScholarDigital Library
- Bringsjord, S., Bello, P. and Ferrucci, D. (2001), 'Creativity, the Turing Test, and the (Better) Lovelace Test', Minds and Machines 11, pp. 3-27. Google ScholarDigital Library
- Chihara, C.S. (1965), 'On the Possibility of Completing an Infinite Process', Philosophical Review 74, pp. 74-87.Google ScholarCross Ref
- Church, A. (1936), 'A Note on the Entscheidungsproblem', Journal of Symbolic Logic 1, pp. 40-41.Google ScholarCross Ref
- Cleland, C.E. (1993), 'Is the Church-Turing Thesis True?', Minds and Machines 3, pp. 283-312.Google ScholarCross Ref
- Cleland, C.E. (1995), 'Effective Procedures and Computable Functions', Minds and Machines 5, pp. 9-23.Google ScholarCross Ref
- Copeland, B.J. (1997), 'The Broad Conception of Computation', American Behavioral Scientist 40, pp. 690-716.Google ScholarCross Ref
- Copeland, B.J. (1998a), Turing's O-machines, Penrose, Searle, and the Brain', Analysis 58, pp. 128- 138.Google ScholarCross Ref
- Copeland, B.J. (1998b), 'Even Turing Machines Can Compute Uncomputable Functions', in C. Calude, J. Casti, and M. Dinneen, eds., Unconventional Models of Computation, London: Springer-Verlag, pp. 150-164.Google Scholar
- Copeland, B.J. (1998c), 'Super Turing-Machines', Complexity 4, pp. 30-32. Google ScholarDigital Library
- Copeland, BJ. (2000), 'Narrow Versus Wide Mechanism', Journal of Philosophy 96, pp. 5-32.Google Scholar
- Copeland, B.J. and Hamkins, J.D. (in preparation), 'Infinitely Fast Computation'.Google Scholar
- Copeland, B.J. and Proudfoot, D. (1996), 'On Alan Turing's Anticipation of Connectionism', Synthese 108: pp. 361-377.Google ScholarCross Ref
- Copeland, B.J. and Proudfoot, D. (1999), 'Alan Turing's Forgotten Ideas in Computer Science', Scientific American 280 (April), pp. 76-81.Google ScholarCross Ref
- Copeland, B.J. and Sylvan, R. (1999), 'Beyond the Universal Turing Machine', Australasian Journal of Philosophy 77, pp. 46-66.Google ScholarCross Ref
- Earman, J. (1986), A Primer on Determinism, Dordrecht: Reidel.Google Scholar
- Earman, J. and Norton, J.D. (1993), 'Forever Is a Day: Supertasks in Pitowsky and Malament-Hogarth Spacetimes', Philosophy of Science 60, pp. 22-42.Google ScholarCross Ref
- Earman, J. and Norton, J.D. (1996), 'Infinite Pains: The Trouble with Supertasks', in A. Morton and S.P. Stich, eds., Benacerraf and his Critics, Oxford: Blackwell.Google Scholar
- Geroch, R. (1977), 'Prediction in General Relativity', in J. Earman, C. Glymour and J. Stachel, eds., Foundations of Space-Time Theories, Minnesota Studies in the Philosophy of Science, 8, Minneapolis: University of Minnesota Press.Google Scholar
- Gold, E.M. (1965), 'Limiting Recursion', Journal of Symbolic Logic 30, pp. 28-48.Google ScholarCross Ref
- Grünbaum, A. (1968), Modern Science and Zeno's Paradoxes, London: Allen and Unwin.Google Scholar
- Hamkins, J.D. and Lewis, A. (2000), 'Infinite Time Turing Machines', Journal of Symbolic Logic 65, pp. 567-604. Google ScholarDigital Library
- Hilbert, D. and Ackermann, W. (1928), Grundziige der Theoretischen Logik, Berlin: Springer.Google Scholar
- Hinton, J.M and Martin, C.B. (1954), 'Achilles and the Tortoise', Analysis 14, pp. 56-68.Google ScholarCross Ref
- Hofstadter, D.R. (1980), Gödel, Escher, Bach: An Eternal Golden Braid, Harmondsworth: Penguin. Google ScholarDigital Library
- Hogarth, M.L. (1992), 'Does General Relativity Allow an Observer to View an Eternity in a Finite Time?', Foundations of Physics Letters 5, pp. 173-181.Google ScholarCross Ref
- Hogarth, M.L. (1994), 'Non-Turing Computers and Non-Turing Computability', PSA 1994 1, pp. 126-138.Google ScholarCross Ref
- McCulloch, W.S., and Pitts, W. (1943), 'A Logical Calculus of the Ideas Immanent in Nervous Activity', Bulletin of Mathematical Biophysics 5, pp. 115-33.Google ScholarCross Ref
- Minsky, M.L. (1967), Computation: Finite and Infinite Machines, Englewood Cliffs, NJ.: Prentice-Hall. Google ScholarDigital Library
- Post, E.L. (1936), 'Finite Combinatory Processes- Formulation 1', Journal of Symbolic Logic 1, pp. 103-105.Google ScholarCross Ref
- Putnam, H. (1965), 'Trial and Error Predicates and the Solution of a Problem of Mostowski', Journal of Symbolic Logic 30, pp. 49-57.Google ScholarCross Ref
- Russell, B.A.W. (1915), Our Knowledge of the External World as a Field for Scientific Method in Philosophy, Chicago: Open Court.Google Scholar
- Russell, B.A.W. (1936), 'The Limits of Empiricism', Proceedings of the Aristotelian Society 36, pp. 131-150.Google ScholarCross Ref
- Searle, J. (1980), 'Minds, Brains, and Programs', Behavioral and Brain Sciences 3, pp. 417-424, 450-456.Google ScholarCross Ref
- Searle, J. (1989), Minds, Brains and Science, London: Penguin.Google Scholar
- Searle, J. (1990), 'Is the Brain's Mind a Computer Program?' Scientific American 262(1), pp. 20-25.Google ScholarCross Ref
- Searle, J. (1992), The Rediscovery of the Mind, Cambridge, MA: MIT Press. Google ScholarDigital Library
- Sorensen, R. (1999), 'Mirror Notation: Symbol Manipulation without Inscription Manipulation', Journal of Philosophical Logic 28, pp. 141-164.Google ScholarCross Ref
- Stewart, I. (1991), 'Deciding the Undecidable', Nature 352, pp. 664-665.Google ScholarCross Ref
- Taylor, R. (1951), 'Mr. Black on Temporal Paradoxes', Analysis 12, pp. 38-44.Google ScholarCross Ref
- Thomson, J.F. (1954), 'Tasks and Super-Tasks', Analysis 15, pp. 1-13.Google ScholarCross Ref
- Thomson, J.F. (1970), 'Comments on Professor Benacerraf's Paper', in W.C. Salmon, ed., Zeno's Paradoxes, Indianapolis: Bobbs-Merrill.Google Scholar
- Turing, A.M. (1936), 'On Computable Numbers, with an Application to the Entscheidungsproblem', Proceedings of the London Mathematical Society, Series 2, 42 (1936-37), pp. 230-265.Google Scholar
- Turing, A.M. (1938), 'Systems of Logic Based on Ordinals'. Dissertation presented to the faculty of Princeton University in candidacy for the degree of Doctor of Philosophy. Published in Proceedings of the London Mathematical Society 45 (1939), pp. 161-228.Google Scholar
- Turing, A.M. (1948), 'Intelligent Machinery', National Physical Laboratory Report, in B. Meltzer and D. Michie, eds., Machine Intelligence 5, Edinburgh: Edinburgh University Press. A digital facsimile of the original document may be viewed in The Turing Archive for the History of Computing. ¿http://www.AlanTuring.net/intelligent_machinery¿.Google Scholar
- Turing, A.M. (1950), 'Programmers' Handbook for Manchester Electronic Computer', University of Manchester Computing Laboratory. A digital facsimile of the original may be viewed in The Turing Archive for the History of Computing document. ¿http://www.AlanTuring.net/programmers_handbook¿.Google Scholar
- Watling, J. (1952), 'The Sum of an Infinite Series', Analysis 13, pp. 39-46.Google ScholarCross Ref
- Weyl, H. (1927), Philosophie der Mathematik und Naturwissenschaft, Munich: R. Oldenbourg.Google Scholar
- Weyl, H. (1949), Philosophy of Mathematics and Natural Science, Princeton: Princeton University Press.Google Scholar
Index Terms
- Accelerating Turing Machines
Recommendations
Do Accelerating Turing Machines Compute the Uncomputable?
Accelerating Turing machines have attracted much attention in the last decade or so. They have been described as "the work-horse of hypercomputation" (Potgieter and Rosinger 2010: 853). But do they really compute beyond the "Turing limit"--e.g., compute ...
Super-tasks, accelerating Turing machines and uncomputability
Super-recursive algorithms and hypercomputationAccelerating Turing machines are devices with the same computational structure as Turing machines (TM), but able to perform super-tasks. We ask whether performing super-tasks alone produces more computational power; for example, whether accelerating TM ...
Zeno machines and hypercomputation
This paper reviews the Church-Turing Thesis (or rather, theses) with reference to their origin and application and considers some models of "hypercomputation", concentrating on perhaps the most straight-forward option: Zeno machines (Turing machines ...
Comments