Extrinsic Motivation: P = NP If You Have A Time Machine

Not all of the entries to The Hackaday Prize were serious – at least we hope not – and this one is the most entertaining of the bunch. [Eduardo] wants to put a flux capacitor in a CPU pipeline. Read that last sentence again, grab a cup of coffee, mull it over, and come back. This post will still be here.

Assuming the events portrayed in BTTF could be real in some alternate history or universe, consider the properties of a DeLorean time machine: It requires 1.21 Jiggawatts (we’re assuming this is Gigawatts from now on), has a curb weight of about three thousand pounds with the nuclear reactor and/or hovercar conversion, and is able to travel in time ± 30 years. If the power required to travel time were to scale proportionally with mass, sending a CPU register back in time would only require a Watt or so. Yes, ‘ol [Doc Brown] had it wrong with wanting to send a car back in time – sending information back is much, much easier. Now, what do you do with it?

[Eduardo] is using this to speed up pipelined CPUs. In a CPU pipeline, instructions are executed in parallel, but if one instruction depends on the output of another instruction, bad things happen CPU designers have spent long, sleepless nights figuring out how to prevent this. Basically, a MEMS flux capacitor solves all outstanding problems in CPU design. It’s brilliant, crazy, and we’re glad to see it as an entry to The Hackaday Prize.

[Eduardo], though, isn’t seeing the forest for the trees. If you have a flux capacitor in your CPU, why even bother with optimizing a CPU? Just take a normal CPU, add a flux capacitor register, and have the output of a long and complex calculation write to the time traveling register. All calculations then happen instantly, your Ps and NPs are indistinguishable. All algorithms run in O(1), and the entire endeavor is a light-hearted romp for the entire family.


SpaceWrencherThis project is an official entry to The Hackaday Prize that sadly didn’t make the quarterfinal selection. It’s still a great project, and worthy of a Hackaday post on its own.

41 thoughts on “Extrinsic Motivation: P = NP If You Have A Time Machine

  1. You can even use it to compute things that couldn’t be compuled in any reasonable amount of available time using a traditional computer, such as factoring enormous prime numbers.

    The method is described – believe it or not – in Harry Potter and the Methods of Rationality, chapter 17: http://hpmor.com/chapter/17

    1. No you can’t, because you then have to leave the CPU running for all eternity for the answer to exist in the future where you’re getting it from.

      1. No – the procedure described only requires a small amount of computing time from each possible instance of the computation, that’s the point. You compute for a bit, checkpoint your work, then send your state back in time for the past version of the same computer to pick up from where you left off.

        1. But your initial condition, or the state that the computer assumes to start with, must be determined by the future because the computer has to start from a condition it is being given or otherwise it won’t enter the loop, which means that the initial condition already exists even though the computer was never given one.

          And you have a paradox.

          1. Except the paradox has a stable resolution: Computer reads answer from memory, outputs answer, and sends it back to itself in the past. That’s the only stable loop, so it’s the one that exists.

          2. You have whats called a bootstrap paradox;

            http://en.wikipedia.org/wiki/Bootstrap_paradox

            Which is actually allowed under:

            http://en.wikipedia.org/wiki/Novikov_self-consistency_principle

            Imho, its not really a paradox – something is causing itself from a linear time perspective, but from an outside linear time its cause is merely curled up in a spiral which we cant see.
            Its not like other paradoxes where the creation of the state is prevented – which is more akin to standing on the top of a building and trying to remove the floors from under you.

          3. All you need is an if statement that.

            If(interation == 1){
            //start execution
            }else if(iteration == 2){
            //stall for first state from future
            }else{
            //read state and continue
            }

          4. A universal property of paradoxes appears to be that they have solutions…

            twdarkflame seems to say that Igor Novikov has a solution for this one. If I’m reading it right, the philosophical equivalent of his solution is quantum immortality. – This may imply that we are actually discussing a quantum computer where quantum states are entangled in time. Sending information through time with quantum effects was actually recently indicated…

            A flux capacitor for CPUs isn’t easily dismissed.

    2. For even more fun, having access to a closed timelike curve (e.g. a flux capacitor) would allow you to do all of the fun things that quantum computers could do as well. Some of the computational complexity people have had fun with pretty much the same idea, and while there’s an excellent paper on this (http://www.scottaaronson.com/papers/ctc.pdf) it would be extremely difficult to read if you aren’t already well versed in the language of computational complexity.

      1. The paper you linked to proves that CTC’s would give computers the ability to efficiently solve any problem in PSPACE, which is much more powerful than what quantum computers are thought to be capable of (which is defined by complexity class BQP). It hasn’t, however, been proven that BQP is smaller than PSPACE, but it would be incredibly (and that’s understating it) surprising if it turned out that they were equal, even more so than if P = NP turned out to be true.

    1. No, sourcing flux capacitors is easy, it’s the sourcing of Plutonium to drive them that’s still the main bottleneck. It’s as though we’re all stuck back in 1985…

  2. How are you simulating the 141.622272kph required by the capacitor to produce 1210MW? … is it all in the charge pump?
    And how will you snub the oscillation caused by the TTRM predicting its own data? this is a problem i had encountered when making a toaster that detects its lifetime using quantum tunneling combined with a retroactive quantum entanglement, could not think of a better use and future TV was all filled with some sort of humanity enslavement or some similar boring crap

    1. It’s not difficult to get an object the size and mass of a CPU up to the required speed of 236,544 furlongs per fortnight. Simply place the CPU in an inertial dampening field and use the rotation of the Earth to provide the required velocity. Simple!

    2. the oscillation in the ttrm is handled the same way you would in designing an rf amplifier , by inverting the phase of the input 180degrees to the output.

  3. The best idea I could come up with was: an ARM Cortex clone, with a 16-bit wide data bus. Double the number of instructions that can be held, eliminate the rubbish with the lowest PC bit needing to be zero.

    Then I see an idea like this, and hang my head in shame…

  4. This idea is not original, It appeared in a book by Steven Baxter called “Exultant”
    The characters in the book constructed a computer that could solve almost any problem in 0 time, (he even goes in theoretical discussion of one plausible implementation using FTL drives)

    1. Clicked through to make sure this work was referenced. It’s a very interesting read, as is most of Baxter… never could into “Manifold: Time” though.

  5. FYI – jig-ga-watt is (or was) the official US National Bureau of Standards pronunciation! Doc Brown got it sort of right in Back to the Future. [http://en.wikipedia.org/wiki/Giga-#Pronunciation]

  6. ok , ok, time travel is cool and fun to play with, but the real meat is in infinite improbability!
    I have had lots of success with finite improbability (cutting two holes in a wall, inserting a large (yet finite) amount of electrical fishtape into one hole and having the end turn up at the other hole) and can say that the potential of infinite improbability has much more use than mere time travel can ever offer. Think of it now, you take a processor with an infinite improbability engine and a random number genorator, you insert any formula, apply the infinite improbability engine to the random number genorator, and BANG! out comes the right answer.
    I have done a studdy on infinity and it concluded the universe is much smaller than may have been origionally realized. Take, for example, a digital camera, 640x480x256, the total number of images that can ever be taken with this camera is 256^307200, if you dont realize it now, this is mind-blowing. It means that, nomatter where in the universe you go, nomatter when, nomatter where you stand, nomatter what stands sits, or hangs from the cieling behind you, its only possable to take a finite number of unique images.
    Work this the other way around, have a computer generate all those images, now flip thru them. There is a photo of me sitting here typing this from every point in this room. There is a photo of you reading it from every point in your room. And upside down, at every angle. There is a photo of me standing behind you reading over your shoulder, again, from every vantage. there is one with pigeons even. There is a photo of the source listing for the shortest, most money making price of software that ever existed….
    Can you people not see the potential here!?!?!?!

    1. Given the average movie is 130 minutes at 24 frames per second. (Still assuming 640×480 and silent) There are only (256^307200)^4492800 possible movies.
      Of course to find any one picture would require a search filter that is the image you are trying to find.

    2. “Can you people not see the potential here!?!?!?!”

      Even less reason for people get to a Adobe software subscription?

      1. The 256 colors are probably because this post came from a couple decades in the past. (VGA resolution.)
        What I wonder about the number of pictures could generate – what is the number if we leave out all pictures of the photographers thumb?
        How about all the pictures of “Me in front of xxxx”?

  7. Pretty sure I read this in new scientist or scientific america a few years back.
    The possibility of even sending a few bytes into the past makes all computing problems (and indeed basically all problems) a mater of just recognizing the solution.

    You could effectively stick a (decent) random number generator into the code, and the code stops if the number is your solution. If its not the solution, you simply send a message into the past with a new seed. The time would loop untill the “first” random number chosen “just happens” to be the correct answer.

    There was some limitation to the idea though – I think the heat from the required computing is still generated but I cant remember why.

    1. How would sending a problem to the past, essentially outsourcing it to our parents and grandparents, allow it be solved by now? Any supercomputer from those eras are slower than our phones :/ I know you would have all the time in the world, but this would be less efficient than a million monkeys on a million typewriters.

  8. Just like Marty shouldn’t date his mom, a future register should not be ALU’d with a present register, or this computer will create an evil alternate timeline where the owner would own all future bitcoins.
    How would the heat from the fiery trail of the register leaving the present be dissipated?
    Liquid cooled from the icy-cold received future register?
    J(G)igawatts in order to accomplish anything is meaningless without a time duration. Surely they suggest that the energy of a bolt of lightning is enough to bump a car through 25 years, but the movie makes a disservice by mis-using SI units.

  9. So if you start a process and receive the result simultaneously, assuming that the calculation has to be finished in the future to write the answer to the present, If you shut the computer off before it finishes the calculation, does the answer you already have cease to exist?

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s