Hacker News new | past | comments | ask | show | jobs | submit login

The conclusion "this function is likely to terminate" may not be helpful, but "this function is likely to leak memory" may be extraordinarily helpful.

The reason that everyone brings up the halting problem in this context is not that we want to test programs if they halt. (Well, we may, but we're generally looking for other behaviors.) It's because for some behaviors, if you want to be able to handle all cases, then that problem can be reduced to the halting problem. Matt provides an excellent demonstration of this with array indices.

I'm confused by your restatement, because it does not restate what I said. You're talking about the halting problem. I'm talking about proving general behaviors in programs, despite the theoretical result that solving the halting problem is impossible, and that many behaviors can be reduced to the halting problem. The solution, as Matt explains, is to find ways to describe behaviors so they do not reduce to the halting problem. Using this technique, you still can have false negatives ("I don't know"), but you can guarantee no false positives.




I'm confused by your restatement, because it does not restate what I said.

Indeed! I hadn't quite made out what you were trying to say in that post - my statement was not relevant.




Join us for AI Startup School this June 16-17 in San Francisco!

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: