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

Consider that a lot of problems seems "obvious" to beginners who does not know the full literature on the subject, pretty much regardless of subject.

I studied computer science, and during our data structures and algorithms course must have "discovered" a dozen or more algorithms that I'd then find treated or discredited a chapter or two later in our course material.

Sometimes someone out of nowhere benefits from not having been explained why a specific idea "can't" work, but much more often they end up wasting their time on it. And some of them go on to think they have valid, significant results.

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.




> 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: