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.

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

This is quite a bold claim. Yeah "in the real world" you often need to take into consideration the constant factors... but to go this far to say that Big O is useless? It's very useful to figure out what would likely work (or not) for your problem, given that you know the data size - I used it for exactly that, many many times.

Let's say you have 2 algorithms. Constant time O(1) and exp time 2^n. It seems constant time is better. But in fact it runs always 42 years. While exp one starts to run longer than millisecond for sizes bigger than number of particles in universe.

Big O says how fast complexity grows, but it doesn't say what that complexity exactly is.

Does something like that happens in real world? Yes, but of course not in such drastic ways.

The fact that Big O notation is sometimes misleading or not helpful is not evidence that it is not generally useful.

https://www.tumblr.com/accidentallyquadratic