{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,28]],"date-time":"2025-03-28T00:02:28Z","timestamp":1743120148275,"version":"3.40.3"},"publisher-location":"Cham","reference-count":27,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030617387"},{"type":"electronic","value":"9783030617394"}],"license":[{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"content-version":"vor","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":[[2020]]},"DOI":"10.1007\/978-3-030-61739-4_9","type":"book-chapter","created":{"date-parts":[[2020,10,14]],"date-time":"2020-10-14T23:14:46Z","timestamp":1602717286000},"page":"131-147","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["The Collatz Process Embeds a Base Conversion Algorithm"],"prefix":"10.1007","author":[{"given":"Tristan","family":"St\u00e9rin","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":[[2020,10,15]]},"reference":[{"key":"9_CR1","doi-asserted-by":"publisher","unstructured":"Adamczewski, B., Bugeaud, Y.: On the complexity of algebraic numbers I. Expansions in integer bases. Ann. Math. 165(2), 547\u2013565 (2007). \nhttps:\/\/doi.org\/10.4007\/annals.2007.165.547","DOI":"10.4007\/annals.2007.165.547"},{"key":"9_CR2","unstructured":"Adamczewski, B., Faverjon, C.: Mahler\u2019s method in several variables II: Applications to base change problems and finite automata, September 2018. \nhttps:\/\/arxiv.org\/abs\/1809.04826"},{"key":"9_CR3","unstructured":"Bruschi, M.: Two cellular automata for the 3x+1 map (2005). \nhttps:\/\/arxiv.org\/abs\/nlin\/0502061"},{"key":"9_CR4","unstructured":"Capco, J.: Odd Collatz sequence and binary representations, March 2019. \nhttps:\/\/hal.archives-ouvertes.fr\/hal-02062503"},{"key":"9_CR5","unstructured":"Caruso, X.: Computations with p-adic numbers. Journ\u00e9es Nationales de Calcul Formel. Les cours du CIRM (2018). \nhttps:\/\/hal.archives-ouvertes.fr\/hal-01444183"},{"issue":"2","key":"9_CR6","first-page":"349","volume":"1","author":"T Cloney","year":"1987","unstructured":"Cloney, T., Goles, E., Vichniac, G.Y.: The $$3x+1$$ problem: a quasi cellular automaton. Complex Syst. 1(2), 349\u2013360 (1987)","journal-title":"Complex Syst."},{"issue":"2","key":"9_CR7","first-page":"349","volume":"1","author":"T Cloney","year":"1987","unstructured":"Cloney, T., Goles, E., Vichniac, G.Y.: The $$3x+1$$ problem: a quasi cellular automaton. Complex Syst. 1(2), 349\u2013360 (1987)","journal-title":"Complex Syst."},{"key":"9_CR8","unstructured":"Conway, J.: Unpredictable iterations. In: Number Theory Conference (1972)"},{"key":"9_CR9","unstructured":"Goles, E., Ollinger, N., Theyssier, G.: Introducing freezing cellular automata. In: Exploratory Papers of Cellular Automata and Discrete Complex Systems (AUTOMATA 2015), pp. 65\u201373 (2015)"},{"issue":"4","key":"9_CR10","doi-asserted-by":"publisher","first-page":"695","DOI":"10.1016\/S0022-0000(02)00025-9","volume":"65","author":"W Hesse","year":"2002","unstructured":"Hesse, W., Allender, E., Barrington, D.A.M.: Uniform constant-depth threshold circuits for division and iterated multiplication. J. Comput. Syst. Sci. 65(4), 695\u2013716 (2002)","journal-title":"J. Comput. Syst. Sci."},{"key":"9_CR11","doi-asserted-by":"publisher","unstructured":"Hew, P.C.: Working in binary protects the repetends of 1\/3$${}^{\\text{h}}$$: comment on Colussi\u2019s \u2018The convergence classes of Collatz function\u2019. Theor. Comput. Sci. 618, 135\u2013141 (2016). \nhttps:\/\/doi.org\/10.1016\/j.tcs.2015.12.033","DOI":"10.1016\/j.tcs.2015.12.033"},{"key":"9_CR12","doi-asserted-by":"publisher","unstructured":"Jakobsen, S.K., Simonsen, J.G.: Liouville numbers and the computational complexity of changing bases. In: Anselmo, M., Della Vedova, G., Manea, F., Pauly, A. (eds.) Beyond the Horizon of Computability. CiE 2020. Lecture Notes in Computer Science, vol. 12098, pp. 50\u201362. Springer, Cham (2020). \nhttps:\/\/doi.org\/10.1007\/978-3-030-51466-2_5","DOI":"10.1007\/978-3-030-51466-2_5"},{"key":"9_CR13","doi-asserted-by":"publisher","unstructured":"Kari, J.: Cellular automata, the Collatz conjecture and powers of 3\/2. In: Yen, H.C., Ibarra, O.H. (eds.) Developments in Language Theory. DLT 2012. Lecture Notes in Computer Science, vol. 7410, pp. 40\u201349. Springer, Heidelberg (2012). \nhttps:\/\/doi.org\/10.1007\/978-3-642-31653-1_5","DOI":"10.1007\/978-3-642-31653-1_5"},{"issue":"1","key":"9_CR14","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1016\/s0304-3975(98)00117-0","volume":"210","author":"P Koiran","year":"1999","unstructured":"Koiran, P., Moore, C.: Closed-form analytic maps in one and two dimensions can simulate universal turing machines. Theoret. Comput. Sci. 210(1), 217\u2013223 (1999). \nhttps:\/\/doi.org\/10.1016\/s0304-3975(98)00117-0","journal-title":"Theoret. Comput. Sci."},{"issue":"5","key":"9_CR15","first-page":"547","volume":"42","author":"I Korec","year":"1992","unstructured":"Korec, I.: The $$3x+1$$ problem, generalized pascal triangles and cellular automata. Mathematica Slovaca 42(5), 547\u2013563 (1992). \nhttp:\/\/eudml.org\/doc\/32424","journal-title":"Mathematica Slovaca"},{"key":"9_CR16","doi-asserted-by":"publisher","unstructured":"Kurtz, S.A., Simon, J.: The undecidability of the generalized Collatz Problem. In: Cai, J.Y., Cooper, S.B., Zhu, H. (eds.) Theory and Applications of Models of Computation. TAMC 2007. Lecture Notes in Computer Science, vol. 4484, pp. 542\u2013553. Springer, Heidelberg (2007). \nhttps:\/\/doi.org\/10.1007\/978-3-540-72504-6_49","DOI":"10.1007\/978-3-540-72504-6_49"},{"key":"9_CR17","unstructured":"Lagarias, J.C.: The $$3x + 1$$ problem and its generalizations. Am. Math. Mon. 92(1), 3\u201323 (1985). \nhttp:\/\/www.jstor.org\/stable\/2322189"},{"key":"9_CR18","volume-title":"Computation: Finite and Infinite Machines","author":"M Minsky","year":"1967","unstructured":"Minsky, M.: Computation: Finite and Infinite Machines. Prentice Hall Inc., Engelwood Cliffs (1967)"},{"issue":"1\u20133","key":"9_CR19","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1016\/s0012-365x(03)00125-0","volume":"275","author":"KG Monks","year":"2004","unstructured":"Monks, K.G., Yazinski, J.: The autoconjugacy of the 3x+1 function. Discrete Math. 275(1\u20133), 219\u2013236 (2004). \nhttps:\/\/doi.org\/10.1016\/s0012-365x(03)00125-0","journal-title":"Discrete Math."},{"issue":"20","key":"9_CR20","doi-asserted-by":"publisher","first-page":"2354","DOI":"10.1103\/PhysRevLett.64.2354","volume":"64","author":"C Moore","year":"1990","unstructured":"Moore, C.: Unpredictability and undecidability in dynamical systems. Phys. Rev. Lett. 64(20), 2354 (1990)","journal-title":"Phys. Rev. Lett."},{"issue":"2","key":"9_CR21","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1088\/0951-7715\/4\/2\/002","volume":"4","author":"C Moore","year":"1991","unstructured":"Moore, C.: Generalized shifts: unpredictability and undecidability in dynamical systems. Nonlinearity 4(2), 199 (1991)","journal-title":"Nonlinearity"},{"key":"9_CR22","doi-asserted-by":"crossref","unstructured":"Moore, C., Mertens, S.: The Nature of Computation. Oxford University Press, Oxford (2011)","DOI":"10.1093\/acprof:oso\/9780199233212.001.0001"},{"key":"9_CR23","first-page":"A8","volume":"19","author":"O Rozier","year":"2019","unstructured":"Rozier, O.: Parity sequences of the 3x+1 map on the 2-adic integers and Euclidean embedding. Integers 19, A8 (2019)","journal-title":"Integers"},{"key":"9_CR24","first-page":"182","volume":"46","author":"J Shallit","year":"1992","unstructured":"Shallit, J., Wilson, D.A.: The \u201c3x + 1\u201d problem and finite automata. Bull. EATCS 46, 182\u2013185 (1992)","journal-title":"Bull. EATCS"},{"key":"9_CR25","unstructured":"St\u00e9rin, T.: Binary expression of ancestors in the Collatz graph. In: Schmitz, S., Potapov, I. (eds.) 14th International Conference on Reachability Problems. LNCS, Springer (2020). (To appear). \nhttps:\/\/arxiv.org\/abs\/1907.00775v4"},{"key":"9_CR26","unstructured":"St\u00e9rin, T., Woods, D.: The Collatz process embeds a base conversion algorithm (2020). Expanded version. \nhttps:\/\/arxiv.org\/abs\/2007.06979v3"},{"key":"9_CR27","doi-asserted-by":"publisher","unstructured":"Vollmar, R.: On cellular automata with a finite number of state changes. In: Kn\u00f6del, W., Schneider, H.J. (eds.) Parallel Processes and Related Automata\/Parallele Prozesse und damit zusammenh\u00e4ngende Automaten. Computing Supplementum, vol. 3, pp. 181\u2013191. Springer, Vienna (1981). \nhttps:\/\/doi.org\/10.1007\/978-3-7091-8596-4_13","DOI":"10.1007\/978-3-7091-8596-4_13"}],"container-title":["Lecture Notes in Computer Science","Reachability Problems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-61739-4_9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,10,14]],"date-time":"2020-10-14T23:15:21Z","timestamp":1602717321000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-030-61739-4_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020]]},"ISBN":["9783030617387","9783030617394"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-61739-4_9","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2020]]},"assertion":[{"value":"15 October 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"RP","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Reachability Problems","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Paris","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"France","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2020","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"19 October 2020","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"21 October 2020","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"14","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"rp2020","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/www.irif.fr\/~rp2020\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}