13 ms·
If you changed the question to something like "process X uses a tape no longer than all the atoms in the universe and will terminate before the heat death of th
by skybrian 9y ago
If you changed the question to something like "process X uses a tape no longer than all the atoms in the universe and will terminate before the heat death of the universe" then it becomes finite, so ZF set theory can handle it fine in principle, via simulation.
So it seems like this paper is about a very small Turing machine, and so seems very concrete, but it's also about very long-running behaviors that are likely to be indistinguishable from an infinite loop in practice, so it avoids any practical result?