3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ :) May I ask why the downvote? $\endgroup$ – Pan Mrož Jul 6 at 19:30
  • 3
    $\begingroup$ I haven't downvoted, but "time-travelling Turing machine" hasn't been defined. $\endgroup$ – Noah Schweber Jul 6 at 19:35
  • 1
    $\begingroup$ I've upvoted, and I disagree with both the downvote and the votes to close. While it's true that the OP hasn't defined TTTMs (the recent edit still doesn't constitute a fully formal definition), there is actually in my opinion a real gulf between articulating the idea, which they have done, and finding the right formal definition - the latter taking some serious care. I think that this question does have some vagueness, but that there's an interesting idea here and the OP isn't refraining from doing "obvious" work. $\endgroup$ – Noah Schweber Jul 6 at 19:49
  • $\begingroup$ @NoahSchweber Thank you for your answer. May I ask you for an example of problem or problems that TTTM wouldn´t been able to solve but ITTM would be able to solve? $\endgroup$ – Pan Mrož Jul 6 at 20:33
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thank you for your answer. May I ask you for an example of problem or problems that TTTM wouldn´t been able to solve but ITTM would be able to solve? $\endgroup$ – Pan Mrož Jul 6 at 19:59
  • $\begingroup$ As far as I can tell, a TTTM can "know" that it will never halt classically (and translate this into a result), whereas an ITTM can actually produce different results for different inputs that do not halt classically $\endgroup$ – Hagen von Eitzen Jul 6 at 20:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.