← Back to context

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.)