The Halting Problem is a terrible example of NP-Harder

Well, for a computer that is a finite state machine there are only finitely many states. So, in finite time the machine will either (a) halt or (b) return to an earlier state and, thus, be in an infinite loop. So, in this case can tell if the "program will stop" and, thus, solve "the halting problem".

Uh, we also assume that before we start, we can look at the design of "the machine" and know how many states there can be and from the speed of the machine how many new states are visited each second. So, we will know how long we have to wait before we see either (a) or (b).

Yes, lots of these problems assume fantasy infinite world.

Big O notation also suffers from this - it's almost useless for real world problems.

You find Big O notation useless for real world problems?

I find it useful to characterise algorithmic performance, e.g. O(1), O(n) O(n^2), etc.

What do you find useless about it - and do you know of something that works better?

Simpler algorithms are usually faster for small N, and N is usually small. Big O assumption is fantasy world where N is always large, and constant factors that slow down an algorithm can be ignored.

>Simpler algorithms are usually faster for small N, and N is usually small.

This mentality is how we ended up with cpu and memory hogging Electron apps...