Good day,
I would like to ask this question.
EDIT: By time-traveling turing machine I mean that if the TM halts then it sends back in time result of computation. The result might be in form of simple 1 or 0 or more complex result.
Is it basicaly correct to say that the ability to time travel for a turing machine (send back in time result of computation) is not enough for hypercomputation as it would never reach the omega-th computational step and therefore for hypercomputers such as infinite time turing machine structures like CTC would be needed?
So our timetraveling turing machine would be able to to unlimitedly many computational steps but even if the number would be unlimited it would always be less then is the cardinality of the set of natural numbers?
Thank you all for kind answers.
It depends what you mean by "time-travelling Turing machine," but under the only reasonable interpretation I can think of they are capable of hypercomputation - that is, there are things that are not computable by ordinary Turing machines but are computable by TTT machines. Here's a rough idea of how we can, for example, compute the Halting Problem with a TTTM:
Suppose we want to determine whether $\Phi_e(e)$ halts.
We'll start running $\Phi_e(e)$, with the agreement ahead of time that - if this halts - we'll send the result back to ourselves at time $2$.
OK, now stop at time $3$: have we received, from our future selves, the result of a computation? If we have, then $\Phi_e(e)$ halts; otherwise, it doesn't.
The point is that your finiteness argument only applies to situations where we do send ourself a message, and this ignores a key aspect of the idea:
The absence of a message is itself a message.
We can exploit this to actually get nontrivial strength. Indeed, continuing in this way, the only natural definition of TTTM that I can think of winds up giving us exactly the hyperarithmetic sets. This is still weaker than ITTMs, but vastly stronger than classical computability.
Incidentally, you might try to modify the definition of TTTM to allow "fake" messages in the event that no message would ordinarily be sent - to avoid the trick above. Basically, if a message would be sent by our future selves, then we receive it; otherwise, we might receive nothing but we might also receive "junk." This doesn't help either: just modify the approach above to send back, not the result of the halting computation, but the stage at which it halts. We can then check directly whether that information is accurate by running the relevant program for that many stages; if it doesn't halt by that stage, then the "message" we received was in fact junk, so our future selves never intended to send a message and so the computation doesn't in fact halt.
Of course, I haven't defined TTTMs either. But I do think the above indicates how any reasonable notion of "time-travelling" here actually does give us the ability to perform "infinitely long computations" in a certain sense, despite the apparent finiteness.
If you'd like, I can expand this answer to include what I think is the right definition for a TTTM. It is however a bit tedious to write down, so it may be a bit of time before I get a chance to do so.