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

> E.g., there are regularly people that are sure they have > solutions to problems that are reducible to solving the > halting problem, but that don't have the theoretical > background to realize it is reducible to the halting > problem or why that means their "solution" doesn't work.

I think you might have gotten this the wrong way: All decidable problems are trivially reducible to the halting problem (just decide them and then map to a halting/non-halting Turing machine). On the other hand, if you can reduce the halting problem to a problem, it means it's undecidable.

I would be curious though which "natural" undecidable problems people claim to solve regularly.




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!




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

Search: