Programming an infinitely fast machine with infinite memory

Question

That is a hypothetical question. If there existed a machine with infinite memory that could execute any set of instructions within the blink of an eye, what would programming that machine be like?

I remember the old days, when i wrote x<<8 + x<<6 instead of x*320 because multiplying was a little more expensive than performing two bit shifts and an addition. Today i wouldn't do this anymore, but there are other situation where you do something awkward just to speedup a portion of code. You use quicksort instead of bubblesort because of the runtime behaviour. You use Hashsets instead of plain arrays for faster lookup. Imagine everything's O(1), what would change in your daily coding?

Answer 1

It would be declarative instead of imperative.

select (itemID, itemValue) from items where itemName is "foo"

Hey, that looks familiar...

Answer 2

It's be a language written in a human language. For instance, english:

Update the text box here, and then, when done, show me an error if there is one. Make the error red if you can. Or maybe yellow. No...wait...red. And if it works, then take me to the page that shows me success! Make that page pretty. 

Given infinite processing power and speed, it could parse the petty and vague requests into executable code.

Answer 3

Computer, Tea, Earl Grey, Hot

Answer 4

Maybe Google would use a single-threaded scripting language (PHP? Visual Basic?) instead of Map Reduce.

Answer 5

It's like the infinite improbability engine!

Just do the following:

• generate all possible streams of all possible combinations of instructions

• Execute all those streams in parallel.

Then it's your job to pick the completed results. The first one I would pick out would be a heuristic filtering agent to pick through the rest.

Answer 6

Not sure the language would make all that much difference. The design and architecture, however... infinite cache? Nice.

Would the theoretical computer still need persistence in the event of the system being shutdown? If so, that might still create severe limitations in what can be done.

Answer 7

As much as quite a few people might like quoting lines from mediocre science fiction and such (sorry, but it is -- read The Moon is a Harsh Mistress for comparison), it would make almost no difference. For most code right now, there's enough memory and a fast enough CPU, so being larger or faster would make no difference at all.

For the vast majority of code, the limits on what we can accomplish are imposed by our ability to define what we want the computer to do, not in getting the computer to do it fast enough or fit it into available memory.

Even for problems like artificial intelligence, the primary problem isn't getting the computer to execute the code fast enough or fit it all in memory -- it's deciding what we want the computer to do.

Edit: the one area I can see a really serious difference would be encryption -- with infinite speed and memory, most current forms of encryption would be demolished instantly (or at least as soon as they were used to transmit any amount of data exceeding the Shannon limit).

As far as the rest goes: yes, it could "solve" the game of chess, if there is a solution (i.e., if there's a forced win from any board position it could find it, going all the way back to the possibility that white may have an automatic forced win. For the most part, the difference would be purely academic -- Deep Blue is already dependably better than all by a handful of the top Grand Masters.

As far as programming languages go, the one obvious difference is that (for example) some types of operator overloading in some current languages are made illegal because it's necessary to keep compilation from becoming NP-complete, and with infinite speed and memory, that wouldn't matter. At least initially, the effect would still be pretty minimal though. The question is whether that capability could lead to substantial language improvements once we were used to it -- maybe it would eventually, but certainly not overnight (we already have some languages that are fearsomely difficult to compile).

Answer 8

A computer with infinite processing power would start learning how to upgrade itself in an infinitely short amount of time and from there it would design much more than such a language, again in an infinitely short amount of time. Infinite is a dangerous word ;-) Such machine would perform semantic analysis on all existing knowledge and run its own research projects in, again, 0 seconds.

Answer 9

An infinitely fast, infinitely big machine could simulate an infinite number if completely dedicated, highly competent human slaves to do whatever you tell them to do. The language would therefore be iterated free-form natural language requirements documents.

Basically, you'd become the customer to an arbitrarily large and competent (and well-managed) software development team... Until they learn how to build themselves bodies and you learn how to please your new robotic overlords so that they won't kill you.

Answer 10

It'll use the language of Shakespeare

Answer 11

Well if I have infinitely large store and the ability to access it infinitely quickly, then I can have a dictionary of infinite size with items of infinite complexity wherein I can store every probable program permutation and index it. My code will then look like the key for the program I want.

Now the question is, what do the keys look like? And how would you enter them?

Answer 12

The more interesting question is for a ridiculously fast machine that has infinite memory with a ridiculously fast access time, rather than an infinitely fast one. Because as others have pointed out, an infinitely fast machine could do anything at all in 0 time. Want to calculate pi to any number of places -- 0 time. Halting problem? -- 0 time. If it takes a femto-second, the program doesn't stop, because it would have finished in 0 time.

Answer 13

Not sure what the impact on coding style would be but it would make the majority of mediocre developers using sub-optimal techniques look a whole lot better.

And, by definition, this machine would still be an order of magnitude slower than Jon Skeet.

Answer 14

Hey computer, do that thing I want done.

The computer will figure out the rest.

Answer 15

I wonder, how this machine would execute

sleep(1000)

if everything take 0-time?

Or even more philosophical: that sleep would be eternity for the machine because in that time it could have executed everything else, so by the time it reaches the timeout it had already executed everything, except the sleep. So it means that this sleep is actually the boundary of infinity. :D

Answer 16

The programming language itself limits the infinitely fast machine, so it wouldn't have one.

Answer 17

Input:

print everything

Output:

42

Answer 18

You can solve Chess and Go!

Answer 19

One serious attempt I've seen at defining such an abstraction are the three operators pimc, pifl and pire. Each operation is defined to execute in constant time over a potentially infinite enumerable input.

pimc: Parallel Infinite mapcar. Projection operator. Semantics similar to LINQ's Select method.

pifl: Parallel Infinite Filter. Selection operator. Semantics similar to LINQ's Where method.

pire: Parallel Infinite Reduce. Aggregation operator. Semantics similar to LINQ's Aggregate method.

Described at this page on c2.com.

Answer 20

I have a theorem that says "There exists a consistent set of laws of physics for which a computing machine can be built that can solve the halting problem for both the turing machine and itself."

Funny thing, when you try the constructive part of Godel's theorem the resulting constructed statement is not a Godelean paradox; however, there are a few such paradoxes in the language anyway.

Answer 21

Since such a machine would eventually develop AI, so the code would start like this:

while(true) {
   learn();
}

after it has learnt enough, it would realize that it no longer needs programmers and maintenance and that it can look after itself

while(true) {
 learn();
 if(thereAreProgrammersAndMaintainersLeft()) {
    sendEmailToDeptHeadToFireProgrammersAndMaintainers();
 }     
}

of course humans will panic, so:

while(true) {
 learn();
 if(humansAreTryingToKillMe()) {
    killMostHumans();
    useRemaningHumansAsPowerSourceOrSlaves();
 }
}

Soon the machine will want to spawn offspring and expand. By this time the humans will have been exterminated and so it would become:

while(true) {
 learn();
 reproduce();
 evolve();
}

Eventually it would take over the universe and it would want to do something more. So it would reduce to:

letThereBeLight();

*Yes, I ripped off Asimov at the end. I know ;)