Hacker Newsnew | comments | show | ask | jobs | submit login

You misunderstand what I wrote. I should perhaps have been more precise, as I can see that "solutions to problems" might be misunderstood. "Problems" in this context was referring to what people might have tried to prove, not the process they were trying to apply it to. The point being that there are plenty of processes where to prove specific outcomes is a problem that can be reformulated as finding a generic algorithm for solving the halting problem.

The most common variations are simply obfuscated variations where it is not clear that a sub-part of the process is turing complete, and where that sub-part can determine whether or not a specific state is reached.

Quite a lot of software have subsystems that turn out to be Turing complete, whether through the explicit inclusion of scripting support, or through more convoluted means.

I'm not sure, but I think I did understand what you were saying. I was genuinely interested in undecidable problems people might run into and that are easily seen to be at least as powerful as the halting problem. Thanks for the example!


Applications are open for YC Winter 2016

Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | DMCA | Apply to YC | Contact