3 ms·
Technically correct is the best kind of correct, and The Halting Problem is a fun head scratcher for a green computer scientist. I'm glad it was part of my intr
by the-grump 1y ago
Technically correct is the best kind of correct, and The Halting Problem is a fun head scratcher for a green computer scientist. I'm glad it was part of my introduction to NP hardness.
That said, you do make a great point OP, and I'll think about it every time the Halting Problem comes up.
- edanm 1y agoThis seems weird to me. I would think the classic way to introduce these topics is to first talk about decidability, introduce the halting problem through that, then introduce complexity. That's certainly how I was introduced to this material. I wouldn't think that you'd learn about the halting problem as only an example of something harder than NP hard.
- sfink 1y agoI agree. NP, NP-complete, and NP-hard are all talking about how long things take. If something is uncomputable, then how long it takes doesn't seem very relevant or interesting. "If Jimmy earns 5 cents a day and a watermelon costs $10, how long will it take for Jimmy to earn enough money to buy the color blue?" Maybe the connection is that it feels like the halting problem could be solved if you had an infinite amount of time?
- thaumasiotes 1y agoThe halting problem obviously can be solved if you have an infinite amount of time, as long as terminating is guaranteed to take place within a finite amount of time. If it's possible to terminate after an infinite amount of time, you'll need a more infinite amount of time to check for halting.