| ▲ | Jerrrrrrrrry 12 hours ago | |
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. | ||