{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,28]],"date-time":"2025-05-28T10:10:02Z","timestamp":1748427002044,"version":"3.41.0"},"publisher-location":"Berlin, Heidelberg","reference-count":41,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662472200"},{"type":"electronic","value":"9783662472217"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-662-47221-7_2","type":"book-chapter","created":{"date-parts":[[2015,6,4]],"date-time":"2015-06-04T05:37:49Z","timestamp":1433396269000},"page":"11-16","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Tag Systems and the Complexity of Simple Programs"],"prefix":"10.1007","author":[{"given":"Turlough","family":"Neary","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Damien","family":"Woods","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,6,4]]},"reference":[{"key":"2_CR1","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. 2055, pp. 1\u201310. Springer, Heidelberg (2001)"},{"issue":"1\u20132","key":"2_CR2","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1016\/S0304-3975(98)00029-2","volume":"204","author":"J Cassaigne","year":"1998","unstructured":"Cassaigne, J., Karhum\u00e4ki, J.: Examples of undecidable problems for 2-generator matrix semigroups. Theoretical Computer Science 204(1\u20132), 29\u201334 (1998)","journal-title":"Theoretical Computer Science"},{"issue":"1","key":"2_CR3","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 = 2$$ . Journal of the Association for Computing Machinery 11(1), 15\u201320 (1964)","journal-title":"Journal of the Association for Computing Machinery"},{"issue":"1","key":"2_CR4","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 15(1), 1\u201340 (2004)","journal-title":"Complex Systems"},{"issue":"1","key":"2_CR5","doi-asserted-by":"publisher","first-page":"92","DOI":"10.1016\/j.tcs.2007.10.020","volume":"390","author":"L Mol De","year":"2008","unstructured":"De Mol, L.: Tag systems and Collatz-like functions. Theoretical Computer Science 390(1), 92\u2013101 (2008)","journal-title":"Theoretical Computer Science"},{"issue":"1\u20132","key":"2_CR6","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1016\/j.tcs.2010.08.026","volume":"412","author":"L Mol De","year":"2011","unstructured":"De Mol, L.: On the complex behavior of simple tag systems - an experimental approach. Theoretical Computer Science 412(1\u20132), 97\u2013112 (2011)","journal-title":"Theoretical Computer Science"},{"issue":"2","key":"2_CR7","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1016\/0304-3975(89)90080-7","volume":"21","author":"A Ehrenfeucht","year":"1982","unstructured":"Ehrenfeucht, A., Karhum\u00e4ki, J., Rozenberg, G.: The (generalized) Post correspondence problem with lists consisting of two words is decidable. Theoretical Computer Science 21(2), 119\u2013144 (1982)","journal-title":"Theoretical Computer Science"},{"issue":"7","key":"2_CR8","doi-asserted-by":"publisher","first-page":"649","DOI":"10.2307\/2695274","volume":"108","author":"V Halava","year":"2001","unstructured":"Halava, V., Harju, T.: Mortality in matrix semigroups. American Mathematical Monthly 108(7), 649\u2013653 (2001)","journal-title":"American Mathematical Monthly"},{"issue":"5","key":"2_CR9","doi-asserted-by":"publisher","first-page":"931","DOI":"10.1142\/S0129054107005066","volume":"18","author":"V Halava","year":"2007","unstructured":"Halava, V., Harju, T., Hirvensalo, M.: Undecidability bounds for integer matrices using Claus instances. International Journal of Foundations of Computer Science 18(5), 931\u2013948 (2007)","journal-title":"International Journal of Foundations of Computer Science"},{"key":"2_CR10","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. 3384, pp. 149\u2013158. Springer, Heidelberg (2005)"},{"key":"2_CR11","doi-asserted-by":"crossref","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, New York, Oct. 1968","DOI":"10.1109\/SWAT.1968.36"},{"issue":"2","key":"2_CR12","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 1(2), 205\u2013215 (1969)","journal-title":"Information Sciences"},{"issue":"2","key":"2_CR13","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 168(2), 241\u2013255 (1996)","journal-title":"Theoretical Computer Science"},{"key":"2_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"149","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. 2295, pp. 149\u2013158. Springer, Heidelberg (2002)"},{"issue":"3","key":"2_CR15","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 4(3), 299\u2013318 (1990)","journal-title":"Complex Systems"},{"key":"2_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"386","DOI":"10.1007\/3-540-59175-3_104","volume-title":"LATIN","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. LNCS, vol. 911, pp. 386\u2013397. Springer, Heidelberg (1995)"},{"issue":"2","key":"2_CR17","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 231(2), 217\u2013251 (2000)","journal-title":"Theoretical Computer Science"},{"issue":"1","key":"2_CR18","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1016\/j.tcs.2004.09.016","volume":"330","author":"Y Matiyasevich","year":"2005","unstructured":"Matiyasevich, Y., S\u00e9nizergues, G.: Decision problems for semi-Thue systems with a few rules. Theoretical Computer Science 330(1), 145\u2013169 (2005)","journal-title":"Theoretical Computer Science"},{"issue":"3","key":"2_CR19","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\" and other topics in theory of Turing machines. Annals of Mathematics 74(3), 437\u2013455 (1961)","journal-title":"Annals of Mathematics"},{"key":"2_CR20","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, vol. 5, pp. 229\u2013238, AMS, Provelence (1962)","DOI":"10.1090\/pspum\/005\/0142452"},{"key":"2_CR21","doi-asserted-by":"crossref","unstructured":"Neary, T.: Small universal Turing machines. Ph.D thesis, National University of Ireland, Maynooth (2008)","DOI":"10.1007\/978-3-642-03409-1_24"},{"key":"2_CR22","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. LNCS, vol. 4051, pp. 132\u2013143. Springer, Heidelberg (2006)"},{"issue":"1\u20133","key":"2_CR23","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 362(1\u20133), 171\u2013195 (2006)","journal-title":"Theoretical Computer Science"},{"key":"2_CR24","unstructured":"Neary, T.: Undecidability in binary tag systems and the Post correspondence problem for five pairs of words. In: Mayr, Ernst W., Ollinger, Nicolas (eds.) 32nd International Symposium on Theoretical Aspects of Computer Science, (STACS 2015), vol. 30 of LIPIcs, pp. 649\u2013661 (2015)"},{"key":"2_CR25","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. 5699, pp. 262\u2013273. Springer, Heidelberg (2009)"},{"issue":"1","key":"2_CR26","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 91(1), 123\u2013144 (2009)","journal-title":"Fundamenta Informaticae"},{"key":"2_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1007\/978-3-642-27660-6_32","volume-title":"SOFSEM 2012: Theory and Practice of Computer Science","author":"T Neary","year":"2012","unstructured":"Neary, T., Woods, D.: The complexity of small universal turing machines: a survey. In: Bielikov\u00e1, M., Friedrich, G., Gottlob, G., Katzenbeisser, S., Tur\u00e1n, G. (eds.) SOFSEM 2012. LNCS, vol. 7147, pp. 385\u2013405. Springer, Heidelberg (2012)"},{"issue":"6","key":"2_CR28","doi-asserted-by":"publisher","first-page":"537","DOI":"10.1007\/BF01163965","volume":"13","author":"L Pavlotskaya","year":"1973","unstructured":"Pavlotskaya, L.: Solvability of the halting problem for certain classes of Turing machines. Mathematical Notes (Springer) 13(6), 537\u2013541 (1973). (Translated from Matematicheskie Zametki, Vol. 13, No. 6, pp. 899\u2013909, June, 1973)","journal-title":"Mathematical Notes (Springer)"},{"key":"2_CR29","unstructured":"Pavlotskaya, L.: Dostatochnye uslovija razreshimosti problemy ostanovki dlja mashin T\u2019juring. Avtomaty i Mashiny, pp. 91\u2013118 (1978). (Sufficient conditions for the halting problem decidability of Turing machines. In Russian)"},{"issue":"2","key":"2_CR30","doi-asserted-by":"publisher","first-page":"197","DOI":"10.2307\/2371809","volume":"65","author":"EL Post","year":"1943","unstructured":"Post, E.L.: Formal reductions of the general combinatorial decision problem. American Journal of Mathmatics 65(2), 197\u2013215 (1943)","journal-title":"American Journal of Mathmatics"},{"key":"2_CR31","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, pages 340\u2013406. Raven Press, New York (1965). (Corrected republication, Dover publications, New York, 2004)"},{"issue":"2","key":"2_CR32","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 168(2), 215\u2013240 (1996)","journal-title":"Theoretical Computer Science"},{"key":"2_CR33","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. 3850, pp. 356\u2013362. Springer, Heidelberg (2006)"},{"key":"2_CR34","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, vol. 2055 of DIMACS, pp. 75\u2013119. AMS, Princeton University (1996)","DOI":"10.1090\/dimacs\/027\/06"},{"key":"2_CR35","first-page":"157","volume":"34","author":"CE Shannon","year":"1956","unstructured":"Shannon, C.E.: A universal Turing machine with two internal states. Automata Studies, Annals of Mathematics Studies 34, 157\u2013165 (1956)","journal-title":"Automata Studies, Annals of Mathematics Studies"},{"issue":"4\u20135","key":"2_CR36","doi-asserted-by":"publisher","first-page":"593","DOI":"10.1016\/S0893-6080(99)00025-8","volume":"12","author":"HT Siegelmann","year":"1999","unstructured":"Siegelmann, H.T., Margenstern, M.: Nine switch-affine neurons suffice for Turing universality. Neural Networks 12(4\u20135), 593\u2013600 (1999)","journal-title":"Neural Networks"},{"issue":"4","key":"2_CR37","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 152(4), 65\u201374 (1963)","journal-title":"Mathematical Annals"},{"issue":"9","key":"2_CR38","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 13(9), 588\u2013592 (1972)","journal-title":"Information Processing Society of Japan Magazine"},{"key":"2_CR39","unstructured":"Wolfram, S.: A new kind of science. Wolfram Media Inc (2002)"},{"key":"2_CR40","doi-asserted-by":"crossref","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, California, Oct. 2006","DOI":"10.1109\/FOCS.2006.58"},{"issue":"1","key":"2_CR41","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 91(1), 179\u2013195 (2009)","journal-title":"Fundamenta Informaticae"}],"container-title":["Lecture Notes in Computer Science","Cellular Automata and Discrete Complex Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-47221-7_2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,28]],"date-time":"2025-05-28T09:31:29Z","timestamp":1748424689000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-47221-7_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783662472200","9783662472217"],"references-count":41,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-47221-7_2","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"4 June 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}