{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,19]],"date-time":"2026-03-19T20:37:34Z","timestamp":1773952654085,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":13,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642308697","type":"print"},{"value":"9783642308703","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-30870-3_12","type":"book-chapter","created":{"date-parts":[[2012,5,27]],"date-time":"2012-05-27T22:56:12Z","timestamp":1338159372000},"page":"107-117","source":"Crossref","is-referenced-by-count":3,"title":["An Undecidable Nested Recurrence Relation"],"prefix":"10.1007","author":[{"given":"Marcel","family":"Celaya","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Frank","family":"Ruskey","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"12_CR1","doi-asserted-by":"crossref","unstructured":"Allouche, J.P., Shallit, J.: A variant of Hofstadter\u2019s sequence and finite automata. arXiv:1103.1133v2 (2011)","DOI":"10.1017\/S1446788713000074"},{"key":"12_CR2","first-page":"29","volume":"10","author":"B. Balamohan","year":"2007","unstructured":"Balamohan, B., Kuznetsov, A., Tanny, S.: On the behavior of a variant of Hofstadter\u2019s Q-sequence. J. Integer Sequences\u00a010, 29 pages (2007)","journal-title":"J. Integer Sequences"},{"issue":"1","key":"12_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\u2009=\u20092. J. ACM\u00a011(1), 15\u201320 (1964)","journal-title":"J. ACM"},{"key":"12_CR4","unstructured":"Conway, J.H.: Unpredictable iterations. In: Proceedings of the 1972 Number Theory Confernence, pp. 49\u201352 (August 1972)"},{"issue":"1","key":"12_CR5","first-page":"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"},{"issue":"4","key":"12_CR6","first-page":"310","volume":"22","author":"P.J. Downey","year":"1984","unstructured":"Downey, P.J., Griswold, R.E.: On a family of nested recurrences. Fibonacci Quarterly\u00a022(4), 310\u2013317 (1984)","journal-title":"Fibonacci Quarterly"},{"key":"12_CR7","unstructured":"Golomb, S.: Discrete chaos: sequences satisfying \u201cstrange\u201d recursions (1991) (preprint)"},{"key":"12_CR8","unstructured":"Hofstadter, D.R.: G\u00f6del, Escher, Bach: An Eternal Golden Braid. Basic Books (1979)"},{"issue":"1","key":"12_CR9","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1016\/0012-365X(94)00303-Z","volume":"152","author":"T. Kubo","year":"1996","unstructured":"Kubo, T., Vakil, R.: On Conway\u2019s recursive sequence. Discrete Mathematics\u00a0152(1), 225\u2013252 (1996)","journal-title":"Discrete Mathematics"},{"issue":"3","key":"12_CR10","doi-asserted-by":"publisher","first-page":"437","DOI":"10.2307\/1970290","volume":"74","author":"M.L. Minsky","year":"1961","unstructured":"Minsky, M.L.: Recursive unsolvability of Post\u2019s problem of \u201dTag\u201d and other topics in theory of Turing machines. The Annals of Mathematics\u00a074(3), 437\u2013455 (1961)","journal-title":"The Annals of Mathematics"},{"issue":"2","key":"12_CR11","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 Mathematics\u00a065(2), 197\u2013215 (1943)","journal-title":"American Journal of Mathematics"},{"issue":"3","key":"12_CR12","first-page":"227","volume":"49","author":"F. Ruskey","year":"2011","unstructured":"Ruskey, F.: Fibonacci meets Hofstadter. Fibonacci Quarterly\u00a049(3), 227\u2013230 (2011)","journal-title":"Fibonacci Quarterly"},{"key":"12_CR13","doi-asserted-by":"crossref","unstructured":"Smith, A.R.: Simple computation-universal cellular spaces and self-reproduction. In: IEEE Conference Record of the 9th Annual Symposium on Switching and Automata Theory 1968, pp. 269\u2013277 (October 1968)","DOI":"10.1109\/SWAT.1968.25"}],"container-title":["Lecture Notes in Computer Science","How the World Computes"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-30870-3_12.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,23]],"date-time":"2020-11-23T22:06:54Z","timestamp":1606169214000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-30870-3_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642308697","9783642308703"],"references-count":13,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-30870-3_12","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012]]}}}