![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
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-
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 –
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-
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-
Back to algorithms, it occurred to me that finding the best possible optimisation and code generation algorithms for a compiler (within reasonable running-
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?
no subject
One of my responses to the question was to try to make a simulation of _this_ universe.
1. Start a simulation of a Schroedinger equation and a big bang, and try all possibilities until you get one that accords exactly with your library.
2. Extrapolate it into the future whilst waving your hands (which through gravitational waves and chaos theory _alter_ the future). When the future state achieves whatever condition you want (say "infinity machine spontaneously falls from sky in London" or "win the lottery" or "world peace") a light comes on and you stop waving :)
3. Profit.
There are only a few flaws:
1. Do you have to know the laws of physics precisely?
2. What if "random rock that happens to have encyclopaedia carved in" is as likely as this universe? Then you may end up with that one.
3. The traditional infinity machine can only do _countably_ infinitely many things iirc. Your potential universes might be uncountable.
4. I'm not positive about the gravity waves/chaos thing. I mean, it's a literally hand-waving solution...
no subject
I think that the idea of a full-universe simulation is one of those ideas. You suddenly hit a whole shedload of horrible violations of information theory the moment you try and put information into or get information out of that simulated universe. Remember - observe something, change that something.
That's why I think my simulated universe is more practical than yours. ;) I don't need mine to be accurate. I just need it to serve as an incubator.
Yours will wildly diverge from whatever reference point (and checkpoints) you set up, thanks to the fact that your simulation will be imperfect (your reference data can never be 100% precise) and that you are also observing it.
no subject
Arguably, yes. :)