The Halting Problem is a terrible example of NP-Harder

For any function f(n) the problem "compute 2^f(n)" is going to be Ω(f(n)), because the output is f(n) bits; so merely writing down the answer takes Ω(f(n)) steps.

Note, that the number n is the input here, which is k = log(n) bits long. So the runtime is actually Ω(f(2^log(n))) = Ω(f(2^k)).

Well, since you said "for any function f" ... It's not true for, say, constant functions.