{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,7,11]],"date-time":"2024-07-11T20:32:41Z","timestamp":1720729961057},"reference-count":30,"publisher":"Cambridge University Press (CUP)","issue":"6","license":[{"start":{"date-parts":[[2010,11,8]],"date-time":"2010-11-08T00:00:00Z","timestamp":1289174400000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Struct. Comp. Sci."],"published-print":{"date-parts":[[2010,12]]},"abstract":"<jats:p>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 \u03a3<jats:sub>1<\/jats:sub> and \u03a3<jats:sub>2<\/jats:sub>.<\/jats:p>","DOI":"10.1017\/s0960129510000344","type":"journal-article","created":{"date-parts":[[2010,11,8]],"date-time":"2010-11-08T06:00:45Z","timestamp":1289196045000},"page":"1011-1017","source":"Crossref","is-referenced-by-count":7,"title":["A note on accelerated Turing machines"],"prefix":"10.1017","volume":"20","author":[{"given":"CRISTIAN S.","family":"CALUDE","sequence":"first","affiliation":[]},{"given":"LUDWIG","family":"STAIGER","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2010,11,8]]},"reference":[{"key":"S0960129510000344_ref11","unstructured":"Fearnley L. (2008) Email to (and discussions with) C. Calude, 3 December 2008."},{"key":"S0960129510000344_ref24","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19780243107"},{"key":"S0960129510000344_ref6","doi-asserted-by":"publisher","DOI":"10.1016\/j.biosystems.2004.05.032"},{"key":"S0960129510000344_ref26","first-page":"371","volume-title":"Unconventional Models of Computation","author":"Svozil","year":"1998"},{"key":"S0960129510000344_ref5","volume-title":"Computability and Logic","author":"Boolos","year":"1980"},{"key":"S0960129510000344_ref16","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.11.040"},{"key":"S0960129510000344_ref30","first-page":"278","article-title":"Relativistic computers and non-uniform complexity theory","volume":"2509","author":"Wiedermann","year":"2002","journal-title":"Springer-Verlag Lecture Notes in Computer Science"},{"key":"S0960129510000344_ref25","doi-asserted-by":"publisher","DOI":"10.1038\/352664a0"},{"key":"S0960129510000344_ref1","unstructured":"Andr\u00e9ka H. , N\u00e9meti I. , N\u00e9meti P. , Madar\u00e1sz J. X. and Sz\u00e9kely G. (2006) Logic and Relativity Theory, Course Notes."},{"key":"S0960129510000344_ref2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-79235-9"},{"key":"S0960129510000344_ref4","doi-asserted-by":"publisher","DOI":"10.2307\/2013813"},{"key":"S0960129510000344_ref20","first-page":"276","volume-title":"Time and History (Papers of the 28th International Wittgenstein Symposium)","author":"Shagrir","year":"2005"},{"key":"S0960129510000344_ref9","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(93)90349-X"},{"key":"S0960129510000344_ref17","volume-title":"Theory of Recursive Functions and Effective Computability","author":"Rogers","year":"1967"},{"key":"S0960129510000344_ref8","doi-asserted-by":"publisher","DOI":"10.1023\/A:1015607401307"},{"key":"S0960129510000344_ref10","doi-asserted-by":"publisher","DOI":"10.1023\/A:1014019225365"},{"key":"S0960129510000344_ref7","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(78)90002-6"},{"key":"S0960129510000344_ref28","volume-title":"Computational Complexity","author":"Wagner","year":"1986"},{"key":"S0960129510000344_ref12","doi-asserted-by":"publisher","DOI":"10.1007\/BF00682813"},{"key":"S0960129510000344_ref13","doi-asserted-by":"publisher","DOI":"10.1002\/9780470757017"},{"key":"S0960129510000344_ref19","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2003.12.007"},{"key":"S0960129510000344_ref21","volume-title":"Introduction to the Theory of Computation","author":"Sipser","year":"2006"},{"key":"S0960129510000344_ref22","first-page":"393","article-title":"\u03c9-computations on Turing machines and the accepted languages","volume":"44","author":"Staiger","year":"1986","journal-title":"Coll. Math. Soc. Janos Bolyai"},{"key":"S0960129510000344_ref23","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-59126-6_6"},{"key":"S0960129510000344_ref14","doi-asserted-by":"publisher","DOI":"10.1007\/BF01691063"},{"key":"S0960129510000344_ref27","article-title":"On the Brightness of the Thomson Lamp","volume":"360","author":"Svozil","year":"2009","journal-title":"A Prolegomenon to Quantum Recursion Theory"},{"key":"S0960129510000344_ref29","doi-asserted-by":"crossref","DOI":"10.1063\/1.3066316","volume-title":"Philosophy of Mathematics and Natural Science","author":"Weyl","year":"1949"},{"key":"S0960129510000344_ref18","doi-asserted-by":"publisher","DOI":"10.1093\/aristotelian\/36.1.131"},{"key":"S0960129510000344_ref15","unstructured":"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.)"},{"key":"S0960129510000344_ref3","volume-title":"The Infinite Book. A Short Guide to the Boundless, Timeless and the Endless","author":"Barrow","year":"2005"}],"container-title":["Mathematical Structures in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0960129510000344","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,27]],"date-time":"2019-04-27T16:32:17Z","timestamp":1556382737000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0960129510000344\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,11,8]]},"references-count":30,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2010,12]]}},"alternative-id":["S0960129510000344"],"URL":"https:\/\/doi.org\/10.1017\/s0960129510000344","relation":{},"ISSN":["0960-1295","1469-8072"],"issn-type":[{"value":"0960-1295","type":"print"},{"value":"1469-8072","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,11,8]]}}}