MURAL - Maynooth University Research Archive Library

    The Collatz Process Embeds a Base Conversion Algorithm

    Sterin, Tristan and Woods, Damien (2020) The Collatz Process Embeds a Base Conversion Algorithm. Lecture Notes in Computer Science. pp. 131-147. ISSN 0302-9743

    Download (833kB) | Preview

    Share your research

    Twitter Facebook LinkedIn GooglePlus Email more...

    Add this article to your Mendeley library


    The Collatz process is defined on natural numbers by iterating the map T(x)=T0(x)=x/2 when x∈N is even and T(x)=T1(x)=(3x+1)/2 when x is odd. In an effort to understand its dynamics, and since Generalised Collatz Maps are known to simulate Turing Machines [Conway, 1972], it seems natural to ask what kinds of algorithmic behaviours it embeds. We define a quasi-cellular automaton that exactly simulates the Collatz process on the square grid: on input x∈N , written horizontally in base 2, successive rows give the Collatz sequence of x in base 2. We show that vertical columns simultaneously iterate the map in base 3. This leads to our main result: the Collatz process embeds an algorithm that converts any natural number from base 3 to base 2. We also find that the evolution of our automaton computes the parity of the number of 1s in any ternary input. It follows that predicting about half of the bits of the iterates Ti(x) , for i=O(logx) , is in the complexity class NC 1 but outside AC 0 . These results show that the Collatz process is capable of some simple, but non-trivial, computation in bases 2 and 3, suggesting an algorithmic approach to thinking about prediction and existence of cycles in the Collatz process.

    Item Type: Article
    Keywords: Collatz map; Model of computation; Reachability problem;
    Academic Unit: Assisting Living & Learning,ALL institute
    Faculty of Science and Engineering > Electronic Engineering
    Faculty of Science and Engineering > Research Institutes > Hamilton Institute
    Item ID: 15714
    Identification Number:
    Depositing User: Damien Woods
    Date Deposited: 22 Mar 2022 14:52
    Journal or Publication Title: Lecture Notes in Computer Science
    Publisher: Springer Nature
    Refereed: Yes
    Use Licence: This item is available under a Creative Commons Attribution Non Commercial Share Alike Licence (CC BY-NC-SA). Details of this licence are available here

    Repository Staff Only(login required)

    View Item Item control page


    Downloads per month over past year

    Origin of downloads