0
$\begingroup$

Let's say we have circuitry that can send pieces of data to the past state of the program through literal time travel. Said time travel takes 1-5 clock cycles (I cannot assume the nature of time travel so I am giving slight lee-way) and sends one byte to some byte in the past programs memory along with a check bit to some other location so that the time travel can be detected. The general purpose would be for the program to basically run once and then essentially bootstrap paradoxing the original calculation, thereby in essence only taking the amount of time it took to send the data back to the program's past state.

Would it actually be realistic for a user level or utility program to use this as a fast/cheap way to optimize a program? My guess is that it is only good for extremely complex calculations such as prime number searches, framebuffer generations for 3D graphics, etc. but I cannot be entirely sure.

Assuming this were in the C language, the syntax for code to be bootstrapped would look like this (in case one wishes to write examples of cases they find contradictory)

bootstrap (<checkbit to see if time travel has occurred>)
{
    <code to process and create the original data>

    send: <list of addresses to be sent back separated by commas>
    to: <list of addresses of where the data should be sent to separated by commas>
}

Assume energy/radiation/side effects of time travel are irrelevant. This assumes that it is literally as easy to time travel as it is to run an adding circuit. Also, assume that people have worked out all the "bugs" from the system. The circuit works correctly without fail.

I apologize if this is the wrong stack exchange site. I wish to speak scientifically regarding this in a real theoretical sense and this seemed like the more theoretical CS stack exchange site.

Improve this question
$\endgroup$
13
  • 3
    $\begingroup$ I don't understand your question. You say that you're assuming that the time travel instructions are as cheap and reliable as any classical instruction. So why wouldn't they be a viable optimization strategy? Any calculation that takes more than a couple of clock cycles can be performed "in the future" and the answer time-travelled back. $\endgroup$
    – David Richerby
    Nov 28, 2016 at 8:37
  • $\begingroup$ @DavidRicherby because as I said, it would require requesting the data from the operating system. $\endgroup$
    – user64742
    Nov 28, 2016 at 14:50
  • 4
    $\begingroup$ This question sounds too hypothetical/speculative to me. It invents an implausible situation, with artificial restrictions that neither make it more interesting nor more plausible. Asking about the computational consequences of time travel sounds implausible but interesting. But then adding in the restriction that (for some unstated reason) this time travel can only be done through the OS? I can't see any reason why such a restriction would exist. That sounds like just making stuff up, with no basis. $\endgroup$
    – D.W. ♦
    Nov 28, 2016 at 17:07
  • 1
    $\begingroup$ It's not true that only the OS can know the true physical location of memory. It's possible to run software that knows the physical location of its own memory (e.g., if it runs on the bare metal or with no OS or with paging disabled or a number of other situations). I suggest the question would be more interesting if you just asked what the computational consequences of time travel are, without drawing in your assumptions about the OS. $\endgroup$
    – D.W. ♦
    Nov 28, 2016 at 17:12
  • 1
    $\begingroup$ It is very hypothetical (interesting though), but I do not see any valid reason to assume the time traveling part exists and we are still using current solutions. Also if I understood correctly it would be benefitial everywhere, since it is cheap and easy to use every operation taking more than said 5 cycles could transfer data back to make it immediately available. If you read from disk to future RAM and send the data back then the cost of reading from disk is 5 cycles, so why not loop everywhere? $\endgroup$
    – Evil
    Nov 28, 2016 at 20:32

1 Answer 1

Reset to default
2
$\begingroup$

Yes. If time travel were possible, it would be a huge win for optimization and computation: it would enable us to solve computational problems that today seem very hard to solve with existing computers.

To formalize this, we must first agree on a model of physics that allows time travel and that describes what happens when you try. There are various plausible ways to do that. Under one plausible set of assumptions about the physics, the set of problems you can solve in polynomial time using time travel is all of PSPACE. (If you're not familiar with it, PSPACE is the set of problems solvable by classical no-time-travel computers in any amount of running time you want, subject only the restriction that the space usage must be polynomial.) For instance, every problem in NP could be solved in polynomial time if time travel were possible.

For instance, there are problems that today seem to require exponential time to solve (with classical no-time-travel computers), but could be solved in polynomial time if time travel were possible.

To learn more about this subject, I suggest you take a look at Scott Aaronson's lecture notes: http://www.scottaaronson.com/democritus/lec19.html

Improve this answer
$\endgroup$
1
  • $\begingroup$ Woah. That is an awesome paper! $\endgroup$
    – user64742
    Nov 29, 2016 at 23:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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