Comment on Show HN: Run unknown shell script with a line-by-line confirmation promptparentComments−aroulin5ydoesn't the halting problem only hold if you have infinite memory?−usr11065yThat's probably correct. But any reasonable execution environment has so many states that doing a full enumeration is infeasible.−rgoulter5yI've seen this argument that 'halting problem is undecideable': http://www.lel.ed.ac.uk/~gpullum/loopsnoop.htmlThe argument doesn't rely on infinite memory.−usr11065yWith 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.
Comments
doesn't the halting problem only hold if you have infinite memory?
That's probably correct. But any reasonable execution environment has so many states that doing a full enumeration is infeasible.
I've seen this argument that 'halting problem is undecideable': http://www.lel.ed.ac.uk/~gpullum/loopsnoop.html
The argument doesn't rely on infinite memory.
With 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.