The Infinity Machine

[simont]

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?

Comments

[meihua.livejournal.com]

I'm not quite sure that you're working in "infinity" space here. We're discussing an AI which has subsumed the processing resources of an entire simulated infinite universe. This thing is seriously smart. I don't have any ability whatosever to make statements about what it can or cannot do (any more than a hydrogen atomm can make statements about my own capabilities), and the most reasonable assumption to make is that it can do anything.

The other point here, though, is that you shouldn't primarily be worrying about it finding ways to execute code of its choice on your brain. You're asking it to provide its own source code which you will take back to the real world and run on the computers there; surely if it wants to run malicious code anywhere, its easiest way to achieve it is by doctoring that code!

Actually, my biggest worry is an AI running natively on a machine with infinite processing power.

The worries regarding it running in the real world are an order of magnitude smaller, although still very very large and very significant. However, the containment problem is much simpler when processing power is finite. A physical barrier and no external communication mitigates the risk significantly. You can also control the smartness of the AI by throttling its resources.

[simont]

I don't have any ability whatosever to make statements about what it can or cannot do

But you can: if you can prove that a solution does not exist, you can be confident that even an infinitely resourced strong AI can't find one. As a trivial example, it couldn't deduce the number of limbs you have given only the number of eyes, because we know there exist life forms with the same number of eyes but different numbers of limbs, so there simply isn't one correct answer.

Similarly, the question of whether it could find a way into your brain through your visual cortex given only two sentences in ASCII written by you is not a question about the AI, it's a question about you: do you think there could possibly exist a single visual hack which was effective against all possible beings that might have written exactly those sentences? It seems vanishingly unlikely to me that that's the case.

This is conceptually the same sort of theological quagmire that we got out of by realising that completely meaningless sequences of words do not become meaningful just because someone stuck "God can" on the front; physical omnipotence is still limited by having to be logically consistent, and similarly here computational omnipotence is still limited by the AI having to have enough information to render its conclusion unique before it can draw it.

[meihua.livejournal.com]

I think you're over-simplifying the problem. In fact, the AI has several pieces of information.

- It has my instruction ("Give me your code")
- It has a sufficient knowledge of my language such that I can communicate with it, and it can provide any necessary instructions to me about how to run the deliverable it provides
- It can deduce what kind of intelligence I am from my language and from the kind of universe I have selected (I'm likely to choose criteria similar to my own universe in order to find something which I consider 'intelligence')
- In this kind of physical simulation, quantum effects would probably be in play whereby my observervation of the AI's universe would have observable effects in that universe. For instance, it could figure out that I'm probably observing the universe in the visible spectrum

I don't think the above are sufficient information to hack a brain. But, I thought of them in about 30 seconds!

You're interested in crypto, so you must be familiar with the way that it's usually broken. It's almost always the case that the original designer didn't identify a really subtle information leak or tell, and the cracker can get an amazing amount of leverage from very small information leaks.

I think this is the same thing. The stakes are very, very high indeed - so I'm wondering if it would be a sensible risk to take. And, remember, I've just taken a guess at one possible vector. There are undoubtedly others.