For the real computer scientists out here, what would time complexity notation be like if time traveling of information was possible (i.e. doing big expensive computations and sending the result back into the past)?
Of course you should still carry out the computation to prevent a paradox.
Some programs won't halt even after forever, in the sense of an infinite number of time stops. For example, if you want to test properties of (possibly infinite) sets of natural numbers, there's no search strategy that will go through them even in infinite time.
(Footnote that I'm assuming, I think reasonably but who knows what CSists have been up to?, a model of computation that allows the performance of countably, but not uncountably, many steps.)
A starts computation. If it halts A sends a result, otherwise it won't.
B sees the result in a finite time. If it doesn't, the program didn't halt.
If time is discrete, it won't fly I think. This works because there is no smallest time unit in gr.
We are working with different types of infinities. A's computational steps take, the further B goes in, less time. Sort of Zeno's paradox. It is easy to map all natural numbers between 0 and 1 on the real line. Just not 1 to 1.
There are more problems.
How to get the information out and how to survive the divergent blue shift, it is somewhat unclear. B cannot talk back. But still a cool find.
For the usual meaning of the term, you certainly can construct a 1-to-1 (that is, injective) map N \to [0, 1] (for example, n \mapsto 10^(-n)); the natural numbers just can't be mapped onto [0, 1] (that is, the map can't be surjective). That's the opposite of the problem we have: it's saying you can losslessly encode a countable amount of information in an uncountable amount of space; but I'm saying conversely that you can't perform an uncountable number of steps in a countably infinite amount of time.
But uhm, if you actually want the future to affect the past formally, that is going to be something really different, so I’m not really sure.