3 ms·
What do you mean "space in your decider"? My decider takes finite but unbounded memory, same as the machine it's deciding.
by dooglius 1y ago
What do you mean "space in your decider"? My decider takes finite but unbounded memory, same as the machine it's deciding.
- yusina 1y agoOk, if that's the class of systems we are talking about, then the system that your decider wants to check does not need to attain the same state twice. It may or may not terminate, and your decider may never know. You can't have it both ways. Keep in mind that the input can be as adversarial as it wants and knows, including having full knowledge of what your decider is trying to do.
- dooglius 1y agoWhat class of system are you talking about where the claim is false? Can you express your statement/definitions rigorously? A system that enters the same state twice will never halt, we know it will keep cycling through the same list of states over and over again.