3 ms·

There’s a rather big gap between “exponential time” and “forever”! I routinely solve instances of problems in EXPTIME to solve practical problems with no diffi

• danbruc 4y ago
  That misses the point. The discussion is about whether limiting a Turing machine to a finite but non-trivial tape length makes the halting problem tractable. That you can solve the halting problem in some cases - for example for while (true) { } or return 42; - has no bearing on this. The question is whether you can solve the hardest instances satisfying the constraints, not whether you can solve some easy instances.