simont | The Infinity Machine

The Infinity Machine

Probably most of my friends have heard me waffling on about the Infinity Machine at one time or another. If anyone reading this has managed to miss it so far, you can find my article introducing the concept at http://www.chiark.greenend.org.uk/~sgtatham/infinity.html. Today I have a question about it to ask geek-inclined readers.

The Infinity Machine has been a fun thought experiment for most of my life, but in one respect it's slightly frustrating. Its ability to search a (countably) infinite space in finite time would enable it to solve quite a few problems that are famously unsolved in the real world; but quite a few of those problems would simultaneously be rendered pointless to solve anyway by the presence of Infinity Machines in the world. For example, you could use the Infinity Machine to search all possible computer programs to find the one which was fastest at factorising large integers – but you wouldn't want to, because if we had Infinity Machines then a perfectly naïve factorisation algorithm would be just as efficient in practice and far easier to get working correctly.

It occurred to me this week that there is a scenario in which that slight frustration might be resolved. Suppose you were suddenly taken away from your normal life and sat down in front of an Infinity Machine for a few days, or a week, or a month. Suppose you were free to write programs and run them on it, and free to write finite quantities of the output to real-world storage media to take back with you, but when your time expired the Infinity Machine would vanish and nobody would ever get their hands on one again. In this situation, asking the Machine for efficient finite algorithms would be entirely sensible, in principle.

What would you get it to compute, in this situation?

(Ground rules: to help you write your programs you can have access to a large library, and perhaps archives of reference websites such as Wikipedia if you want them. But you don't get unfettered Internet access while you're using the Infinity Machine: I don't want you doing things like factorising every key on the PGP keyservers, or all the root CA keys, because that's against the spirit of what I'm interested in asking.)

Some thoughts on my own answer:

There are three categories of things you might try for. You might try for global altruism: find out things that improve the sum of human knowledge or the global quality of life. Or you might try for personal profit, e.g. finding algorithms you can sell. Or you might simply try to satisfy your own curiosity. I would certainly like to think I'd mostly try for the former, but then, who knows what I'd really do…

The trouble is that quite a few of the ‘does there exist an efficient algorithm’ questions I can think of are things where I want the answer to be no. If I found out there was an integer factorisation algorithm so efficient that RSA keys had to be impractically big to defeat it, I'm not sure I'd want to publish it to the world anyway. Finding out there wasn't would be more pleasant, but less dramatic.

It might be more interesting to set the Machine searching for unbreakable crypto primitives. Instead of obsoleting RSA (or perhaps as well), I could tell the Machine to work on finding me a block cipher, a hash function and an asymmetric key scheme which have no computationally feasible attacks against them. But the trouble with that is, what would I do with them when I got back to the real world? I'm not a published cryptographer; how would I get people to believe my algorithms were better than those of any other random crank?

It would certainly be interesting to set up some mathematical formal systems and search through all possible derivations within them for proofs of unsolved problems. Goldbach's conjecture would make a good warm-up exercise. The Riemann hypothesis would probably be the one I was most interested in tackling in this way, although I'm not sure what kind of formal system it would take to even express the question coherently, let alone have a good chance of containing a proof. And let's not forget Fermat's Last Theorem: just because it's been solved doesn't mean it wouldn't still be interesting to search through the formal system of Peano arithmetic to see if it contained an elementary proof short enough to have nearly fitted into Fermat's margin. Again, you have the problem of distinguishing yourself from a crank on your return to the real world; but the nice thing about formal systems is that they're independently checkable. I could publish the description of my formal system, a formal proof written in that system, and my derivation-checking program; then people could verify the code of my own checker, and/or easily write their own derivation-checkers, to independently test that the proof was formally valid.

Back to algorithms, it occurred to me that finding the best possible optimisation and code generation algorithms for a compiler (within reasonable running-time limits) might be a worthwhile thing. One could certainly sell that if one were of a mind, without suffering from the crank problem – cryptographic algorithms require careful review to determine their security, but the output of a compiler speaks for itself and the market would figure it out eventually. Alternatively one could publish it as free software, according to taste; either way, I'm pretty confident it would be genuinely useful to people in helping them get stuff done.

So, what do other people think?

Perhaps I should ask some subquestions as well:

What could you do that would have the biggest effect on improving the world?
What would you do in order to make yourself the biggest profit?
What would you be most curious to know the answers to, even if nobody would ever believe you?
And which of those would you prioritise most highly: what would be the thing you'd actually do if given the chance?

Threaded | Flat

I'd imagine you could produce a formal proof of your crypto algorithm that would be enough to convince people in the same was as the Fermat proof. Likewise for the compiler, actually.

I think I'd have great difficulty correctly formulating any of those questions... but supposing I could do so...

I want the answer to chess, which may or may not be believed but at least I could be smug about it.

And I want an answer to the problem of getting computers to learn through experience; depending on how much I get to take away with me a programme that can read/write fluent English would be nice but one that had the potential to *learn* to do so would be even better.

Devising protein structure prediction methods comes to mind. The problem is, there's only finite training/evaluation data; I have no idea how one would avoid hideous overfitting if performing an infinite number of trials. This is probably a problem with any machine-learning type problem.

I don't know if there are existing molecular dynamics sims that would give good answers given enough cycles (

fivemack?); if so then one could generate one's own training data (and get structures for all known sequences while we're at it).

As a naive barely-programmer, I assume this is possible - I would look for an algorithm to without fail identify spam from genuine emails, and when I was kicked out I would give it free of charge to every email provider in the world.

I would also run everybody's multislice simulations, starting with my several-billion-atom one that would otherwise need silly amounts of breaking up to do a bit at a time on CamGRID.

I'd like to see if I could find a way to win go comprehensively - if by searching the complete game space you can say "actually, this is how you should approach a game".

Work-wise, I'd like to have a crack at a problem that bugs me about simulations - how do we know when we've done enough simulations?

I'd make my money by devising a good weather forecasting system, and bringing back enough good enough predictions to bet on white Christmasses and the like :)

Hmm. One infinity machine can simulate an infinite number of infinity machines, right?

So, I'd go in armed with all the data I could gather on physical constants and laws.

I'd then code up a simulation of the physical world. I can make the efficiency as sloppy as I like, since I have infinite computing power. All I want is accurate.

Finally, let's assume that any sufficiently advanced society will eventually create a working artificial intelligence.

Then?

Evolution, baby. I want to walk out with a disc (or discs) which contain the code for an AI, as evolved inside a virtual society evolved inside the simulation of the physical world.

I can run an infinite number of these simultions, and specify some criteria relating to artifacts of civilisation (objects of more than a certain weight remaining in the sky for more than a certain time, for instance, would let me know when they invent planes) that will let the Machine present me with only the civilisations which are making good progress.

Instead of obsoleting RSA (or perhaps as well), I could tell the Machine to work on finding me a block cipher, a hash function and an asymmetric key scheme which have no computationally feasible attacks against them. But the trouble with that is, what would I do with them when I got back to the real world? I'm not a published cryptographer; how would I get people to believe my algorithms were better than those of any other random crank?

I think that I'd treat the claim of someone who had worked out how to factor big numbers cheaply with a certain amount of respect if they also claimed to have an unbreakable cypher. I suspect that might be good enough to get the big guns involved...

Get a few optimal processor designs: optimal MIPS and optimal MIPS/watt.

Try to solve some computational biology issues, either directly or by searching for optimal algorithms.

Search the space of all possible machine designs until you find the one which is the Infinity Machine.

I feel like I'm sidestepping the "nobody will ever get their hands on one ever again", but if one can exist in the universe, that should be repeatable.

Might need to build a few Dyson spheres to power the thing, but once you have one, you can fill it with infinite infinite VMs (ridiculous politics notwithstanding).

PROFIT: (or is that Prophet?)
Pick a specific message, such as one pretending to be from God announcing myself as the Messiah, translate it via ASCII into a single number, then search the digits of Pi to find the message.

IMPROVE THE WORLD:
Run infinitely many infinite size simulations of Conway's life for an infinite duration. In each one, fire a stream of gliders (with the presence of a glider being a "1" and an absense being a "0") containing a message. Eg a repeated sequence, then build up to numbers, representation, alphabets, etc. The message would be finite in length but basically request a confirmation of understanding message be sent back to a specific point at a specific time, using the same glider gun code. Set the complexity of return message to be such that it is less likely to randomly occur than intelligent stable life is to evolve. Pick a sampling of those game of Life instances that passed this test, and ask them for advice on solving the world's problems (eg "Here's the structure of DNA and the human genome. Here are the diseases that affect the world. Please provide structure of immortality virus.")

CURIOUS:
Prove Reay's Lemma:
http://www.toothycat.net/wiki/wiki.pl?ReaysLemma

WHAT WOULD I DO?
Use the Conway life evolving trick, but combined with a test for superior intelligence and good will. I could then trade with them, running infinity machine programs on their behalf to solve problems for them. Ask an infinite number of such civilisations to each come up with a program they think I ought to run, run them, and store the questions and answers. If I don't have the storage to take an infinite answer away with me, I could use infinite peer review to pick out the best problems and answers. Another trade point would be to act as a communication channel between the infinite number of such benign civilisations, allowing them to send messages to each other.

Threaded | Flat

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

Three Ideas