Actually, as someone with background in Biology I can tell you that this is not a problem you want to approach atoms-up. It’s been tried, and our computational capabilities fell woefully short of succeeding.
I should explain what “woefully short” means, so that the answer won’t be “but can’t the AI apply more computational power than us?”. Yes, presumably it can. But the scales are immense. To explain it, I will need an analogy.
Not that long ago, I had the notion that chess could be fully solved; that is, that you could simply describe every legal position and every position possible to reach from it, without duplicates, so you could use that decision tree to play a perfect game. After all, I reasoned, it’s been done with checkers; surely it’s just a matter of getting our computational power just a little bit better, right?
First I found a clever way to minimize the amount of bits necessary to describe a board position. I think I hit 34 bytes per position or so, and I guess further optimization was possible. Then, I set out to calculate how many legal board positions there are.
I stopped trying to be accurate about it when it turned out that the answer was in the vicinity of 10^68, give or take a couple orders of magnitude. That’s about a billionth billionth of the TOTAL NUMBER OF ATOMS IN THE ENTIRE UNIVERSE. You would literally need more than our entire galaxy made into a huge database just to store the information, not to mention accessing it and computing on it.
So, not anytime soon.
Now, the problem with protein folding is, it’s even more complex than chess. At the atomic level, it’s incredibly more complex than chess. Our luck is, you don’t need to fully solve it; just like today’s computers can beat human chess players without spanning the whole planet. But they do it with heuristics, approximations, sometimes machine learning (though that just gives them more heuristics and approximations). We may one day be able to fold proteins, but we will do so by making assumptions and approximations, generating useful rules of thumb, not by modeling each atom.
Yes, I understand what “exponential complexity” means :-)
It sounds, then, like you’re on the side of kalla724 and myself (and against my Devil’s Advocate persona): the AI would not be able to develop nanotechnology (or any other world-shattering technology) without performing physical experiments out in meatspace. It could do so in theory, but in practice, the computational requirements are too high.
But this puts severe constraints on the speed with which the AI’s intelligence explosion could occur. Once it hits the limits of existing technology, it will have to take a long slog through empirical science, at human-grade speeds.
Actually, I don’t know that this means it has to perform physical experiments in order to develop nanotechnology. It is quite conceivable that all the necessary information is already out there, but we haven’t been able to connect all the dots just yet.
At some point the AI hits a wall in the knowledge it can gain without physical experiments, but there’s no good way to know how far ahead that wall is.
It is quite conceivable that all the necessary information is already out there, but we haven’t been able to connect all the dots just yet.
Wouldn’t this mean that creating fully functional self-replicating nanotechnology is just a matter of performing some thorough interdisciplinary studies (or meta-studies or whatever they are called) ? My impression was that there are currently several well-understood—yet unresolved—problems that prevent nanofactories from becoming a reality, though I could be wrong.
The way I see it, there’s no evidence that these problems require additional experimentation to resolve, rather than find an obscure piece of experimentation that has already taken place and whose relevance may not be immediately obvious.
Sure, that more experimentation is needed is probable; but by no means certain.
Thorough interdisciplinary studies may or may not lead to nanotechnology, but they’re fairly certain to lead to something new. While there are a fair number of (say) marine biologists out there, and a fair number of astronomers, there are probably rather few people who have expertise in both fields; and it’s possible that there exists some obscure unsolved problem in marine biology whose solution is obvious to someone who’s keeping up on the forefront of astronomy research. Or vice versa.
Or substitute in any other two fields of your choice.
First I found a clever way to minimize the amount of bits necessary to describe a board position. I think I hit 34 bytes per position or so, and I guess further optimization was possible.
Indeed, using a very straightforward Huffman encoding (1 bit for an for empty cell, 3 bits for pawns) you can get it down to 24 bytes for the board alone. Was an interesting puzzle.
Looking up “prior art” on the subject, you also need 2 bytes for things like “may castle”, and other more obscure rules.
There’s further optimizations you can do, but they are mostly for the average case, not the worst case.
It’s been tried, and our computational capabilities fell woefully short of succeeding.
Is that because we don’t have enough brute force, or because we don’t know what calculation to apply it to?
I would be unsurprised to learn that calculating the folding state having global minimum energy was NP-complete; but for that reason I would be surprised to learn that nature solves that problem, rather than finding a local minimum.
I don’t have a background in biology, but my impression from Wikipedia is that the tension between Anfinsen’s dogma and
Levinthal’s paradox is yet unresolved.
A-la Levinthal’s paradox, I can say that throwing a marble down a conical hollow at different angles and force can have literally trillions of possible trajectories; a-la Anfinsen’s dogma, that should not stop me from predicting that it will end up at the bottom of the cone; but I’d need to know the shape of the cone (or, more specifically, its point’s location) to determine exactly where that is—so being able to make the prediction once I know this is of no assistance for predicting the end position with a different, unknown cone.
Similarly, Eliezer is able to predict that a grandmaster chess player would be able to bring a board to a winning position against himself, even though he has no idea what moves that would entail or which of the many trillions of possible move sets the game would be comprised of.
Problems like this cannot be solved on brute force alone; you need to use attractors and heuristics to get where you want to get.
So yes, obviously nature stumbled into certain stable configurations which propelled it forward, rather than solve the problem and start designing away. But even if we can never have enough computing power to model each and every atom in each and every configuration, we might still get a good enough understanding of the general laws for designing proteins almost from scratch.
I would think it would be possible to cut the space of possible chess positions down quite a bit by only retaining those which can result from moves the AI would make, and legal moves an opponent could make in response. That is, when it becomes clear that a position is unwinnable, backtrack, and don’t keep full notes on why it’s unwinnable.
This is more or less what computers do today to win chess matches, but the space of possibilities explodes too fast; even the strongest computers can’t really keep track of more than I think 13 or 14 moves ahead, even given a long time to think.
Merely storing all the positions that are unwinnable—regardless of why they are so—would require more matter than we have in the solar system. Not to mention the efficiency of running a DB search on that...
Not to mention the efficiency of running a DB search on that...
Actually, with proper design, that can be made very quick and easy. You don’t need to store the positions; you just need to store the states (win:black, win:white, draw—two bits per state).
The trick is, you store each win/loss state in a memory address equal to the 34-byte (or however long) binary number that describes the position in question. Checking a given state is then simply a memory retrieval from a known address.
I suspect that with memory on the order of 10^70 bytes, that might involve additional complications; but you’re correct, normally this cancels out the complexity problem.
Merely storing all the positions that are unwinnable—regardless of why they are so—would require more matter than we have in the solar system. Not to mention the efficiency of running a DB search on that...
The storage space problem is insurmountable. However searching that kind of database would be extremely efficient (if the designer isn’t a moron). The search speed would have a lower bound of very close to (diameter of the sphere that can contain the database / c). Nothing more is required for search purposes than physically getting a signal to the relevant bit, and back, with only minor deviations from a straight line each way. And that is without even the most obvious optimisations.
If your chess opponent is willing to fly with you in a relativistic rocket and you only care about time elapsed from your own reference frame rather than the reference frame of the computer (or most anything else of note) you can even get down below that diameter / light speed limit, depending on your available fuel and the degree of accelleration you can survive.
Hmm, ok, my Nanodevil’s Advocate persona doesn’t have a good answer to this one. Perhaps some SIAI folks would like to step in and pick up the slack ?
I’m afraid not.
Actually, as someone with background in Biology I can tell you that this is not a problem you want to approach atoms-up. It’s been tried, and our computational capabilities fell woefully short of succeeding.
I should explain what “woefully short” means, so that the answer won’t be “but can’t the AI apply more computational power than us?”. Yes, presumably it can. But the scales are immense. To explain it, I will need an analogy.
Not that long ago, I had the notion that chess could be fully solved; that is, that you could simply describe every legal position and every position possible to reach from it, without duplicates, so you could use that decision tree to play a perfect game. After all, I reasoned, it’s been done with checkers; surely it’s just a matter of getting our computational power just a little bit better, right?
First I found a clever way to minimize the amount of bits necessary to describe a board position. I think I hit 34 bytes per position or so, and I guess further optimization was possible. Then, I set out to calculate how many legal board positions there are.
I stopped trying to be accurate about it when it turned out that the answer was in the vicinity of 10^68, give or take a couple orders of magnitude. That’s about a billionth billionth of the TOTAL NUMBER OF ATOMS IN THE ENTIRE UNIVERSE. You would literally need more than our entire galaxy made into a huge database just to store the information, not to mention accessing it and computing on it.
So, not anytime soon.
Now, the problem with protein folding is, it’s even more complex than chess. At the atomic level, it’s incredibly more complex than chess. Our luck is, you don’t need to fully solve it; just like today’s computers can beat human chess players without spanning the whole planet. But they do it with heuristics, approximations, sometimes machine learning (though that just gives them more heuristics and approximations). We may one day be able to fold proteins, but we will do so by making assumptions and approximations, generating useful rules of thumb, not by modeling each atom.
Yes, I understand what “exponential complexity” means :-)
It sounds, then, like you’re on the side of kalla724 and myself (and against my Devil’s Advocate persona): the AI would not be able to develop nanotechnology (or any other world-shattering technology) without performing physical experiments out in meatspace. It could do so in theory, but in practice, the computational requirements are too high.
But this puts severe constraints on the speed with which the AI’s intelligence explosion could occur. Once it hits the limits of existing technology, it will have to take a long slog through empirical science, at human-grade speeds.
Actually, I don’t know that this means it has to perform physical experiments in order to develop nanotechnology. It is quite conceivable that all the necessary information is already out there, but we haven’t been able to connect all the dots just yet.
At some point the AI hits a wall in the knowledge it can gain without physical experiments, but there’s no good way to know how far ahead that wall is.
Wouldn’t this mean that creating fully functional self-replicating nanotechnology is just a matter of performing some thorough interdisciplinary studies (or meta-studies or whatever they are called) ? My impression was that there are currently several well-understood—yet unresolved—problems that prevent nanofactories from becoming a reality, though I could be wrong.
The way I see it, there’s no evidence that these problems require additional experimentation to resolve, rather than find an obscure piece of experimentation that has already taken place and whose relevance may not be immediately obvious.
Sure, that more experimentation is needed is probable; but by no means certain.
Thorough interdisciplinary studies may or may not lead to nanotechnology, but they’re fairly certain to lead to something new. While there are a fair number of (say) marine biologists out there, and a fair number of astronomers, there are probably rather few people who have expertise in both fields; and it’s possible that there exists some obscure unsolved problem in marine biology whose solution is obvious to someone who’s keeping up on the forefront of astronomy research. Or vice versa.
Or substitute in any other two fields of your choice.
Indeed, using a very straightforward Huffman encoding (1 bit for an for empty cell, 3 bits for pawns) you can get it down to 24 bytes for the board alone. Was an interesting puzzle.
Looking up “prior art” on the subject, you also need 2 bytes for things like “may castle”, and other more obscure rules.
There’s further optimizations you can do, but they are mostly for the average case, not the worst case.
I didn’t consider using 3 bits for pawns! Thanks for that :) I did account for such variables as may castle and whose turn it is.
Is that because we don’t have enough brute force, or because we don’t know what calculation to apply it to?
I would be unsurprised to learn that calculating the folding state having global minimum energy was NP-complete; but for that reason I would be surprised to learn that nature solves that problem, rather than finding a local minimum.
I don’t have a background in biology, but my impression from Wikipedia is that the tension between Anfinsen’s dogma and Levinthal’s paradox is yet unresolved.
The two are not in conflict.
A-la Levinthal’s paradox, I can say that throwing a marble down a conical hollow at different angles and force can have literally trillions of possible trajectories; a-la Anfinsen’s dogma, that should not stop me from predicting that it will end up at the bottom of the cone; but I’d need to know the shape of the cone (or, more specifically, its point’s location) to determine exactly where that is—so being able to make the prediction once I know this is of no assistance for predicting the end position with a different, unknown cone.
Similarly, Eliezer is able to predict that a grandmaster chess player would be able to bring a board to a winning position against himself, even though he has no idea what moves that would entail or which of the many trillions of possible move sets the game would be comprised of.
Problems like this cannot be solved on brute force alone; you need to use attractors and heuristics to get where you want to get.
So yes, obviously nature stumbled into certain stable configurations which propelled it forward, rather than solve the problem and start designing away. But even if we can never have enough computing power to model each and every atom in each and every configuration, we might still get a good enough understanding of the general laws for designing proteins almost from scratch.
I would think it would be possible to cut the space of possible chess positions down quite a bit by only retaining those which can result from moves the AI would make, and legal moves an opponent could make in response. That is, when it becomes clear that a position is unwinnable, backtrack, and don’t keep full notes on why it’s unwinnable.
This is more or less what computers do today to win chess matches, but the space of possibilities explodes too fast; even the strongest computers can’t really keep track of more than I think 13 or 14 moves ahead, even given a long time to think.
Merely storing all the positions that are unwinnable—regardless of why they are so—would require more matter than we have in the solar system. Not to mention the efficiency of running a DB search on that...
Actually, with proper design, that can be made very quick and easy. You don’t need to store the positions; you just need to store the states (win:black, win:white, draw—two bits per state).
The trick is, you store each win/loss state in a memory address equal to the 34-byte (or however long) binary number that describes the position in question. Checking a given state is then simply a memory retrieval from a known address.
I suspect that with memory on the order of 10^70 bytes, that might involve additional complications; but you’re correct, normally this cancels out the complexity problem.
The storage space problem is insurmountable. However searching that kind of database would be extremely efficient (if the designer isn’t a moron). The search speed would have a lower bound of very close to (diameter of the sphere that can contain the database / c). Nothing more is required for search purposes than physically getting a signal to the relevant bit, and back, with only minor deviations from a straight line each way. And that is without even the most obvious optimisations.
If your chess opponent is willing to fly with you in a relativistic rocket and you only care about time elapsed from your own reference frame rather than the reference frame of the computer (or most anything else of note) you can even get down below that diameter / light speed limit, depending on your available fuel and the degree of accelleration you can survive.