You don’t need nearly that much complexity; a simple program generating all n-bit strings should only take a few lines, independently of the language you use. Think about how in natural language, it takes only the line ‘all 1 million character strings’ to completely specify the entire library. The length of this description is the notion of complexity in algorithmic information theory. The entire library thus needs only the bits encoding this sentence to fully encode, while any given book typically can’t be compressed very much.
Now, if the likelihood of something popping into existence spontaneously is given by its complexity, which would be true for a process generating random bitstrings with uniform likelihood, then the entire library is indeed more likely than any given book to arise spontaneously.
All of the ‘almost libraries’ (which can’t boil down to a few different characters in some of the books—those books would be included in the original library, too!) must be more complex, at least by the specification of the differences, i.e. ‘all the books with 1 million characters, except for the book [description of the book—taking, on average, 1 million characters!] which has an additional ‘y’ at the end’.
That’s a description, but not a generation algorithm. I’m damned if I can think of a generation algorithm that takes “only a few lines.” Can you help me out here?
Maybe I’m not being fair here, but it seems to me that this is only a meta-description, depending on assumed knowledge. “All the works of William Shakespeare” – there, I’ve accurately described it in just six words – but it doesn’t construct the object.
I have learned to respect your views here on SDMB very, very highly, and if you say it’s so, it is most likely so. But… I just can’t find myself feeling this is right.
I think, in terms of objects popping out of black holes or other quantum noise, the definition of complexity you’re using is not valid.
For instance, under your terms, a hydrogen molecule – H2 – is not twice as complex as a single hydrogen atom. You don’t have to say, “One hydrogen atom and then another hydrogen atom.” You just say “One hydrogen atom…twice.” So, by that logic, hydrogen molecules ought to pop out of black holes more than half as often as hydrogen atoms. I’m gonna go way out on a limb and bet a pickle this isn’t the fact.
But I think that how nature looks at the complexity of an object is not quite the same way that an information theorist does.
In the same way, I think that the “library of Babel minus the final letter” would pop out of a black hole almost exactly as often as the full library of Babel, even though the amount of information it takes to describe the former is vastly greater than the amount it takes to describe the former. To any naïve assessment of complexity, the two look almost exactly alike.
I think that black holes eject matter in a naïve way, and not such a calculated fashion.
For instance, I suggest that black holes would not eject six carbon atoms in a ring any more often than they would eject six carbon atoms not in a ring. In fact, I’d say the ring is quite a bit less common. But you would have the former be more common, as it is easier to describe informationally.
I know I’m putting myself in the dangerous and absurd position of our former correspondent who doubted Relativity based on only his gut feelings. I certainly hope I’m not making quite such a bozo of myself!
The thing about Borges’ Library of Babel is that it is almost completely information-free - basically it is just grey noise made up of letters and spaces. The few meaningful elements in it are distributed at random and can’t be found - as Borges realised very clearly. So it can be described in a very few instructions.
The REALLY cool thing about it is that it is possible for it to contain books in languages that are long-lost…and languages which don’t exist yet! For instance, not only does the library contain every possible book in Klingon, but also every book in Narnian, or R’yehlian, ancient Sumerian, ancient proto-Chinese, even Mayan (if you allow Mayan glyphs to be transliterated into letters.)
500 years from now, some intellectual descendant of J.R.R. Tolkien will make up a new fantasy language – and the Library of Babel has books in that language. It has all books in that language, including translations of all other books.
The library not only has all of the lost works of Homer and Plato and Sophocles – but also all the books they intended to write but never got around to!
Let’s generate all one million bit strings. First, generate the string 00…0: can be done using a for loop. Then, increment that string one million times by one. You could just as well use all seven million bit strings and then decode them into letters using the ASCII scheme.
The idea is that natural laws act on the seed generated randomly to sort of ‘unpack’ it: as I said, it’s not like monkeys typing on a typewriter, but like monkeys typing on a computer.
I’m not saying that the entire library pops out of random fluctuations, but that something including all the information of the library—about none—is much more likely to pop into existence than something including the information of a human brain. This something can then be used to construct the library, i.e. by application of the natural laws, just as a simple program, under the action of a computer, can give rise to apparently hugely complex outputs. Perhaps the wiki article on algorithmic information theory helps.
The BBrain story looks at randomly and spontaneously generating the output, but I’m thinking about the input instead.
Er…but you still have to have internal pointers incrementing. A million of them. All you’ve done is throw this down to the level of machine language, but you still have a complex algorithm. Remember, most computers aren’t able to cope with million-bit strings, so you’ve got some very hairy string manipulation to do.
However… At this point, I’ve lost the real point of my objections, so I’m gonna retreat from the field, in some disarray (computer programming pun!) and cede the debate to you. I know you know more than I do about science!
Yes, indeed! There are some very pretty illustrations.
For those who would like to read the story, I will put a link to it here. It’s in a spoiler box and not a live link because it’s a hot pdf link, and those should not be clicked on by the unready or the unwilling. It’s a jolly little story, well worth the effort.
First of all, my post above contains a mistake: of course, you wouldn’t merely have to increment the string one million times, but rather, 2[sup]1000000[/sup] times, since that’s the number of different bit strings of length one million.
Now for your objections: did you take a look at the wiki article I linked to? Complexity, in the algorithmic sense, is concerned merely with the length of the (minimum length) algorithm that is able to output a certain data structure. Whatever the machine does is unimportant, and can be abstracted away (in fact, that’s one of the key theorems of algorithmic information theory: any choice of machine at best adds a constant overhead, which can be ignored in the limit). So your attack at the implementation of the code misses the mark: the key quantities are (asymptotically) implementation-independent; all that matters is that there’s a short code such that some machine outputs the desired data structure.
This isn’t trivial, by the way: in fact, most bit strings (and almost all infinite length bit strings) won’t have such a code—the asymptotically shortest code outputting them is approximately as long as they are themselves, and thus, they are incompressible (meaning they have a high information content). And once more, while most individual bit strings are like that, the set of all bit strings is extremely simple.
That’s your call, but I’d rather try and clarify my arguments to you than ‘win’ by assumed competence.
As i read the wiki article, the following occurred to me even before I read it at the end of the second paragraph:
Pretty obvious and pretty convincing.
Furthermore, we don’t know nearly enough about the odds to calculate either evolved consciousness or random ones, so there’s no way in hell we can say which is greater. However, we can look around, and observe that either these random consciousnesses don’t exist nearby, or if they do exist, they don’t interact with us in any detectable way. Unless that’s what ghosts are!
That was one of my first thoughts, too, but just remember the magic of infinity: if it can happen in an instant, it can happen with a succession of instants, and ones that correlate to some external reality enough to count as perception, etc … But yeah, it’s a mental stretch!
Right, as explained in Dawkins’s Climbing Mount Improbable.
Oof. It’d be nice if someone could translate that!
Nicely reasoned.
Ah good, you beat me to it and fixed your own bug.
Here’s a quick stab at a python program, assuming arbitrary-length integers, and using a fictitious “%b” to print a number in binary, for simplicity. Caution: do not run this at home as you run the risk of creating an evil consciousness.
import math
for length in range(1,10000001):
val = 0
while val < math.pow(2, length):
print "Book: %0*b" % (length, val)
val += 1
This just prints the bitstrings as hex, one line per book, including all books of all lengths up to one million bits. Converting to unicode characters is left to the student as an exercise.
Here’s a more practical example that prints all hex strings up to a given length. You can run this without fear of destroying the world:
import math
max_digits = 3
for length in range(1,max_digits+1):
val = 0
while val < math.pow(16, length):
print "Book: %0*x" % (length, val)
val += 1
Hopefully this illustrates Half Wit’s point that this is a trivial exercise in programming.
Wonderful book! The metaphor is clear and easy to understand. I’ve climbed hills like that!
Okay, granted. But, as I said, you’re just kicking a lot of work down to the machine-language level. Instead of my defining a whole bunch of nested for-next loops, I’m allowing the machine to do it itself in the “val=val+1” statement. The computer will have to define all the data pointers and implicit loops, just in the process of performing binary addition.
So, for our human purposes, yeah, it’s simple. But the complexity of the object – the overall process and system and its description – isn’t reduced that much.
It’s like the sergeant giving the command to the troops: “Okay, make camp here.” It’s easy for him to say, but they have to clear brush, put up tents, dig the latrine, gather firewood, dig firepits, post a watch, etc.
Where I’m bouncing is that I think the completely random process by which a black hole spits out matter and energy is not going to be amenable to such algorithmic short cuts.
To the black hole, the entire alphabet – A through Z – is absolutely indistinguishable from the same alphabet, but with “G” deleted and a duplicate “H” in its place. The two objects are exactly as likely to be ejected from the black hole, even though the former object is easier to describe algorithmically. The black hole isn’t processing an algorithm. It’s using a much more naïve definition of complexity.
In describing a sequence of numbers, it takes more information to describe 1, 6, 2, 2, 3, 6, 1, 2 than it does to describe 5, 5, 5, 5, 5, 5, 5, 5. The latter is much simpler to describe. “Eight fives.” But the two strings are exactly equally likely to arise when I roll a six-sided die eight times. The “less complex” string does not arise any more often than the “more complex” string.
You invite the fool to return to his folly! But, as Gomez Addams wisely said, “I am that fool!”
This is the way things would happen with monkeys hacking on typewriters. But that simply isn’t the situation in the real world: whatever gets hacked into the keyboard is then acted on by natural laws—they’re what does the ‘heavy lifting’. You don’t need to produce a brain randomly, but merely something that will eventually give rise to a brain (or many).
Take the initial state of the universe: by most accounts, it’s a pretty simple thing, nearly perfectly uniform, describable by a short equation, etc. Much simpler than a human brain. But eventually, that simple initial state evolved to all the observed apparent complexity around us, including not just one, but many human brains. The monkeys don’t have to come up with the brain, but merely with the initial state of the universe—the rest comes for free.
And since the initial state of the universe is much simpler than any individual brain, it’s much more likely to pop into existence by some random process. So it’s not the case that it’s more likely that we’re BBrains—in fact, it’s more likely we’re evolved observers in a whole universe, because algorithmically, that’s a less complex thing, just as the whole library is less complex than any individual book.
Perhaps it helps to consider complexity as (in-)compressibility. The information content of a given data structure is the shortest length to which it can be compressed. As you observe, the sequence 5,5,5,… is of very low complexity, because it can be compressed very highly, however, random or patternless sequences typically can’t be compressed at all—that’s what makes them random. They thus have a very high information content. Intuitively, this is about right: with each new number, you learn something new—you couldn’t have guessed it using what you knew before.
But what is the maximally compressed version of a string? Well, it’s some data that, if input to the proper machine, generates the original string. Take note that given any other compressed version, the resulting string will be different: it’s what’s input that contains the information of what’s output. In this sense the compressed string contains all the information of the original string. What the machine does, however complicated it might be, is of no consequence to this.
Likewise with algorithmic information. Here, the compressed version is a program that causes some machine to output some data structure. By the same reasoning, the program contains all the information in the original data: it is both necessary and sufficient to fully recreate it. The machine is just a (partial recursive) function from inputs to outputs: its details do not matter.
What pops into existence is the compressed version. The laws of nature then perform the unpacking. A brain can’t be compressed very much, and thus, the input is about as complex as the output. But a system containing many brains, such as the universe, may be highly compressible. For an incompressible string, e.g. ‘18274956106945’, what has to spontaneously arise is basically the string itself, or something similarly long. But for a compressible string, such as ‘555555555555555’, only the description ‘15*5’ needs to crop up; the laws of nature then unpack that to the original string.
Hence, there’s a difference in the likelihood of the two strings, even though in a process of random die rolling, both are equally likely. The natural evolution realizes the map that takes ‘15*5’ to ‘555555555555555’, and ‘18274956106945’ to itself. Thus, the latter doesn’t gain anything, and is as unlikely as in the case of random die rolling; but the former becomes much more likely.
If the universe exists long enough (as it does under the standard cosmological model), thermal fluctuations might give rise to BBrains. The Higgs mass, as observed at the LHC, opens up the possibility that our universe isn’t actually stable, but might undergo spontaneous vacuum decay with some appreciable probability. If that probability is high enough, then the universe might end soon. Yay!
This strongly depends on the definition of book. If by book you mean any ordering of one million characters, then clearly if you use a program to generate these books, the first million characters you produce will be a book contained in the complete library, and the contention is disproved.
If you mean that the million characters make sense under some definition, and nonsense sequences are allowed, then starting from the same conditions the single book case and the library case will generate the same sequence, but of course the single book case will terminate first. If there is some check for bookdom, then it can be applied in both cases to determine which string of sequences is a book. If not, we can compute how many characters must be generated to produce a book with a given probability, which will be much shorter than the number of characters to generate to generate all books with a given probability.
Finally, if you require that only books are generated, then we have a much more detailed and complex algorithm. In this case the generation of one book will be much faster than the generation of all books.
I think you were comparing the generation of exactly one book with no extraneous characters with the generation of all books with many extraneous characters. In that case the latter is indeed less complex, but it is not a fair comparison.
??? Vacuum fluctuations and black hole emissions aren’t monkeys-on-typewriters random?
I’m really screwed here: I know you know better than I do…but what you say just seems massively contrary to everything I’ve ever learned in probability classes!
But that brings us back to the “standard model” – a real world, with physical laws, producing complexity by the flow of energy through interface zones.
I thought the Boltzmann Brain was an eruption, all in one instant, from nothing at all, by pure randomness.
True…but that initial state had a huge amount of energy all wadded up tightly. As the energy wound down, the chemical elements built up. Some of those elements, like Uranium, had energy hidden inside them. But, overall, the total amount of energy is moving in the direction of heat. We only get local accumulations and concentrations.
Sunlight through the biosphere pumps life up.
There, at least, I agree.
And there, alas, I simply cannot!
I often use the example of sand dunes, existing in (somewhat) orderly arrays. You can look at five of them, and pretty much guess that the sixth will follow the pattern. There is “information” in that pattern, even if it arose only from the “random” process of wind moving over sand.
What I can’t grok is how you get that patterns are more likely than non-patterns in random collections. A bunch of things in a straight line are more easily described – they fit into a clear pattern – but if you throw a shitload of pebbles down on a football field, you won’t find bunches of them in straight lines any more often than random chance would dictate. The simplicity of algorithmic description does not reveal itself in actual appearance of objects.
I really need to drop out here; I can’t do this debate justice, and I’m starting to repeat myself.
ETA: I think I agree with Voyager, but I’m not completely clear on that, either.
THE PENNY DROPS! (I ain’t as stupid as I may seem!)
I was envisioning the appearance of a thing all in one quantum leap!
Hawking once said that anything could pop out of a black hole, and I understood that to mean any object, all at once, wholly formed.
That’s what I was thinking Half Man Half Wit was describing: a mind, or a library, or even a cosmos, popping up in a “big bang” instant. One tick of the clock, nothing. Next tick of the clock, the fully formed shebang.
I wasn’t thinking of a whole bunch of intermediate steps.
I gonna go now and play with my ABC blocks. Thank you for your patience!
Yes, there are some books that can be easily generated, but most (in the limit of infinite length books, almost all) can’t; in fact, most will have a program not much shorter than the book itself. But the point is, in generating the whole library, you get all of those books, as well. The whole thing is merely to show that a collection of things may be less complex than (at least some) of the things it contains (which is, I think, an uncontroversial, if counterintuitive assertion).
Trinopus, yes, I think you’ve got it now—what needs to be randomly produced is only an initial seed, the compressed version, on which then natural evolution acts (nothing ever pops up randomly from nothing, you need at least something like natural laws allowing this sort of thing to happen, meaning you don’t really have ‘nothing’). Just keep the analogy of the world being a computer in mind (we know that its laws are at least capable of supporting computation): what needs to be produced randomly corresponds to programs/inputs, not the ultimate outputs.
But in a sense a library with every “book” of one million characters has less information than a library with a single book. It does not have zero information since it does not contain many books of 1,000,002 characters. Programs to generate outputs with little information (all possible strings) are of course less complex than programs to generate output with significant information.
Just consider a channel carrying books from your all possible million character book library. Any noise on this channel cannot be corrected, since any noise not adding or removing characters will result in a valid book in the library. A stuck at zero or stuck at one fault on the channel will also result in valid books.
So while your point is literally correct, it just says that it is less complex to generate random junk than output with meaning. (The randomness is not important here, since random strings carry lots of information. It is that all strings are generated.)
