News for hackers. Stuff that matters.
Re:Total Functional Programming [pdf] by jpt4 on Thursday October 06, 2016 @11:21AM (#12653227)
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...

Re:Total Functional Programming [pdf] by pron on Thursday October 06, 2016 @11:55AM (#12653489)
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.