4 ms·
doesn't the halting problem only hold if you have infinite memory?
by aroulin 5y ago
doesn't the halting problem only hold if you have infinite memory?
- usr1106 5y agoThat's probably correct. But any reasonable execution environment has so many states that doing a full enumeration is infeasible.
- rgoulter 5y agoI've seen this argument that 'halting problem is undecideable': http://www.lel.ed.ac.uk/~gpullum/loopsnoop.html http://www.lel.ed.ac.uk/~gpullum/loopsnoop.html The argument doesn't rely on infinite memory.
- usr1106 5y agoWith finite memory and no external inputs an observer can enumerate all possible states. In real systems external inputs provide an infinite source of "memory" to read from.