4 ms·

Do the results from Generic Case Complexity [0] bring more of the computational hierarchy into the realm of feasible (generic) verification? [0] Specifically

• pron 10y ago
  If you read the proof of that theorem, you'll see it's irrelevant: the decidable set, while "asymptotically dense" does not contain most programs humans write. But in any event, halting itself is not very interesting. The point is that knowing one property (like halting) cannot help you with others. As to whether the class of programs humans write are theoretically feasibly verifiable, nobody knows for sure, but the problem is certainly not easy, judging by all attempts so far.