{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,18]],"date-time":"2025-03-18T22:10:10Z","timestamp":1742335810097,"version":"3.40.1"},"publisher-location":"Berlin, Heidelberg","reference-count":112,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642276590"},{"type":"electronic","value":"9783642276606"}],"license":[{"start":{"date-parts":[[2012,1,1]],"date-time":"2012-01-01T00:00:00Z","timestamp":1325376000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-27660-6_32","type":"book-chapter","created":{"date-parts":[[2012,1,16]],"date-time":"2012-01-16T15:14:28Z","timestamp":1326726868000},"page":"385-405","source":"Crossref","is-referenced-by-count":18,"title":["The Complexity of Small Universal Turing Machines: A Survey"],"prefix":"10.1007","author":[{"given":"Turlough","family":"Neary","sequence":"first","affiliation":[]},{"given":"Damien","family":"Woods","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"4","key":"32_CR1","doi-asserted-by":"publisher","first-page":"677","DOI":"10.1145\/321420.321426","volume":"14","author":"S. Aanderaa","year":"1967","unstructured":"Aanderaa, S., Fischer, P.C.: The solvability of the halting problem for 2-state post machines. Journal of the Association for Computing Machinery\u00a014(4), 677\u2013682 (1967)","journal-title":"Journal of the Association for Computing Machinery"},{"issue":"5","key":"32_CR2","doi-asserted-by":"crossref","first-page":"410","DOI":"10.26421\/QIC2.5-7","volume":"2","author":"S. Aaronson","year":"2002","unstructured":"Aaronson, S.: Book review: A new kind of science. Quantum Information and Computation\u00a02(5), 410\u2013423 (2002)","journal-title":"Quantum Information and Computation"},{"key":"32_CR3","unstructured":"Baiocchi, C.: 3N+1, UTM e tag-system. Technical Report Pubblicazione 98\/38, Dipartimento di Matematico, Universit\u00e0 di Roma (1998) (in Italian)"},{"key":"32_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/3-540-45132-3_1","volume-title":"Machines, Computations, and Universality","author":"C. Baiocchi","year":"2001","unstructured":"Baiocchi, C.: Three Small Universal Turing Machines. In: Margenstern, M., Rogozhin, Y. (eds.) MCU 2001. LNCS, vol.\u00a02055, pp. 1\u201310. Springer, Heidelberg (2001)"},{"issue":"6","key":"32_CR5","doi-asserted-by":"publisher","first-page":"525","DOI":"10.1147\/rd.176.0525","volume":"17","author":"C.H. Bennett","year":"1973","unstructured":"Bennett, C.H.: Logical reversibility of computation. IBM Journal of Research and Development\u00a017(6), 525\u2013532 (1973)","journal-title":"IBM Journal of Research and Development"},{"issue":"163","key":"32_CR6","first-page":"647","volume":"40","author":"A.H. Brady","year":"1983","unstructured":"Brady, A.H.: The determination of the value of Rado\u2019s noncomputable function \u03a3(k) for four-state Turing machines. Mathematics of Computation\u00a040(163), 647\u2013665 (1983)","journal-title":"Mathematics of Computation"},{"key":"32_CR7","doi-asserted-by":"crossref","unstructured":"Brady, A.H.: The busy beaver game and the meaning of life. In: Herken, R. (ed.) The Universal Turing Machine: A Half-Century Survey, pp. 259\u2013277. Oxford University Press (1988)","DOI":"10.1093\/oso\/9780198537748.003.0009"},{"issue":"1","key":"32_CR8","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1145\/321203.321206","volume":"11","author":"J. Cocke","year":"1964","unstructured":"Cocke, J., Minsky, M.: Universality of tag systems with P\u2009=\u20092. Journal of the Association for Computing Machinery\u00a011(1), 15\u201320 (1964)","journal-title":"Journal of the Association for Computing Machinery"},{"issue":"1","key":"32_CR9","doi-asserted-by":"crossref","first-page":"1","DOI":"10.25088\/ComplexSystems.15.1.1","volume":"15","author":"M. Cook","year":"2004","unstructured":"Cook, M.: Universality in elementary cellular automata. Complex Systems\u00a015(1), 1\u201340 (2004)","journal-title":"Complex Systems"},{"key":"32_CR10","doi-asserted-by":"publisher","first-page":"31","DOI":"10.4204\/EPTCS.1.4","volume":"1","author":"M. Cook","year":"2009","unstructured":"Cook, M.: A Concrete View of Rule 110 Computation. Electronic Proceedings in Theoretical Computer Science\u00a01, 31\u201355 (2009)","journal-title":"Electronic Proceedings in Theoretical Computer Science"},{"key":"32_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"170","DOI":"10.1007\/978-3-540-74593-8_15","volume-title":"Machines, Computations, and Universality","author":"L. Mol De","year":"2007","unstructured":"De Mol, L.: Study of Limits of Solvability in Tag Systems. In: Durand-Lose, J., Margenstern, M. (eds.) MCU 2007. LNCS, vol.\u00a04664, pp. 170\u2013181. Springer, Heidelberg (2007)"},{"issue":"4","key":"32_CR12","doi-asserted-by":"publisher","first-page":"570","DOI":"10.1145\/321296.321308","volume":"12","author":"P.C. Fischer","year":"1965","unstructured":"Fischer, P.C.: On formalisms for Turing machines. Journal of the Association for Computing Machinery\u00a012(4), 570\u2013580 (1965)","journal-title":"Journal of the Association for Computing Machinery"},{"issue":"3","key":"32_CR13","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1007\/BF01694011","volume":"2","author":"P.C. Fischer","year":"1968","unstructured":"Fischer, P.C., Meyer, A.R., Rosenberg, A.L.: Counter machines and counter languages. Mathematical Systems Theory\u00a02(3), 265\u2013283 (1968)","journal-title":"Mathematical Systems Theory"},{"issue":"3","key":"32_CR14","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1145\/321127.321129","volume":"9","author":"J. Friedman","year":"1962","unstructured":"Friedman, J.: A decision procedure for computations of finite automata. Journal of the ACM\u00a09(3), 315\u2013323 (1962)","journal-title":"Journal of the ACM"},{"key":"32_CR15","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1016\/S0166-218X(00)00334-6","volume":"117","author":"A. Gajardo","year":"2002","unstructured":"Gajardo, A., Moreira, A., Goles, E.: Complexity of Langton\u2019s ant. Discrete Applied Mathematics\u00a0117, 41\u201350 (2002)","journal-title":"Discrete Applied Mathematics"},{"key":"32_CR16","doi-asserted-by":"crossref","unstructured":"Green, M.W.: A lower bound on Rado\u2019s sigma function for binary Turing machines. In: Proceedings of the 5th IEEE Annual Symposium on Switching Circuit Theory and Logical Design, pp. 91\u201394 (1964)","DOI":"10.1109\/SWCT.1964.3"},{"key":"32_CR17","doi-asserted-by":"crossref","DOI":"10.1093\/oso\/9780195085914.001.0001","volume-title":"Limits to parallel computation: P-completeness theory","author":"R. Greenlaw","year":"1995","unstructured":"Greenlaw, R., Hoover, H.J., Ruzzo, W.L.: Limits to parallel computation: P-completeness theory. Oxford university Press, Oxford (1995)"},{"key":"32_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1007\/11493785_13","volume-title":"DNA Computing","author":"T. Harju","year":"2005","unstructured":"Harju, T., Margenstern, M.: Splicing Systems for Universal Turing Machines. In: Ferretti, C., Mauri, G., Zandron, C. (eds.) DNA 2004. LNCS, vol.\u00a03384, pp. 149\u2013158. Springer, Heidelberg (2005)"},{"key":"32_CR19","doi-asserted-by":"publisher","first-page":"368","DOI":"10.1109\/SWAT.1968.36","volume-title":"Proceedings of the Ninth Annual Symposium on Switching and Automata Theory (FOCS)","author":"G.T. Hermann","year":"1968","unstructured":"Hermann, G.T.: The uniform halting problem for generalized one state Turing machines. In: Proceedings of the Ninth Annual Symposium on Switching and Automata Theory (FOCS), pp. 368\u2013372. IEEE Computer Society Press, Schenectady (1968)"},{"issue":"7-12","key":"32_CR20","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1002\/malq.19680140706","volume":"14","author":"G.T. Hermann","year":"1968","unstructured":"Hermann, G.T.: The halting problem of one state Turing machines with n-dimensional tape. Mathematical Logic Quarterly\u00a014(7-12), 185\u2013191 (1968)","journal-title":"Mathematical Logic Quarterly"},{"key":"32_CR21","unstructured":"Hooper, P.: Some small, multitape universal Turing machines. Technical report, Computation Laboratory, Harvard University, Cambridge, Massachusetts (1963)"},{"issue":"2","key":"32_CR22","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1016\/0020-0255(69)90017-6","volume":"1","author":"P. Hooper","year":"1969","unstructured":"Hooper, P.: Some small, multitape universal Turing machines. Information Sciences\u00a01(2), 205\u2013215 (1969)","journal-title":"Information Sciences"},{"key":"32_CR23","unstructured":"Ikeno, N.: A 6-symbol 10-state universal Turing machine. In: Proceedings, Institute of Electrical Communications, Tokyo (1958)"},{"key":"32_CR24","unstructured":"Kleine-B\u00fcning, H.: \u00dcber probleme bei homogener Parkettierung von \u2124\u00d7\u2124 durch Mealy-automaten bei normierter verwendung. PhD thesis, Institut f\u00fcr Mathematische Logik, M\u00fcnster (1977)"},{"issue":"4-5","key":"32_CR25","first-page":"179","volume":"13","author":"H. Kleine-B\u00fcning","year":"1977","unstructured":"Kleine-B\u00fcning, H., Ottmann, T.: Kleine universelle mehrdimensionale Turingmaschinen. Elektronische Informationsverarbeitung und Kybernetik\u00a013(4-5), 179\u2013201 (1977) (in German)","journal-title":"Elektronische Informationsverarbeitung und Kybernetik"},{"issue":"2","key":"32_CR26","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1016\/S0304-3975(96)00078-3","volume":"168","author":"M. Kudlek","year":"1996","unstructured":"Kudlek, M.: Small deterministic Turing machines. Theoretical Computer Science\u00a0168(2), 241\u2013255 (1996)","journal-title":"Theoretical Computer Science"},{"key":"32_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1007\/3-540-46011-X_27","volume-title":"Developments in Language Theory","author":"M. Kudlek","year":"2002","unstructured":"Kudlek, M., Rogozhin, Y.: A Universal Turing Machine with 3 States and 9 Symbols. In: Kuich, W., Rozenberg, G., Salomaa, A. (eds.) DLT 2001. LNCS, vol.\u00a02295, pp. 311\u2013318. Springer, Heidelberg (2002)"},{"key":"32_CR28","series-title":"Lecture Notes in Computer Science","first-page":"219","volume-title":"Computation and Logic in the Real World","author":"G. Lafitte","year":"2007","unstructured":"Lafitte, G., Papazian, C.: The Fabric of Small Turing Machines. In: Cooper, S.B., L\u00f6we, B., Sorbi, A. (eds.) CiE 2007. LNCS, vol.\u00a04497, pp. 219\u2013227. Springer, Heidelberg (2007)"},{"issue":"1-3","key":"32_CR29","doi-asserted-by":"publisher","first-page":"120","DOI":"10.1016\/0167-2789(86)90237-X","volume":"2","author":"C. Langton","year":"1986","unstructured":"Langton, C.: Studying artificial life with cellular automata. Physica D\u00a02(1-3), 120\u2013149 (1986)","journal-title":"Physica D"},{"issue":"2","key":"32_CR30","doi-asserted-by":"publisher","first-page":"196","DOI":"10.1145\/321264.321270","volume":"12","author":"S. Lin","year":"1965","unstructured":"Lin, S., Rado, T.: Computer studies of Turing machine problems. Journal of the ACM\u00a012(2), 196\u2013212 (1965)","journal-title":"Journal of the ACM"},{"issue":"3","key":"32_CR31","first-page":"299","volume":"4","author":"K. Lindgren","year":"1990","unstructured":"Lindgren, K., Nordahl, M.G.: Universal computation in simple one-dimensional cellular automata. Complex Systems\u00a04(3), 299\u2013318 (1990)","journal-title":"Complex Systems"},{"key":"32_CR32","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1016\/j.entcs.2008.12.075","volume":"225","author":"M. Margenstern","year":"2009","unstructured":"Margenstern, M.: Surprising areas in the quest for small universal devices. Electronic Notes in Theoretical computer Science\u00a0225, 201\u2013220 (2009)","journal-title":"Electronic Notes in Theoretical computer Science"},{"key":"32_CR33","unstructured":"Margenstern, M.: Sur la fronti\u00e8re entre machines de Turing \u00e1 arr\u00eat d\u00e9cidable et machines de Turing universelles. Technical Report 92-83, LITP Institut Blaise Pascal (1992)"},{"key":"32_CR34","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"375","DOI":"10.1007\/3-540-57163-9_32","volume-title":"Fundamentals of Computation Theory","author":"M. Margenstern","year":"1993","unstructured":"Margenstern, M.: Non-erasing Turing Machines: A Frontier Between a Decidable Halting Problem and Universality. In: \u00c9sik, Z. (ed.) FCT 1993. LNCS, vol.\u00a0710, pp. 375\u2013385. Springer, Heidelberg (1993)"},{"key":"32_CR35","unstructured":"Margenstern, M.: Une machine de Turing universelle sur {0,1}, non-effa\u00e7ante et \u00e0 trois instructions gauches. Technical Report 94-08, LITP Institut Blaise Pascal (1994)"},{"key":"32_CR36","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"386","DOI":"10.1007\/3-540-59175-3_104","volume-title":"LATIN \u201995: Theoretical Informatics","author":"M. Margenstern","year":"1995","unstructured":"Margenstern, M.: Non-Erasing Turing Machines: A New Frontier Between a Decidable Halting Problem and Universality. In: Baeza-Yates, R.A., Poblete, P.V., Goles, E. (eds.) LATIN 1995. LNCS, vol.\u00a0911, pp. 386\u2013397. Springer, Heidelberg (1995)"},{"key":"32_CR37","first-page":"101","volume":"320","author":"M. Margenstern","year":"1995","unstructured":"Margenstern, M.: Une machine de Turing universelle non-effa\u00e7ante \u00e0 exactement trois instructions gauches. C. R. Acad. Sci. Paris, S\u00e9rie I\u00a0320, 101\u2013106 (1995)","journal-title":"C. R. Acad. Sci. Paris, S\u00e9rie I"},{"key":"32_CR38","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"226","DOI":"10.1007\/3-540-63045-7_23","volume-title":"Logical Foundations of Computer Science","author":"M. Margenstern","year":"1997","unstructured":"Margenstern, M.: Decidability and Undecidability of the Halting Problem on Turing Machines, a Survey. In: Adian, S., Nerode, A. (eds.) LFCS 1997. LNCS, vol.\u00a01234, pp. 226\u2013236. Springer, Heidelberg (1997)"},{"issue":"2","key":"32_CR39","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1051\/ita\/1997310201591","volume":"31","author":"M. Margenstern","year":"1997","unstructured":"Margenstern, M.: The laterality problem for non-erasing Turing machines on {0, 1} is completely solved. Theoretical Informatics and Applications\u00a031(2), 159\u2013204 (1997)","journal-title":"Theoretical Informatics and Applications"},{"key":"32_CR40","unstructured":"Margenstern, M.: Frontier between decidability and undecidability: a survey. In: Margenstern, M. (ed.) Machines, Computations, and Universality (MCU), France, vol.\u00a01, pp. 141\u2013177 (1998)"},{"issue":"2","key":"32_CR41","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1016\/S0304-3975(99)00102-4","volume":"231","author":"M. Margenstern","year":"2000","unstructured":"Margenstern, M.: Frontier between decidability and undecidability: a survey. Theoretical Computer Science\u00a0231(2), 217\u2013251 (2000)","journal-title":"Theoretical Computer Science"},{"issue":"1-2","key":"32_CR42","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1016\/S0304-3975(00)00114-6","volume":"257","author":"M. Margenstern","year":"2001","unstructured":"Margenstern, M.: On quasi-unilateral universal Turing machines. Theoretical Computer Science\u00a0257(1-2), 153\u2013166 (2001)","journal-title":"Theoretical Computer Science"},{"key":"32_CR43","unstructured":"Margenstern, M.: An algorithm for building intrinsically universal cellular automata in hyperbolic spaces. In: Proceedings of the 2006 International Conference on Foundations of Computer Science (FCS), Las Vegas, NV, pp. 3\u20139. CSREA Press (2006)"},{"key":"32_CR44","first-page":"1395","volume":"320","author":"M. Margenstern","year":"1995","unstructured":"Margenstern, M., Pavlotskaya, L.: Deux machines de Turing universelles\u00e1 au plus deux instructions gauches. C. R. Acad. Sci. Paris, S\u00e9rie I\u00a0320, 1395\u20131400 (1995)","journal-title":"C. R. Acad. Sci. Paris, S\u00e9rie I"},{"key":"32_CR45","unstructured":"Margenstern, M., Pavlotskaya, L.: Vers ue nouvelle approche de l\u2019universalit\u00e9 concernant les machines de Turing. Technical Report 95-58, LITP Institut Blaise Pascal (1995)"},{"issue":"2","key":"32_CR46","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1142\/S0218196703001262","volume":"13","author":"M. Margenstern","year":"2003","unstructured":"Margenstern, M., Pavlotskaya, L.: On the optimal number of instructions for universality of Turing machines connected with a finite automaton. International Journal of Algebra and Computation\u00a013(2), 133\u2013202 (2003)","journal-title":"International Journal of Algebra and Computation"},{"key":"32_CR47","first-page":"247","volume":"40","author":"H. Marxen","year":"1990","unstructured":"Marxen, H., Buntrock, J.: Attacking the Busy Beaver 5. Bulletin of the EATCS\u00a040, 247\u2013251 (1990)","journal-title":"Bulletin of the EATCS"},{"issue":"5","key":"32_CR48","doi-asserted-by":"publisher","first-page":"351","DOI":"10.1007\/BF01409968","volume":"32","author":"P. Michel","year":"1993","unstructured":"Michel, P.: Busy beaver competition and Collatz-like problems. Archive Mathematical Logic\u00a032(5), 351\u2013367 (1993)","journal-title":"Archive Mathematical Logic"},{"key":"32_CR49","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1016\/j.tcs.2004.05.008","volume":"326","author":"P. Michel","year":"2004","unstructured":"Michel, P.: Small Turing machines and generalized busy beaver competition. Theoretical Computer Science\u00a0326, 45\u201356 (2004)","journal-title":"Theoretical Computer Science"},{"key":"32_CR50","unstructured":"Michel, P.: The busy beaver competition: a historical survey, arXiv:0906.3749v2 (2010), http:\/\/www.logique.jussieu.fr\/~michel\/ha.html"},{"key":"32_CR51","unstructured":"Minsky, M.: A 6-symbol 7-state universal Turing machines. Technical Report 54-G-027, MIT (1960)"},{"key":"32_CR52","unstructured":"Minsky, M.: Recursive unsolvability of Post\u2019s tag problem. Technical Report 54-G-023, Massachusetts Institute of Technology (1960)"},{"issue":"3","key":"32_CR53","doi-asserted-by":"publisher","first-page":"437","DOI":"10.2307\/1970290","volume":"74","author":"M. Minsky","year":"1961","unstructured":"Minsky, M.: Recursive unsolvability of Post\u2019s problem of \u201ctag\u201d and other topics in theory of Turing machines. Annals of Mathematics\u00a074(3), 437\u2013455 (1961)","journal-title":"Annals of Mathematics"},{"key":"32_CR54","doi-asserted-by":"crossref","unstructured":"Minsky, M.: Size and structure of universal Turing machines using tag systems. In: Recursive Function Theory: Proceedings, Symposium in Pure Mathematics, Provelence, vol.\u00a05, pp. 229\u2013238 (1962)","DOI":"10.1090\/pspum\/005\/0142452"},{"key":"32_CR55","volume-title":"AIM-33, A.I. memo 33, Computer Science and Artificial Intelligence Laboratory","author":"M. Minsky","year":"1962","unstructured":"Minsky, M.: Universality of (p=2) tag systems and a 4 symbol 7 state universal Turing machine. In: AIM-33, A.I. memo 33, Computer Science and Artificial Intelligence Laboratory. MIT, Cambridge (1962)"},{"key":"32_CR56","volume-title":"Computation, finite and infinite machines","author":"M. Minsky","year":"1967","unstructured":"Minsky, M.: Computation, finite and infinite machines. Prentice-Hall, Englewood Cliffs (1967)"},{"key":"32_CR57","doi-asserted-by":"crossref","unstructured":"Moore, C., Mertens, S.: The Nature of Computation. Oxford University Press (2011)","DOI":"10.1093\/acprof:oso\/9780199233212.001.0001"},{"key":"32_CR58","doi-asserted-by":"publisher","first-page":"100","DOI":"10.1016\/S0167-2789(96)00255-2","volume":"103","author":"C. Moore","year":"1997","unstructured":"Moore, C.: Quasi-linear cellular automata. Physica D\u00a0103, 100\u2013132 (1997)","journal-title":"Physica D"},{"key":"32_CR59","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1016\/S0167-2789(97)80003-6","volume":"111","author":"C. Moore","year":"1998","unstructured":"Moore, C.: Predicting non-linear cellular automata quickly by decomposing them into linear ones. Physica D\u00a0111, 27\u201341 (1998)","journal-title":"Physica D"},{"key":"32_CR60","doi-asserted-by":"crossref","unstructured":"Moore, E.F.: A simplified universal Turing machine. In: ACM National Meeting, Toronto, Canada, pp. 50\u201354. ACM Press (1952)","DOI":"10.1145\/800259.808993"},{"key":"32_CR61","unstructured":"Morita, K., Shirasaki, A., Gono, Y.: A 1-tape 2-symbol reversible Turing machine. The Transactions of the IEICE Japan\u00a0E72(3), 223\u2013228 (1989)"},{"key":"32_CR62","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"90","DOI":"10.1007\/978-3-540-74593-8_8","volume-title":"Machines, Computations, and Universality","author":"K. Morita","year":"2007","unstructured":"Morita, K., Yamaguchi, Y.: A Universal Reversible Turing Machine. In: Durand-Lose, J., Margenstern, M. (eds.) MCU 2007. LNCS, vol.\u00a04664, pp. 90\u201398. Springer, Heidelberg (2007)"},{"key":"32_CR63","doi-asserted-by":"crossref","unstructured":"Neary, T.: Small universal Turing machines. PhD thesis, National University of Ireland, Maynooth (2008)","DOI":"10.1007\/978-3-642-03409-1_24"},{"key":"32_CR64","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"132","DOI":"10.1007\/11786986_13","volume-title":"Automata, Languages and Programming","author":"T. Neary","year":"2006","unstructured":"Neary, T., Woods, D.: P-Completeness of Cellular Automaton Rule 110. In: Bugliesi, M., Preneel, B., Sassone, V., Wegener, I. (eds.) ICALP 2006, Part I. LNCS, vol.\u00a04051, pp. 132\u2013143. Springer, Heidelberg (2006)"},{"issue":"1-3","key":"32_CR65","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1016\/j.tcs.2006.06.002","volume":"362","author":"T. Neary","year":"2006","unstructured":"Neary, T., Woods, D.: Small fast universal Turing machines. Theoretical Computer Science\u00a0362(1-3), 171\u2013195 (2006)","journal-title":"Theoretical Computer Science"},{"key":"32_CR66","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"242","DOI":"10.1007\/978-3-540-74593-8_21","volume-title":"Machines, Computations, and Universality","author":"T. Neary","year":"2007","unstructured":"Neary, T., Woods, D.: Four Small Universal Turing Machines. In: Durand-Lose, J., Margenstern, M. (eds.) MCU 2007. LNCS, vol.\u00a04664, pp. 242\u2013254. Springer, Heidelberg (2007)"},{"key":"32_CR67","doi-asserted-by":"crossref","unstructured":"Neary, T., Woods, D.: Small weakly universal Turing machines, arXiv:0707.4489v1 [cs.CC] (2007)","DOI":"10.1016\/j.tcs.2006.06.002"},{"key":"32_CR68","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"262","DOI":"10.1007\/978-3-642-03409-1_24","volume-title":"Fundamentals of Computation Theory","author":"T. Neary","year":"2009","unstructured":"Neary, T., Woods, D.: Small Weakly Universal Turing Machines. In: Kuty\u0142owski, M., Charatonik, W., G\u0119bala, M. (eds.) FCT 2009. LNCS, vol.\u00a05699, pp. 262\u2013273. Springer, Heidelberg (2009)"},{"issue":"1","key":"32_CR69","doi-asserted-by":"crossref","first-page":"123","DOI":"10.3233\/FI-2009-0036","volume":"91","author":"T. Neary","year":"2009","unstructured":"Neary, T., Woods, D.: Four small universal Turing machines. Fundamenta Informaticae\u00a091(1), 123\u2013144 (2009)","journal-title":"Fundamenta Informaticae"},{"issue":"1","key":"32_CR70","first-page":"29","volume":"5","author":"A. Nozaki","year":"1969","unstructured":"Nozaki, A.: On the notion of universality of Turing machine. Kybernetika Academia Praha\u00a05(1), 29\u201343 (1969) (English translated version)","journal-title":"Kybernetika Academia Praha"},{"key":"32_CR71","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"318","DOI":"10.1007\/3-540-45465-9_28","volume-title":"Automata, Languages and Programming","author":"N. Ollinger","year":"2002","unstructured":"Ollinger, N.: The Quest for Small Universal Cellular Automata. In: Widmayer, P., Triguero, F., Morales, R., Hennessy, M., Eidenbenz, S., Conejo, R. (eds.) ICALP 2002. LNCS, vol.\u00a02380, pp. 318\u2013329. Springer, Heidelberg (2002)"},{"issue":"1-2","key":"32_CR72","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1016\/j.tcs.2010.08.018","volume":"412","author":"N. Ollinger","year":"2011","unstructured":"Ollinger, N., Richard, G.: Four states are enough? Theoretical Computer Science\u00a0412(1-2), 22\u201332 (2011)","journal-title":"Theoretical Computer Science"},{"issue":"1-2","key":"32_CR73","first-page":"27","volume":"11","author":"T. Ottmann","year":"1975","unstructured":"Ottmann, T.: Eine universelle Turingmaschine mit zweidimensionalem band. Elektronische Informationsverarbeitung und Kybernetik\u00a011(1-2), 27\u201338 (1975) (in German)","journal-title":"Elektronische Informationsverarbeitung und Kybernetik"},{"key":"32_CR74","unstructured":"Ottmann, T.: Einfache universelle mehrdimensionale Turingmaschinen. Habilitationsschrift, Karlsruhe (1975)"},{"key":"32_CR75","doi-asserted-by":"crossref","unstructured":"Pavlotskaya, L.: Solvability of the halting problem for certain classes of Turing machines. Mathematical Notes\u00a013(6), 537\u2013541; Translated from Matematicheskie Zametki, 13(6), 899\u2013909 (1973)","DOI":"10.1007\/BF01163965"},{"key":"32_CR76","first-page":"52","volume":"27","author":"L. Pavlotskaya","year":"1975","unstructured":"Pavlotskaya, L.: O minimal\u2019nom chisle razlichnykh kodov vershin v grafe universal\u2019noj mashiny T\u2019juringa. Disketnyj Analiz, Sbornik Trudov Instituta Matematiki SO AN SSSR\u00a027, 52\u201360 (1975); On the minimal number of distinct codes for the vertices of the graph of a universal Turing machine (in Russian)","journal-title":"Disketnyj Analiz, Sbornik Trudov Instituta Matematiki SO AN SSSR"},{"key":"32_CR77","unstructured":"Pavlotskaya, L.: Dostatochnye uslovija razreshimosti problemy ostanovki dlja mashin T\u2019juring. Avtomaty i Mashiny, 91\u2013118 (1978); Sufficient conditions for the halting problem decidability of Turing machines (in Russian)"},{"issue":"2","key":"32_CR78","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1016\/S0304-3975(96)00079-5","volume":"168","author":"L. Pavlotskaya","year":"1996","unstructured":"Pavlotskaya, L.: On machines, universal by extensions. Theoretical Computer Science\u00a0168(2), 257\u2013266 (1996)","journal-title":"Theoretical Computer Science"},{"issue":"2","key":"32_CR79","doi-asserted-by":"publisher","first-page":"197","DOI":"10.2307\/2371809","volume":"65","author":"E.L. Post","year":"1943","unstructured":"Post, E.L.: Formal reductions of the general combinatorial decision problem. American Journal of Mathmatics\u00a065(2), 197\u2013215 (1943)","journal-title":"American Journal of Mathmatics"},{"issue":"1","key":"32_CR80","doi-asserted-by":"publisher","first-page":"1","DOI":"10.2307\/2267170","volume":"12","author":"E.L. Post","year":"1947","unstructured":"Post, E.L.: Recursive unsolvability of a problem of Thue. Journal of Symbolic Logic\u00a012(1), 1\u201311 (1947)","journal-title":"Journal of Symbolic Logic"},{"key":"#cr-split#-32_CR81.1","unstructured":"Post, E.L.: Absolutely unsolvable problems and relatively undecidable propositions - account of an anticipation. In: Davis, M. (ed.) The Undecidable: Basic Papers on Undecidable Propositions, Unsolvable Problems and Computable Functions, pp. 340-406. Raven Press, New York (1965)"},{"key":"#cr-split#-32_CR81.2","unstructured":"Corrected republication. Dover publications, New York (2004)"},{"issue":"4","key":"32_CR82","doi-asserted-by":"publisher","first-page":"508","DOI":"10.1137\/0208041","volume":"8","author":"L. Priese","year":"1979","unstructured":"Priese, L.: Towards a precise characterization of the complexity of universal and nonuniversal Turing machines. SIAM J. Comput.\u00a08(4), 508\u2013523 (1979)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"32_CR83","doi-asserted-by":"publisher","first-page":"877","DOI":"10.1002\/j.1538-7305.1962.tb00480.x","volume":"41","author":"T. Rado","year":"1962","unstructured":"Rado, T.: On non-computable functions. Bell System Technical Journal\u00a041(3), 877\u2013884 (1962)","journal-title":"Bell System Technical Journal"},{"key":"32_CR84","unstructured":"Richard, G.: A particular universal cellular automaton, HAL research report (oai:hal.archives-ouvertes.fr:hal-00095821_v1) (2006)"},{"issue":"3","key":"32_CR85","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1007\/BF01418780","volume":"12","author":"R.M. Robinson","year":"1971","unstructured":"Robinson, R.M.: Undecidability and nonperiodicity for tilings of the plane. Inventiones Mathematicae\u00a012(3), 177\u2013209 (1971)","journal-title":"Inventiones Mathematicae"},{"issue":"5","key":"32_CR86","doi-asserted-by":"publisher","first-page":"551","DOI":"10.1142\/S0129167X91000302","volume":"2","author":"R.M. Robinson","year":"1991","unstructured":"Robinson, R.M.: Minsky\u2019s small universal Turing machine. International Journal of Mathematics\u00a02(5), 551\u2013562 (1991)","journal-title":"International Journal of Mathematics"},{"key":"32_CR87","unstructured":"Rogozhin, Y.: Sem\u2019 universal\u2019nykh mashin T\u2019juringa. In: Fifth All Union Conference on Mathematical Logic, Akad. Naul SSSR. Otdel. Inst. Mat., Novosibirsk, p. 27 (1979); Seven universal Turing machines (in russian)"},{"key":"32_CR88","unstructured":"Rogozhin, Y.: Sem\u2019 universal\u2019nykh mashin T\u2019juringa. Systems and Theoretical Programming, Mat.\u00a0Issled\u00a069, 76\u201390 (1982); Seven universal Turing machines (in Russian)"},{"key":"32_CR89","unstructured":"Rogozhin, Y.: Universal\u2019naja mashina T\u2019juringa s 10\u00a0sostojanijami i 3\u00a0simvolami. Izvestiya Akademii Nauk Respubliki Moldova, Matematika\u00a04(10), 80\u201382 (1992); A universal Turing machine with 10 states and 3 symbols (in Russian)"},{"issue":"3","key":"32_CR90","first-page":"108","volume":"1","author":"Y. Rogozhin","year":"1993","unstructured":"Rogozhin, Y.: About Shannon\u2019s problem for Turing machines. Computer Science Journal of Moldova\u00a01(3), 108\u2013111 (1993)","journal-title":"Computer Science Journal of Moldova"},{"issue":"2","key":"32_CR91","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1016\/S0304-3975(96)00077-1","volume":"168","author":"Y. Rogozhin","year":"1996","unstructured":"Rogozhin, Y.: Small universal Turing machines. Theoretical Computer Science\u00a0168(2), 215\u2013240 (1996)","journal-title":"Theoretical Computer Science"},{"issue":"3","key":"32_CR92","first-page":"259","volume":"1","author":"Y. Rogozhin","year":"1998","unstructured":"Rogozhin, Y.: A universal Turing machine with 22 states and 2 symbols. Romanian Journal of Information Science and Technology\u00a01(3), 259\u2013265 (1998) (in Russian)","journal-title":"Romanian Journal of Information Science and Technology"},{"key":"32_CR93","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"356","DOI":"10.1007\/11603047_24","volume-title":"Membrane Computing","author":"Y. Rogozhin","year":"2006","unstructured":"Rogozhin, Y., Verlan, S.: On the Rule Complexity of Universal Tissue P Systems. In: Freund, R., P\u0103un, G., Rozenberg, G., Salomaa, A. (eds.) WMC 2005. LNCS, vol.\u00a03850, pp. 356\u2013362. Springer, Heidelberg (2006)"},{"key":"32_CR94","doi-asserted-by":"crossref","unstructured":"Rothemund, P.W.K.: A DNA and restriction enzyme implementation of Turing Machines. In: Lipton, R.J., Baum, E.B. (eds.) DNA Based Computers: Proceeding of a DIMACS Workshop. DIMACS, vol.\u00a02055, pp. 75\u2013119. Princeton University, AMS (1996)","DOI":"10.1090\/dimacs\/027\/06"},{"key":"32_CR95","first-page":"157","volume":"34","author":"C.E. Shannon","year":"1956","unstructured":"Shannon, C.E.: A universal Turing machine with two internal states. Automata Studies, Annals of Mathematics Studies\u00a034, 157\u2013165 (1956)","journal-title":"Automata Studies, Annals of Mathematics Studies"},{"issue":"4-5","key":"32_CR96","doi-asserted-by":"publisher","first-page":"593","DOI":"10.1016\/S0893-6080(99)00025-8","volume":"12","author":"H.T. Siegelmann","year":"1999","unstructured":"Siegelmann, H.T., Margenstern, M.: Nine switch-affine neurons suffice for Turing universality. Neural Networks\u00a012(4-5), 593\u2013600 (1999)","journal-title":"Neural Networks"},{"key":"32_CR97","unstructured":"Schroeppel, R.: A two counter machine cannot calculate 2n. Technical Report AIM-257, A.I. memo 257, Computer Science and Artificial Intelligence Laboratory, MIT, Cambridge, MA (1972)"},{"key":"32_CR98","unstructured":"Takahashi, H.: Keisankikai II. Iwanami, Tokyo (1958); Computing machine II (in Japanese)"},{"issue":"42","key":"32_CR99","first-page":"230","volume":"2","author":"A.M. Turing","year":"1936","unstructured":"Turing, A.M.: On computable numbers, with an application to the Entscheidungsproblem. Proceedings of the London Mathematical Society\u00a02(42), 230\u2013265 (1936)","journal-title":"Proceedings of the London Mathematical Society"},{"key":"32_CR100","unstructured":"Wagner, K.: Universelle Turingmaschinen mit n-dimensionale band. Elektronische Informationsverarbeitung und Kybernetik\u00a09(7-8), 423\u2013431 (1973); Universal Turing machines with n-dimensional tapes (in German)"},{"issue":"1","key":"32_CR101","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1145\/320856.320867","volume":"4","author":"H. Wang","year":"1957","unstructured":"Wang, H.: A variant to Turing\u2019s theory of computing machines. Journal of the Association for Computing Machinery\u00a04(1), 63\u201392 (1957)","journal-title":"Journal of the Association for Computing Machinery"},{"issue":"4","key":"32_CR102","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1007\/BF01343730","volume":"152","author":"H. Wang","year":"1963","unstructured":"Wang, H.: Tag systems and lag systems. Mathematical Annals\u00a0152(4), 65\u201374 (1963)","journal-title":"Mathematical Annals"},{"key":"32_CR103","unstructured":"Watanabe, S.: On a minimal universal Turing machine. Technical report, MCB Report, Tokyo (1960)"},{"issue":"4","key":"32_CR104","doi-asserted-by":"publisher","first-page":"476","DOI":"10.1145\/321088.321090","volume":"8","author":"S. Watanabe","year":"1961","unstructured":"Watanabe, S.: 5-symbol 8-state and 5-symbol 6-state universal Turing machines. Journal of the ACM\u00a08(4), 476\u2013483 (1961)","journal-title":"Journal of the ACM"},{"issue":"9","key":"32_CR105","first-page":"588","volume":"13","author":"S. Watanabe","year":"1972","unstructured":"Watanabe, S.: 4-symbol 5-state universal Turing machine. Information Processing Society of Japan Magazine\u00a013(9), 588\u2013592 (1972)","journal-title":"Information Processing Society of Japan Magazine"},{"issue":"3","key":"32_CR106","doi-asserted-by":"publisher","first-page":"601","DOI":"10.1103\/RevModPhys.55.601","volume":"55","author":"S. Wolfram","year":"1983","unstructured":"Wolfram, S.: Statistical mechanics of cellular automata. Reviews of Modern Physics\u00a055(3), 601\u2013644 (1983)","journal-title":"Reviews of Modern Physics"},{"key":"32_CR107","unstructured":"Wolfram, S.: A new kind of science. Wolfram Media, Inc. (2002)"},{"key":"32_CR108","first-page":"439","volume-title":"47th Annual IEEE Symposium on Foundations of Computer Science (FOCS)","author":"D. Woods","year":"2006","unstructured":"Woods, D., Neary, T.: On the time complexity of 2-tag systems and small universal Turing machines. In: 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 439\u2013446. IEEE, Berkeley (2006)"},{"key":"32_CR109","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1007\/978-3-540-74593-8_26","volume-title":"Machines, Computations, and Universality","author":"D. Woods","year":"2007","unstructured":"Woods, D., Neary, T.: Small Semi-Weakly Universal Turing Machines. In: Durand-Lose, J., Margenstern, M. (eds.) MCU 2007. LNCS, vol.\u00a04664, pp. 303\u2013315. Springer, Heidelberg (2007)"},{"issue":"4-5","key":"32_CR110","doi-asserted-by":"publisher","first-page":"443","DOI":"10.1016\/j.tcs.2008.09.051","volume":"410","author":"D. Woods","year":"2009","unstructured":"Woods, D., Neary, T.: The complexity of small universal Turing machines: A survey. Theoretical Computer Science\u00a0410(4-5), 443\u2013450 (2009)","journal-title":"Theoretical Computer Science"},{"issue":"1","key":"32_CR111","doi-asserted-by":"crossref","first-page":"179","DOI":"10.3233\/FI-2009-0039","volume":"91","author":"D. Woods","year":"2009","unstructured":"Woods, D., Neary, T.: Small semi-weakly universal Turing machines. Fundamenta Informaticae\u00a091(1), 179\u2013195 (2009)","journal-title":"Fundamenta Informaticae"}],"container-title":["Lecture Notes in Computer Science","SOFSEM 2012: Theory and Practice of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-27660-6_32","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,18]],"date-time":"2025-03-18T21:49:56Z","timestamp":1742334596000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-27660-6_32"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642276590","9783642276606"],"references-count":112,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-27660-6_32","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}