| ▲ | davrosthedalek 20 hours ago | |
First, TMs don't have a stack. Second, still no recurrent state needed. Extending a state with additional variables doesn't make a unique state less unique anyway, so "total state" is always more or same unique as "just tape". | ||
| ▲ | Jerrrrrrrrry 12 hours ago | parent [-] | |
Some turing machine variants have multiple tapes, effectively registers. If the tape, instruction position, and all other variables are the same as any previous step, then the deterministic machine is going to continue to find itself in that loop, and never halt. Think Collatz like functions - if the output starts into a loop, you know the end result. However, any program trying to detect all loops by maintaining a bloom filter of every previous state doesnt work, that drags any computation down by a scale of its inputs^runtime. | ||