Integer Sequences from Turing Machine Tapes

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.