No free lunch?

Huruvida gratisluncher existerar eller inte har ju av och till varit föremål för het debatt (se t.ex. mina gamla gräl med den amerikanske matematikern och neokreationisten William Dembski), men nu på måndag ser frågan ut att avgöras i ett samarrangemang här på Chalmers mellan föreningarna Chalmers Students for Sustainability och Effective Altruism Chalmers; se mötets Facebooksida för mer information. Kom och lyssna, kom och ät!

The libraries of Babel, Mendel and Turing

There is much disagreement concerning the dangers associated with a breakthrough in artificial intelligence. Could such an event lead to our extinction, or the End of the Human Era as James Barrat put it in the subtitle of his book Our Final Invention? Thinkers like Eliezer Yudkowsky and Nick Bostrom argue that the risk is real and that we need to solve the (very difficult) problem of how to avoid an AI Armageddon. As is clear from my review of Bostrom's book Superintelligence, I find their arguments sufficiently compelling to warrant serious attention.

Many others consider (for a wide variety of reasons) the risk to be an illusion. The latest contributor to this highly diverse camp is computer scientist Thore Husfeldt, with his essay The Monster in the Library of Turing, which is a review of Superintelligence to appear in the Swedish philosophy journal Filosofisk tidskrift and published in English translation on his blog. I find Husfeldt's essay very interesting, and what sets him apart from nearly every other critic of the Bostromian-Yudkowskian position (such as Selmer Bringsjord, Rodney Brooks, David Deutsch, Steven Pinker, John Searle and David Sumpter, just to mention a few of those whose criticisms I debunk at shorter or greater length in my upcoming book Here Be Dragons: Science, Techonlogy and the Future of Humanity (Oxford University Press, to appear)) is that neither does his argument consist in attacking straw men, nor does it succumb to any obvious fallacy. Husfeldt has read Superintelligence carefully and seems to accept many of its arguments, but disagrees on (at least) one crucial point. To make his case, he invokes a new metaphor: the Library of Turing, building on Jorge Luis Borges' Library of Babel and Daniel Dennett's Library of Mendel. Let me breifly describe these three libraries:

• The Library of Babel goes back to Jorge Luis Borges' short story from 1941 with the same name. It contains of all of the 25^1,312,000 books with 1,312,000 characters (we learn from the story that "each book is of four hundred and ten pages; each page, of forty lines, each line, of some eighty letters which are black in color"; 1,312,000=410·40·80) taken from a 25-letter alphabet, including blank space. 25^1,312,000 is an enormously large number, so large that the number of books that would fit in the observable universe is ridiculously small by comparison. We can still try to imagine the library. It contains many wonderful books, including Shakespeare's Hamlet and Solzhenitsyn's One Day in the Life of Ivan Denisovich, but it contains far more books consisting of pure gibberish. The library is so huge that, even if we assume the books to be ordered alphabetically, the interesting books are virtually impossible to find, unless you know exactly what you are looking for. To know which of the library's 25 buildings to go to, you need to know the book's first letter; to know which of the 25 floors of that building to go to, you need to know the book's second letter, and so on and so forth. If you are sitting in front of a word processor, you actually have the Library of Babel at your fingertips: if you first specify the book's first letter by typing it, then specify the second letter similarly, all the way down to the 1,312,000th and last, then - ta-dah! - there is your book.

• The Library of Mendel, invented by Daniel Dennett in his 1995 book Darwin's Dangerous Idea, consists of all DNA sequences of length up to (say) 10,000,000,000. Here we have only four characters (A, C, G and T) but the greater lengths allowed compared to the Library of Babel more than make up for that, so that the number of DNA sequences in the Library of Mendel is even larger than the number of books in the Library of Babel. Just like there are very many interesting books in the Library of Babel, there are very many DNA sequences in the Library of Mendel that code for viable complex organisms. These two subsets from the respective libraries are what Dennett call Vast but Vanishing, where Vast means roughly that their number is far far bigger than the number of elementary particles in the observable universe, and Vanishing means that their proportion of the entire library is so small that the reciprocal of that proportion is Vast.

• The Library of Turing - Thore Husfeldt's new invention - consists of all sequences of length up to (say) 10²⁰ (a very large number, but far from Vast) from an 128-character alphabet - sequences that are interpreted as computer programs written in a given programming language, which Husfeldt takes to be Lisp, but any Turing-complete language will do. As is the case in the libraries of Babel and Mendel, most sequences are just gibberish, but there is a Vast but Vanishing subset of interesting programs.

Husfeldt accepts that the human brain is probably far from an optimal arrangement of matter to produce intelligence, and he accepts functionalism. This leads him to belive (as Bostrom does, and Yudkowsky, and me) that somewhere in the Library of Turing, there is some program that far outstrips our feeble human powers of intelligence. But can we find it? Here is Husfeldt:

Given that the description of a superintelligence exists somewhere in the library, all that remains is to find it. If you don’t work in computer science, this task seems to be relatively trivial. After all, even a mindless exhaustive search will find the volume in question. While this approach is not a particularly tempting exercise for a human, computers are supposed to be good at performing mindless, well-defined, repetitive, and routine tasks at high speed and without complaining. Thus, sooner or later we stumble upon the monster; the only debate is whether the search time is measured in years, generations, or geological time scales.

But this is a fallacy. It is a fallacy because of the unreasonable growth rate of the exponential function, and the powerlessness of exhaustive search.

The point here is that, although presumably Vast, the set of superhumanly intelligent programs in the Library of Turing is also Vanishing, and therefore geological time scales will be far far from sufficient for brute force to succeed.

If the Library of Turing entirely lacked structure, this would be the end of the argument: if there were no structure, there would be no way to improve on brute force search, so there would be no hope (or, to be pedantically precise, a Vanishingly small hope) to come up with a superhumanly intelligent computer program. Intelligent design proponent William Dembski, in his book No Free Lunch, tried (for the purpose of concluding that we have been deliberately designed by an intelligent being) to employ this type of argument to prove that Darwinian evolution is impossible. He hid away the (utterly unreasonable) unstructuredness assumption behind mathematical smokescreens, so as to render it undetectable to most readers, but he failed to make it undetectable to yours truly.

The unstructuredness assumption is just as unreasonable for the Library of Turing as it is for the Library of Mendel, since if the former lacked structure, we would not be able to write useful computer programs. Now, Husfeldt, unlike Dembski, is an honest thinker, so of course he makes no attempt to pretend that the Library of Turing is unstructured, and he admits that there might be ways to improve on brute force search sufficiently well that a superhumanly intelligent program can be found, but intuits that it can't be done:

Could there be another way of discovering the superintelligence than exhaustive search? Certainly. After all, nature has discovered one of the monsters, the brain of Homo sapiens, starting with very simple "brains" hundreds of millions of years ago, and refining them stepwise by natural selection and mutation in environments that favoured cognition. Thus, there is some gradient, some sensible set of stepwise refinements, that Nature has followed through the Library of Turing to arrive at Einstein’s brain. We just don’t know how to recognise, nor efficiently follow this gradient. In the enthusiasm surrounding artificial intelligence in the 1960s we might have thought that we were on such a gradient. If so, we have abandoned it. The current trend in artificial intelligence, away from symbolic reasoning and towards statistical methods like machine learning, that do not aim to build cognitive models, strikes me as an unlikely pathway.

Given our current understanding of the limits of computation, there are many relatively innocent-looking computational problems that are computationally hard. After more than a generation of very serious research into these problems, nobody knows anything better than exhaustive search for many of them. In fact, while the amazing features of your smartphone may tell you a different story, the main conclusion of a generation of research in algorithms is bleak: for most computational problems we don’t know what to do.

Here Husfeldt's intuition and mine part from each other. I agree with him that most likely P≠NP, but I don't see why that would be such a blow to our prospects of finding a superintelligent program. We can do a lot of wonderful things without solving NP-hard problems in polynomial time, and I think the success that Nature has had in coming up with the brain of Homo sapiens and many other impressive things is very suggestive. The Library of Turing is probably at least as structured as the Library of Babel, offering at least as navigable a landscape to search in if we should choose to imitate Nature's method of evolution by natural selection. And we have the bonus option of using our own intelligence to make clever macro-moves in the landscape. I am not in a position to tell whether symbolic reasoning is a more promising approach than machine learning, but there seem to be many potential ways forward. I think there's a good chance (or risk!) we'll create superintelligence before the end of the persent century, and perhaps a lot sooner than that.

This divergence of our intuitions notwithstanding, I find Husfeldt's essay interesting and stimulating, and it ends on a constructive note, suggesting a number of research directions that may turn out worthwhile even in case he is right about the inaccessability of "the monster in the Library of Turing". There's just one passage I find a little bit misleading:

Computation is a resource, exponential growth is immense, and the universe is finite.

Bostrom pays little attention to this problem. For instance, in his discussion of current efforts on brain simulation, he writes:

Success at emulating a tiny brain, such as that of C. elegans, would give us a better view of what it would take to emulate larger brains. At some point in the technology development process, once techniques are available for automatically emulating small quantities of brain tissue, the problem reduces to one of scaling.
Well, to me, scaling is the problem.

Here (and in combination with the essay's overall focus on exponential complexity), Husfeldt seems to suggest that the problem of emulating a brain of size n would suffer from a combinatorial explosion and the accompanying exponential increase in computational complexity. Does he really mean this? I don't want to claim that whole brain emulation is an easy project (it most certainly isn't!), but to me the scaling problem here sounds like it should land in a linear complexity in n, or perhaps a low-degree polynomial, but not exponential, as I don't see where the combinatorial explosion would be coming from.