{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:59:58Z","timestamp":1750309198679,"version":"3.41.0"},"publisher-location":"Cham","reference-count":13,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319602516"},{"type":"electronic","value":"9783319602523"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"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":[[2017]]},"DOI":"10.1007\/978-3-319-60252-3_22","type":"book-chapter","created":{"date-parts":[[2017,6,2]],"date-time":"2017-06-02T14:59:13Z","timestamp":1496415553000},"page":"274-286","source":"Crossref","is-referenced-by-count":1,"title":["2-State 2-Symbol Turing Machines with Periodic Support Produce Regular Sets"],"prefix":"10.1007","author":[{"given":"Turlough","family":"Neary","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,6,3]]},"reference":[{"key":"22_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). doi: 10.1007\/3-540-45132-3_1"},{"issue":"1","key":"22_CR2","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 Syst. 15(1), 1\u201340 (2004)","journal-title":"Complex Syst."},{"key":"22_CR3","doi-asserted-by":"crossref","unstructured":"Hermann, G.: The uniform halting problem for generalized one state Turing machines. In: Proceedings, Ninth Annual Symposium on Switching and Automata Theory (FOCS), pp. 368\u2013372. IEEE Computer Society Press, October 1968","DOI":"10.1109\/SWAT.1968.36"},{"issue":"2","key":"22_CR4","doi-asserted-by":"crossref","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. TCS 168(2), 241\u2013255 (1996)","journal-title":"TCS"},{"key":"22_CR5","doi-asserted-by":"crossref","unstructured":"Minsky, M.: Size and structure of universal Turing machines using tag systems. In: Recursive Function Theory, Symposium in Pure Mathematics, vol. 5, pp. 229\u2013238 (1962)","DOI":"10.1090\/pspum\/005\/0142452"},{"issue":"1","key":"22_CR6","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. Fundam. Inform. 91(1), 123\u2013144 (2009)","journal-title":"Fundam. Inform."},{"key":"22_CR7","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). doi: 10.1007\/978-3-642-03409-1_24"},{"key":"22_CR8","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). doi: 10.1007\/978-3-642-27660-6_32"},{"issue":"6","key":"22_CR9","doi-asserted-by":"crossref","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. Math. Notes (Springer) 13(6), 537\u2013541 (1973)","journal-title":"Math. Notes (Springer)"},{"key":"22_CR10","unstructured":"Pavlotskaya, L.: Dostatochnye uslovija razreshimosti problemy ostanovki dlja mashin T\u2019juring. Problemi kibernetiki, pp. 91\u2013118 (1978). (in Russian)"},{"issue":"2","key":"22_CR11","doi-asserted-by":"crossref","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. TCS 168(2), 215\u2013240 (1996)","journal-title":"TCS"},{"issue":"7\u20138","key":"22_CR12","first-page":"423","volume":"9","author":"K Wagner","year":"1973","unstructured":"Wagner, K.: Universelle Turingmaschinen mit n-dimensionale band. Elektronische Informationsverarbeitung und Kybernetik 9(7\u20138), 423\u2013431 (1973)","journal-title":"Elektronische Informationsverarbeitung und Kybernetik"},{"issue":"4","key":"22_CR13","doi-asserted-by":"crossref","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. J. ACM 8(4), 476\u2013483 (1961)","journal-title":"J. ACM"}],"container-title":["Lecture Notes in Computer Science","Descriptional Complexity of Formal Systems"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-60252-3_22","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T23:10:23Z","timestamp":1750288223000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-60252-3_22"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319602516","9783319602523"],"references-count":13,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-60252-3_22","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2017]]}}}