4 ms·
Generally, when we talk about the halting problem in the Busy Beaver context, we're talking about the halting problem starting from an empty tape. However, some
by LegionMammal978 3y ago
Generally, when we talk about the halting problem in the Busy Beaver context, we're talking about the halting problem starting from an empty tape. However, some authors have analyzed the behavior of Turing machines on certain classes of infinite tapes. For instance, in [0], the authors surveyed the behavior of TMs starting on a tape with an arbitrary word in the middle, and an infinitely repeating word on one or both sides; one finding is that no 2-state 2-symbol TM is a universal Turing machine, for any of these input tapes.
[0] https://arxiv.org/abs/1110.2230 https://arxiv.org/abs/1110.2230