Overanalyzed

New CPU Instruction

April 28, 2009 at 9:12 am | In Science, Technology | No Comments
by Chris Davenport

I’m going to propose a new CPU instruction. Purely theoretical for now, but interesting to talk about. At least I hope so.

My new CPU instruction is going to load into EAX the value of EAX from 10 seconds in the future.

Crazy talk, I know. But I’m going to ignore the “you can’t do that!” aspect, because that’s just silly rejectionism. Instead, I’m going to think about how to actually implement the instruction.

Supposing we had a second computer, nay, a supercomputer available. That supercomputer has a virtual machine in it, that exactly matches our machine. It’s going to pack 10 seconds of runtime of our computer into the time to execute one instruction, and provide the value back to our machine.

And we’ve implemented it. Well, with a few exceptions.. Our virtual machine simulator doesn’t have the connection to a supercomputer to provide the same 10 seconds in the future instruction. We’d need an even more super computer. Also, I’ve assumed that 10 seconds of runtime is 10 seconds of realtime, which may or may not hold.

That isn’t anything new really, that’s an old turing machine problem. The question of whether a turing machine can determine if a program for that machine will ever halt is considered unsolvable by that same machine.

But that’s because we need that external connection to the supercomputer to give us that 10 seconds’ future result.

Supposing we didn’t. We already know about virtual machines. We already know we can run, on one machine, a virtual machine that just emulates everything. If we don’t worry about time and memory, we could concieveably do all this on one machine, by just firing up a virtual machine that’s a copy of our currently running machine, running it for 10 seconds, then returning to our original machine with the result.

That one can even provide the same 10-seconds’ future EAX, by just creating a second virtual machine within the virtual machine.

So my instruction is going to be a FORK. It means “clone yourself and continue, then in 10 seconds, die and return EAX”

It’s an interesting instruction. We already use branch prediction and pipelining very similarly. And it highlights something we should have noticed earlier. Of COURSE a turing machine can solve the problem of it ever halting. It just takes the machine waiting for itself to run to completion.

One of the interesting problems with FORK in software is telling the two apart. If we really execute a FORK instruction, and really accomplish it, then the new machine is expecting the results of a fork instruction in EAX. Supposing the next instruction is the equivalent of “oh, well, don’t do that then”.

What should the fork instruction assume? should it assume a value at all? should it nest again? we’ll just run out of resources cloning machines. Maybe throw a temporal processor exception?

I see a paradox. There is one here, there’s no way to just nest machines forever. Paradoxes by their nature is interesting, because they either can’t happen, or can’t not happen. So if it’s not happening, it never will. And if it is happening, it’s a tautology and always will.

So press onward. We don’t need to nest forever. EAX is only 32 bits. We only need to create 2^32 virtual machines, each with a different value for EAX, let them all run, and figure out which one resolves the paradox. Which machines, when given a value for EAX, actually produce that same value in 10 seconds time.

And the instruction, the same for all of them, is now “Guess and Explode if Wrong” (GEW?), and of course we throw away the one that guesses it explodes, though I suppose that can’t happen because “exploded” isn’t a valid value of EAX, but now we have the problem of them all exploding.

We’ve gotten around the requirement of requiring intramachine communication, though we still have the cellular automata problem of a machine copying itself, but it stands to reason that if we can copy it, we can also copy it with a new value of Guessed EAX.

If we keep the VM on the same machine, running inside the same machine, then we can answer the larger class of turing problems, provided that we have a specific limitation on the instruction set. There can’t be a halt instruction, because that can’t be emulated without halting the machine, we’re working with non-self-modifying code here, and there must be a return-to-host-or-halt instruction. With those two limits, one program can analyze another and determine if it ever halts within an arbitrary limit, by running it for that long. And the only reason we can’t say if a program will EVER halt is because we can’t run it one step past forever and see.

But that’s for really complicated predictions. Most predictions in a computer system can be made more simply. If all we want to know is the result of a function call, we can do that in the same machine, by setting up a little function-calling sandbox closure and calling it.

I wrote a patent similar to this, many years ago, in which an application could trade runtime for user input, by cloning itself and predicting that input, and then destroying those that guessed wrong. It’s even trainable using standard net techniques.

Pretty easy to see how this technique could be used in a distributed processing system, the function-closure model is very similar to google’s map/reduce, and I doubt it will be long before the OS vendors figure out that they can export memory and runtime to other systems.