论文标题
Collatz过程嵌入了基本转换算法
The Collatz process embeds a base conversion algorithm
论文作者
论文摘要
Collatz进程是通过迭代地图$ t（x）= t_0（x）= x/2 $来定义的，当$ x \ in \ mathbb {n} $均匀而$ t（x）= t_1（x）=（x）=（x）=（3x+1）/2 $时，$ x $是奇数时。为了理解其动力学，并且已知广义的Collatz地图可以模拟Turing机器[Conway，1972]，因此询问它嵌入的算法行为是自然的。我们定义了一个准细胞自动机，可以准确模拟平方网格上的collatz过程：在\ mathbb {n} $中的输入$ x \上，水平写在基数2中，连续的行会在基本2中的collatz序列$ x $在基本2中的collatz序列。我们显示了同步的基础图中的垂直柱子。将任何自然数量从基本3转换为基数2。我们还发现，自动机的演变计算出任何三元输入中1s的奇偶校验。因此，预测迭代$ t^i（x）$的一半，对于$ i = o（\ log x）$，都在复杂性类NC $^1 $中，但在AC $^0 $之外。最后，我们表明，在将Collatz过程扩展到具有无限二进制扩展（$ 2 $ -ADIC整数）的数字[Lagarias，1985]时，我们的自动机将环环Collatz猜想描述为自然可及性问题。这些结果表明，Collatz过程能够在基本2和3中进行一些简单但不平凡的计算，这表明在Collatz过程中对周期的存在，预测和结构进行思考的算法方法。
The Collatz process is defined on natural numbers by iterating the map $T(x) = T_0(x) = x/2$ when $x\in\mathbb{N}$ is even and $T(x)=T_1(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\in\mathbb{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 $T^i(x)$, for $i = O(\log x)$, is in the complexity class NC$^1$ but outside AC$^0$. Finally, we show that in the extension of the Collatz process to numbers with infinite binary expansions ($2$-adic integers) [Lagarias, 1985], our automaton encodes the cyclic Collatz conjecture as a natural reachability problem. 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 existence, prediction and structure of cycles in the Collatz process.
