Comment by LegionMammal978
3 years ago
On the contrary, 36 of its 60 bits are dedicated to goto labels. Although you're right that TMs cannot "call" a state then "return" to the caller, as would be expected from a reusable function. Regardless, for busy beaver purposes, most of TMs' state tends to be encoded in the tape rather than the state graph, so I suspect it's the differences in the means of data manipulation that create such a gap. (E.g., with substitution, you can easily move a term across an arbitrary amount of garbage.)
No comments yet
Contribute on Hacker News ↗