Given an input and a program when can you derive the output faster than just running the program? Given an input string W, a description of a turning machine M, and a target output string O (W,M,O) as input, when can a machine M' decide, in fewer steps than simply running M on W, if running M on W, in fact, produces O or not?

What are the circumstances under which this faster M' exists and when is this impossible, i.e. when does this problem reduce to the halting problem (seems like it does)?

Thanks!
Here's an example:

for i from 1 to 10000000000
  do nothing
end for
output 1


In general, however, you can't save much. Indeed, the time hierarchy theorem states, roughly speaking, that you cannot simulate a $T(n)$-time Turing machine running in time $o(T(n)/\log T(n))$.