10 Conclusion
By interpreting Turing machine tapes as binary numbers, we have defined a class of integer sequences—binary step sequences—that directly reflect the locality and mechanical constraints of computation. We have provided a complete and rigorous characterization for all finite sequences of this type. The central open problem remains the characterization of TM-generable infinite sequences, which we conjecture is a proper subset of all infinite binary step sequences. We hope this work opens new avenues for analyzing computational processes through the lens of number theory, suggesting a deeper structure underlying the seemingly unpredictable behavior of Turing machines.
- 1
J.-P. Allouche and J. Shallit. Automatic Sequences: Theory, Applications, Generalizations. Cambridge University Press, 2003.
- 2
H. Marxen and J. Buntrock. Attacking the Busy Beaver 5. Bulletin of the EATCS, 40:247–251, 1990.
- 3
P. Michel. Problems in number theory from busy beaver competition. arXiv:1311.1029, 2015.
- 4
P. Michel. The Busy Beaver Competition: A historical survey. arXiv:0906.3749v2, 2017.
- 5
J. Shallit. The Logical Approach to Automatic Sequences. Cambridge University Press, 2022.
- 6
A. M. Turing. On computable numbers, with an application to the Entscheidungsproblem. Proceedings of the London Mathematical Society, 42(2):230–265, 1936.