zlacker

[parent] [thread] 1 comments
1. tadfis+(OP)[view] [source] 2023-04-24 01:37:56
One thing that comes to mind is function application, which begets recursion. This is the last quarter of the example program's encoding, while the example TM has enough space for 6 states and no concept of a "goto" or "jmp" that would simulate recursion.
replies(1): >>Legion+36
2. Legion+36[view] [source] 2023-04-24 02:43:10
>>tadfis+(OP)
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.)
[go to top]