Remix clone Hacker News

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.