4 ms·

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 c

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)?

openasocket 2y ago
Surprisingly there is prior work on this! https://www.scottaaronson.com/papers/ctchalt.pdf https://www.scottaaronson.com/papers/ctchalt.pdf . Apparently a Turing Machine with time travel can solve the halting problem
- fragmede 2y ago
  With time travel, isn't the halting problem trivially solvable? You start the program, and then just jump to after the end of forever and see if the program terminated.
  - PittleyDunkin 2y ago
    Surely we already have this: the jump just takes forever.
  - HeliumHydride 2y ago
    I think you can only time travel a finite time.
    - MadnessASAP 2y ago
      That's why you instead specify that if & when the program halts it travels back in time to let you know it has. Thus you would know immediately after starting the computation if it's going to halt, how long it'll take, and what the result is. Of course you should still carry out the computation to prevent a paradox.
  - JadeNB 2y ago
    > With time travel, isn't the halting problem trivially solvable? You start the program, and then just jump to after the end of forever and see if the program terminated. 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.)
    - eddd-ddde 2y ago
      But if you are at the present, and dont receive a future result immediately, can't you assume it never halts? Otherwise you would have received a result.
      - mgsouth 2y ago
        I don't think so. That's assuming the program will always be in a frame of reference which is temporally unbounded. If, for example, it fell into a black hole it would, IIUC, never progress (even locally) beyond the moment of intercepting the event horizon.
        eddd-ddde 2y ago
        Hmmm, couldn't you, as long as there's a fixed period of time that supports time travel, keep execution working by travelling to the start of the period again and again (/with/ the current program state) to avoid the program from going beyond the working time period?
        mgsouth 2y ago
        Ooh, clever. Vaguely envision entropy problems, that some mash-up of Godel's Incompleteness theorem, Maxwell's Demon, and Bell's Inequality, and Newton's laws conspires against it. Maybe sending changes back add entropy, or moves it around? Would make a good old-school SF story, with backwater multi-verse dumps for waste entropy, a free-lance troubleshooter uncovering a secret corporate scandal regarding deleterious effects, etc.
pcblues 2y ago
If you shift the computational result back in time to the same time you started it, your O notation is just a zero, and quite scalable. Actually it would open the programming market up to more beginners, because they can brute force any computation without caring about the time dimension. Algorithm courses will go broke, and the books will all end up in the remainder bin. Of course, obscure groups of purists will insist on caring about the space AND time dimensions of complexity, but no-one will listen to them anymore.
- ordu 2y ago
  I don't think it will work like that. It is necessary to run the computation to get the result, even if you transfer the result back in time. So the world will end up running a lot of computations while knowing their future results. These computations will be a new kind of a tech debt, people will choose between adding one more task to the existing supercomputer (and slowing all the tasks there), or creating/leasing another supercomputer to finish some tasks early and forget of them finally.
- neeleshs 2y ago
  There will also be a cult that says this is all borrowing time from the future and we will run out of time eventually.
- deadbabe 2y ago
  You definitely have to be capable of performing the computation to get the result, you can’t just get something from nothing. You just don’t have to actually exist in the timeline where you process the work.
JadeNB 2y ago
I whimsically imagine some version of bi-directional Hoare logic.
seanmcdirmid 2y ago
Going back in the past requires checkpointing the past, which can be very expensive, but maybe cheaper with the right kind of time-indexed data structures underlying your programs. So you just wind back time and begin fixing data structures with your backward change until you are consistent at head time again. 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.

openasocket 2y ago

Surprisingly there is prior work on this! https://www.scottaaronson.com/papers/ctchalt.pdf https://www.scottaaronson.com/papers/ctchalt.pdf . Apparently a Turing Machine with time travel can solve the halting problem

fragmede 2y ago
With time travel, isn't the halting problem trivially solvable? You start the program, and then just jump to after the end of forever and see if the program terminated.
- PittleyDunkin 2y ago
  Surely we already have this: the jump just takes forever.
- HeliumHydride 2y ago
  I think you can only time travel a finite time.
  - MadnessASAP 2y ago
    That's why you instead specify that if & when the program halts it travels back in time to let you know it has. Thus you would know immediately after starting the computation if it's going to halt, how long it'll take, and what the result is. Of course you should still carry out the computation to prevent a paradox.
- JadeNB 2y ago
  > With time travel, isn't the halting problem trivially solvable? You start the program, and then just jump to after the end of forever and see if the program terminated. 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.)
  - eddd-ddde 2y ago
    But if you are at the present, and dont receive a future result immediately, can't you assume it never halts? Otherwise you would have received a result.
    - mgsouth 2y ago
      I don't think so. That's assuming the program will always be in a frame of reference which is temporally unbounded. If, for example, it fell into a black hole it would, IIUC, never progress (even locally) beyond the moment of intercepting the event horizon.
      - eddd-ddde 2y ago
        Hmmm, couldn't you, as long as there's a fixed period of time that supports time travel, keep execution working by travelling to the start of the period again and again (/with/ the current program state) to avoid the program from going beyond the working time period?
        mgsouth 2y ago
        Ooh, clever. Vaguely envision entropy problems, that some mash-up of Godel's Incompleteness theorem, Maxwell's Demon, and Bell's Inequality, and Newton's laws conspires against it. Maybe sending changes back add entropy, or moves it around? Would make a good old-school SF story, with backwater multi-verse dumps for waste entropy, a free-lance troubleshooter uncovering a secret corporate scandal regarding deleterious effects, etc.

pcblues 2y ago

If you shift the computational result back in time to the same time you started it, your O notation is just a zero, and quite scalable. Actually it would open the programming market up to more beginners, because they can brute force any computation without caring about the time dimension. Algorithm courses will go broke, and the books will all end up in the remainder bin. Of course, obscure groups of purists will insist on caring about the space AND time dimensions of complexity, but no-one will listen to them anymore.

ordu 2y ago
I don't think it will work like that. It is necessary to run the computation to get the result, even if you transfer the result back in time. So the world will end up running a lot of computations while knowing their future results. These computations will be a new kind of a tech debt, people will choose between adding one more task to the existing supercomputer (and slowing all the tasks there), or creating/leasing another supercomputer to finish some tasks early and forget of them finally.
neeleshs 2y ago
There will also be a cult that says this is all borrowing time from the future and we will run out of time eventually.
deadbabe 2y ago
You definitely have to be capable of performing the computation to get the result, you can’t just get something from nothing. You just don’t have to actually exist in the timeline where you process the work.

JadeNB 2y ago

I whimsically imagine some version of bi-directional Hoare logic.

seanmcdirmid 2y ago

Going back in the past requires checkpointing the past, which can be very expensive, but maybe cheaper with the right kind of time-indexed data structures underlying your programs. So you just wind back time and begin fixing data structures with your backward change until you are consistent at head time again. 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.