Hostname: page-component-586b7cd67f-rcrh6 Total loading time: 0 Render date: 2024-11-25T02:26:46.506Z Has data issue: false hasContentIssue false
  • English
  • Français

A note on accelerated Turing machines

Published online by Cambridge University Press:  08 November 2010

CRISTIAN S. CALUDE  and
LUDWIG STAIGER
CRISTIAN S. CALUDE
Affiliation:
Department of Computer Science, The University of Auckland, Private Bag 92019, Auckland, New Zealand Email: [email protected]
LUDWIG STAIGER
Affiliation:
Martin-Luther-Universität Halle-Wittenberg, Institut für Informatik, D - 06099 Halle, Germany Email: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

In this paper we prove that any Turing machine that uses only a finite computational space for every input cannot solve an uncomputable problem even when it runs in accelerated mode. We also propose two ways to define the language accepted by an accelerated Turing machine. Accordingly, the classes of languages accepted by accelerated Turing machines are the closure under Boolean operations of the sets Σ1 and Σ2.

Type
Paper
Information
Mathematical Structures in Computer Science , Volume 20 , Special Issue 6: Quantum Algorithms , December 2010 , pp. 1011 - 1017
Copyright
Copyright © Cambridge University Press 2010

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Andréka, H., Németi, I., Németi, P., Madarász, J. X. and Székely, G. (2006) Logic and Relativity Theory, Course Notes.Google Scholar
Balcázar, J. L., Díaz, J. and Gabarró, L. (1995) Structural Complexity I, Second revised edition, Springer-Verlag.CrossRefGoogle Scholar
Barrow, J. (2005) The Infinite Book. A Short Guide to the Boundless, Timeless and the Endless, Jonathan Cape.Google Scholar
Blake, R. M. (1926) The paradox of temporal process. J. Philos. 23 645–654.CrossRefGoogle Scholar
Boolos, G. and Jeffrey, R. C. (1980) Computability and Logic, Cambridge University Press.Google Scholar
Calude, C. S. and Păun, G. (2004) Bio-steps beyond Turing. Biosystems 77 (1–3)175–194.CrossRefGoogle ScholarPubMed
Cohen, R. S. and Gold, A. Y. (1978) ω-computations on Turing machines. Theoret. Comput. Sci. 6 1–23.CrossRefGoogle Scholar
Copeland, B. (2002) Accelerating Turing machines. Minds and Machines 12 (2)281–300.CrossRefGoogle Scholar
Engelfriet, J. and Hoogeboom, H. J. (1993) X-automata on ω-words. Theoret. Comput. Sci. 110 (1)1–51.CrossRefGoogle Scholar
Etesi, G. and Németi, I. (2002) Non-Turing computations via Malament–Hogarth space-times. International Journal of Theoretical Physics 41 341–370.CrossRefGoogle Scholar
Fearnley, L. (2008) Email to (and discussions with) C. Calude, 3 December 2008.Google Scholar
Hogarth, M. (1992) Does general relativity allow an observer to view eternity in a finite time? Foundations of Physics Letters 5 173–181.CrossRefGoogle Scholar
Floridi, L. (ed.) (2004) The Blackwell Guide to the Philosophy of Computing and Information, Blackwell.CrossRefGoogle Scholar
Landweber, L. H. (1969) Decision problems for ω-automata. Math. Syst. Theory 3 (4)376–384.CrossRefGoogle Scholar
Ord, T. (2002) Hypercomputation: Computing More than the Turing Machine. Honours Thesis, Computer Science Department, University of Melbourne (Available at arxiv.org/ftp/math/papers/0209/0209332.pdf.)Google Scholar
Potgieter, P. H. (2006) Zeno machines and hypercomputation. Theoretical Computer Science 358 23–33. (Available at arXiv:cs.CC/0412022.)CrossRefGoogle Scholar
Rogers, H. (1967) Theory of Recursive Functions and Effective Computability, McGraw Hill.Google Scholar
Russell, B. (1936) The limits of empiricism, Proc. Aristotelian Soc. 36 131–150.CrossRefGoogle Scholar
Shagrir, O. (2004) Super-tasks, accelerating Turing machines and uncomputability. Theoretical Computer Science 317 105–114.CrossRefGoogle Scholar
Shagrir, O. (2005) Accelerating Turing machines. In: Stadler, F. and Stroltzner, M. (eds.) Time and History (Papers of the 28th International Wittgenstein Symposium), Austrian Ludwig Wittgenstein Society 276–278.Google Scholar
Sipser, M. (2006) Introduction to the Theory of Computation, second edition, PWS.Google Scholar
Staiger, L. (1986) ω-computations on Turing machines and the accepted languages. In: Lovász, L. and Szemerédi, E. (eds.) Coll. Math. Soc. Janos Bolyai 44 393–403.Google Scholar
Staiger, L. (1997) ω-languages. In: Rozenberg, G. and Salomaa, A. (eds.) (1997) Handbook of Formal Languages 3, Springer-Verlag 339–387.CrossRefGoogle Scholar
Staiger, L. and Wagner, K. (1977) Rekursive Folgenmengen I (in German). Zeitschr. Math. Logik u. Grundl. Mathematik 24 (6)523–538. A preliminary version appeared as: Wagner, K. and Staiger, L. (1977) Recursive ω-languages. In: Karpiński, M. (ed.) Proc. Fundamentals of Computation Theory '77. Springer-Verlag Lecture Notes in Computer Science 56 532–537.CrossRefGoogle Scholar
Stewart, I. (1991) Deciding the undecidable. Nature 352 664–665.CrossRefGoogle Scholar
Svozil, K. (1998) The Church–Turing thesis as a guiding principle for physics. In: Calude, C., Casti, J. and Dinneen, M. (eds.) Unconventional Models of Computation, Springer-Verlag 371–385.Google Scholar
Svozil, K. (2009) On the Brightness of the Thomson Lamp. A Prolegomenon to Quantum Recursion Theory. CDMTCS Research Report 360.Google Scholar
Wagner, K. and Wechsung, G. (1986) Computational Complexity, Deutscher Verlag der Wissenschaften.Google Scholar
Weyl, H. (1949) Philosophy of Mathematics and Natural Science, Princeton University Press.Google Scholar
Wiedermann, J. and vanLeeuwen, J. Leeuwen, J. (2002) Relativistic computers and non-uniform complexity theory. In: Calude, C. S., Dinneen, M. J. and Peper, F. (eds.) Unconventional Models of Computation. Springer-Verlag Lecture Notes in Computer Science 2509 278–298.Google Scholar