ω-rewriting the Collatz problem

• Autorzy: Scollo G.
• Języki publikacji: EN

Abstrakty

EN

The Collatz problem is comprised of two distinct, separate questions: existence of eventually periodic Collatz reductions with a nontrivial period, and existence of period-free Collatz reductions. This paper introduces a few distinct, related formalizations of the Collatz dynamics as term rewriting systems, using elementary concepts from the theory of state transition dynamics. Some of the subject systems act on finite terms, whereas others rewrite terms that are endowed with a countable, recursively defined structure. The latter presents a convenient framework for the investigation of extensions of the Collatz dynamics to dense systems.

Słowa kluczowe

EN

state transition dynamics; attractor; periodicity; quasiperiodicity; infinitary rewriting

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2005
• Tom: Vol. 64, nr 1-4
• Strony: 405--416
• Opis fizyczny: Bibliogr. 9 poz.

Twórcy

autor

Scollo G.

• Universita di Verona, Dipartimento di Informatica, Ca' Vignal 2, Strada Le Grazie, 15-37134 Verona, Italy,

Bibliografia

• [1] I. Bethke, J. W. Klop, and R. de Vrijer. Descendants and origins in term rewriting. Information and Computation, 159:59–124, 2000.
• [2] R. Kennaway. Infinitary rewriting and cyclic graphs. Electronic Notes in Theoretical Computer Science, 2, 2000.
• [3] R. Kennaway, J. W. Klop, R. Sleep, and F.-J. de Vries. Transfinite reductions in orthogonal term rewriting systems. Information and Computation, 119(1):18–38, 1995.
• [4] J. Lagarias. The 3x+1 problem and its generalizations. American Mathematical Monthly, 92:3–23, 1985.
• [5] V. Manca, G. Franco, and G. Scollo. State transition dynamics: basic concepts and molecular computing perspectives. In M. Gheorghe and M. Holcombe, editors, Molecular Computational Models: Unconventional Approaches. Idea Group, Hershey, PA, USA, 2004.
• [6] S. Marcus. Quasiperiodic infinite words. Bull. of the EATCS, 82:170–174, 2004.
• [7] S. Marcus and G. Paun. Infinite (almost periodic) words, formal languages and dynamical systems. Bull. Of the EATCS, 54:224–231, 1994.
• [8] R. Terra. A stopping time problem on the positive integers. Acta Arith., 30:241–252, 1976.
• [9] R. Terra. On the existence of a density. Acta Arith., 35:101–102, 1979.