The Halting Problem is a terrible example of NP-Harder

To be honest, checking if there is a path between two nodes is a better example of NP-Hard, because it's obvious why you can't verify a solution in polynomial time. Sure the problem isn't decidable, but it's hard to give problems are decidable and explain why the proof can't be verified in P time. Only problems that involve playing optimally a game (with more than one player) that can have cycles come to mind. These are the "easiest" to grasp.

Isn't this NP-complete? The "solution" here would be the steps to take in the path which can be found by brute-force

Wikipedia:

> 2. When the answer is "yes", this can be demonstrated through the existence of a short (polynomial length) solution.

> 3. The correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by trying all possible solutions.