An Automated Approach to the Collatz Conjecture
An Automated Approach to the Collatz Conjecture
复制标题
Collatz 猜想的自动化方法
DOI：
10.1007/s10817-022-09658-8
复制
发表时间：
2023
期刊：
影响因子：
--
通讯作者：
Heule, Marijn J. H.
中科院分区：
文献类型：
--
作者：
Yolcu, Emre;Aaronson, Scott;Heule, Marijn J. H.
我们通过弦重写终止的透镜来研究Collatz猜想及其变体。我们构建了一个重写系统，模拟迭代应用Collatz函数对应的混合二元-三元表示的正整数字符串。这个重写系统的终止等价于Collatz猜想。为了显示我们的方法在证明数学上有趣的语句的可行性，我们实现了一个最小的终止证明，使用矩阵/北极解释的自动化方法，我们进行实验，我们获得证明的非平凡的削弱Collatz猜想。最后，我们适应我们的重写系统，以表明数学中的其他开放问题也可以接近相对较小的重写系统的终止问题。虽然我们没有成功地证明Collatz猜想，我们相信，这里的想法代表了一个有趣的新方法。
We explore the Collatz conjecture and its variants through the lens of termination of string rewriting. We construct a rewriting system that simulates the iterated application of the Collatz function on strings corresponding to mixed binary–ternary representations of positive integers. Termination of this rewriting system is equivalent to the Collatz conjecture. To show the feasibility of our approach in proving mathematically interesting statements, we implement a minimal termination prover that uses the automated method of matrix/arctic interpretations and we perform experiments where we obtain proofs of nontrivial weakenings of the Collatz conjecture. Finally, we adapt our rewriting system to show that other open problems in mathematics can also be approached as termination problems for relatively small rewriting systems. Although we do not succeed in proving the Collatz conjecture, we believe that the ideas here represent an interesting new approach.
登录
查看更多内容
3x 1 问题注释参考书目
DOI：
--
发表时间：
--
期刊：
影响因子：
--
作者：
BibliographyJ. C. LagariasAT;T. L. Park
通讯作者：
T. L. Park
可满足性求解器的轻量级组件缓存方案
DOI：
--
发表时间：
2007
期刊：
International Conference on Theory and Applications of Satisfiability Testing
影响因子：
--
作者：
Knot Pipatsrisawat;Adnan Darwiche
通讯作者：
Adnan Darwiche
DOI：
--
发表时间：
1985
期刊：
影响因子：
--
作者：
Daniel A. Rawsthorne
通讯作者：
Daniel A. Rawsthorne
非交换有理级数及其应用
影响因子：
1.7
作者：
J. Berstel;C. Reutenauer
通讯作者：
C. Reutenauer
Matchbox：用于匹配限制字符串重写的工具
DOI：
--
发表时间：
2004
期刊：
International Conference on Rewriting Techniques and Applications
影响因子：
--
作者：
Johannes Waldmann
通讯作者：
Johannes Waldmann