Hacker News Reader

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

[0] Specifically the generic case decidability of the Halting Problem for one-sided tape Turing Machines? https://en.wikipedia.org/wiki/Generic-case_complexity#The_ha...

View on HN

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.

Reply on news.ycombinator.com