Remix clone Hacker News

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 6 days ago | parent [-]

This 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 5 days ago | parent [-]

I 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 5 days ago \| parent [-]
		The 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.