Saturday, November 30, 2013

On the pace of change in human technology

Lately, I've been listening to the BBC podcast of A History of the World in 100 Objects.  The program is full of all sorts of illuminating information about the history of humanity, but I want to focus here on three of the eariler objects
At first glance, these seem pretty similar.  They're pieces of hard stone that have had pieces knocked off of them to make tools.  The hand axe and the spear point have the same general form, though the spear point is considerably smaller.  If you had to guess what kind of creature made each object, you might well think that the hand axe and the spear point were made by the same creature, or at least similar, while the chopping tool was made by something much less sophisticated.  But that's not quite the case.

All three objects were made by members of our genus, Homo.  That is, they were made by primates that walked upright like us and, at least by comparison with other primates, had skulls and teeth more or less like ours, and so on.  However, the humanoids who made the chopping tool were definitely not modern humans.

Why not?  First, they didn't look like us, even if they looked more like us than like other apes.  The chopping tool is found with the bones of Homo habilis, which, while it walked upright, had longer arms than us and a smaller skull, was considerably smaller overall, and showed a greater size difference between male and female than humans do.  If we'd seen a group of habilis out walking around, we would probably have thought "Those are interesting-looking apes.  Almost human, even." and not "Those people look weird."

Second, Homo habilis doesn't seem to have been able to make much else out of stone.  Yes, several other kinds of tools are found at the same site, but not many kinds, and all made basically the same way: Take a more-or-less hand-sized rock and knock a small number of chips off it.  The end result looks much like the original piece of stone.  In fact, it's also possible that what we see as a chopping tool is actually just the leftover and it's the sharp flakes that the makers were after.  Or they could have used both.  In any case, the formula is simple: Knock one rock with another, use what you end up with.

Despite appearances, it's also quite clear that the makers of the Archeulean hand axe were not human.  From skeletal remains, they were Homo ergaster (or African Homo erectus, depending on your classification).  To be sure, the tools found with them are the result of a more elaborate process than habilis's chopping tools.  After hammering the core stone with another stone to flake parts of it off, the stone is then worked with bone, wood or antler to refine the shape.  This gives longer, sharper edges than Oldowan tools have, and the hand axe is much more symmetrical than the chopper, but again, there are only a few basic tools in the toolkit, and this toolkit remains the same for hundreds of thousands of years.  [As one would expect from an area of active inquiry, there has been some new information about hand-axes and such since I first wrote this, but the basic picture is still a small repertoire of tools with little or no change for thousands of generations.  I may return to this topic ... --D.H. 15 Oct 2014]

The simplest explanation for the the Oldowan and Acheulean toolkits is that they were the product of instinct, not some general tool-making ability.

I think, if we weren't talking about human ancestry here, this would be an open-and-shut case.  Since we are, I suppose I should elaborate on that a bit.  Because the chopping tool and hand axe are being presented as early human tools, it's natural to look at them and think, especially in the case of the hand axe, "Of course.  They're too complex and sophisticated to be the result of instinct, and they were clearly meant to be used as tools.  That implies a mind capable of intention and forethought."

It's natural to think that, but all kinds of natural, common-sense conclusions turn out not to be true.  This is most likely one of them.

First, consider complexity.  It's hard to say how an Archeulean hand axe is any more complex than, say, a weaver bird nest, beehive or pufferfish circle, to take a few examples.  You could argue that weaving a nest, or making a beehive or circular pattern in the sand is merely a matter of performing a simple behavior repeatedly according to a predetermined recipe -- leaving aside how "simple" that might actually be -- but so too is hitting one rock with another in a symmetrical pattern.

Fair enough, but a hand axe is not just a passive structure.  It is a tool built to be used to help manipulate the environment to a particular purpose.  But other animals do this, too, without any evident abstract forethought.  While there are not a lot of examples of this, there are several well-known ones: a capuchin monkey using a stick to get at termites, for instance, or an otter using rocks to break open a shellfish.

There are even a few known cases of other animals making tools to be used.  Elephants will strip the bark off of branches to make a better switch for swatting flies.  Chimps will do likewise with termite-fetching sticks.  For that matter, building a nest or burrow is no better or worse an argument for forethought.  Both are built for future use.  This is not the same as building a particle accelerator, or even a well-fletched arrow, but it's clearly something.

And yet, there is no particular reason to think that a bird building a nest is consciously thinking "I will build this nest so that I can sleep and brood eggs here."  It's not out of the question, but it doesn't seem at all necessary to assume intent in order to explain the behavior.

In that light, the chopping tool and hand axe look like just another example of animal tool use, perhaps unique in the particular combination of making and using the tool, but not a huge leap from other animal examples.

Let me be clear that I'm not arguing that the Oldowan and Archeulean tools are the product of instinct because they are in some way "simple".  Modern archeologists have learned the "knapping" technique used to produce these tools, and it's harder than it might look.  Rather, I'm arguing that instinctive behavior is not necessarily simple, other animals do similarly complex things instinctively, and in both cases the behavior carries on, essentially unchanged, for generation after generation.

But hold on.  Couldn't we just as well say that the Clovis spear point is the product of instinct?  Sure, we know that we make tools intentionally, but maybe the Clovis people didn't.  The Clovis tool kit is remarkably uniform over the Americas, and most (but not all) finds comprise a handful of different designs of tools made by the same stone-knapping techniques as the hand axe and the chopping tool.

However, there are two big clues that this is not the case, and one even has to do with the title of this post.

First, the Clovis people came along well after humans began to disperse from Africa.  People alive today share a large number of common characteristics unique to humans, such as language with pronouns and other heavy linguistic machinery, music, art, jewelry and, of course, tool-making as we know it.  The most recent common ancestor of all people alive today lived somewhere in the vicinity of 50,000 years ago.

Genetic studies of modern Native Americans in North America show that they share a common ancestor at least as far back as the Clovis people and, of course, belong to the same family tree as everyone else.  There is no plausible way that the Clovis people were not ancestors of people alive today, and no plausible way that those ancestors are not descendants of the original human population.

Why would the Clovis artifacts seem to closely resemble those of habilis and ergaster, then?  Why no Clovis art, beyond a few markings on bone?  Why no evidence of jewelry, or other kinds of artifact found in European sites from thousands of years earlier?

A survey paper by Ryan Ellsworth of the University of Missouri puts forth a plausible explanation:  The Clovis people spread very quickly, over a period of a few hundred years, over a previously uninhabited area, which would explain the uniformity.  They were nomadic, and tended to camp at the kill sites of the megafauna (mastodons and such) that they brought down.  They would not have built permanent dwellings, much less villages or cities, would have had no reason to carry anything bulky and non-functional with them, and probably preferred easy-to-work but more perishable materials for any art or jewelry they did carry.  This is not too far from hunter-gatherer societies encountered in modern times [Much of this type of narrative has been called into serious question, but that'll have to go in a different post -- D.H Jan 2022].

There is still a lot to be learned about the Clovis culture, and there are several competing theories as to who arrived when and did what, but Ellsworth's hypothesis fits the known evidence and is in line with a fair bit of other work.  Even if that particular account doesn't turn out to be the definitive answer, there's no need to reach too far to explain why a population of behaviorally modern humans might leave traces such as we find for the Clovis people.

Which brings me to the second big clue, and the title: Clovis culture is succeeded immediately by a number of other cultures which show a steady development of tools, regional variations and, eventually, the full array of human artifacts, from cities with huge monuments to houses to carved beads.  This happens over a period of thousands of years, much, much too quickly to be explained by genetic change.  Even if some disaster had wiped out humanity in the Americas before Europeans arrived, we would know that these later artifacts were made by people, and the early ones by their ancestors.

In short, the rate of change by itself is enough to make it clear that a generalist tool-user was at work.

This still leaves plenty of questions unanswered.  What happened between Homo ergaster and Homo sapiens [and our cousins such as Denisovans and Neanderthals] to make that shift from instinctive behavior to cultural behavior, learned and passed down from generation to generation?  Why is it that, while other animals can learn new behavior, and to some extent transmit it, we only see this sort of ratcheting effect, of each generation building on the last, in our species?  How did civilization and technology develop in several branches of the human family tree independently, but not to any significant extent in others?  Why does the pace of technological change appear to be accelerating?  Will this continue?

All interesting questions, and I may get to them some time.  Or back to them.  I've had a couple of stabs at some of them already.




Tuesday, November 19, 2013

The crux of the biscuit ...

... is, of course, the apostrophe.

What's an apostrophe?  With that ph in the middle, it's got to be Greek, and so it is. As a rhetorical device, it means "turning away", as when Hamlet turns to address that skull (we're never sure just whose), and in general when a speaker switches from addressing those present to address someone or something not.

So how do we get from there to signs that say "Employee's only" and the eternal confusion between its and it's?  Let's start with the second item first.

For whatever reason, what stuck in my mind coming out of grade school was that the apostrophe was the way you formed possessives.  Finnegan's Wake.  Hobson's Choice.  David's blog.  That kind of thing.  And, by the way, it was also used for contractions.  Let's dance.  I'd've preferred not to.  But actually, I had it backwards.

In fact, the original use of the apostrophe is to indicate left-out letters.  If you squint just right, that makes the connection to "turning away".  Thus you'll see 'd all over the place in Elizabethan literature, a good clue that a past tense is going to be pronounced as we do now, without making a syllable of the -ed -- a consummation / Devoutly to be wish'd, as opposed to Of unimproved mettle hot and full, where the -ed gets its own syllable, as the meter dictates.  You'll also often see the -ed spelled out but not pronounced, so that's not a sure indication, but if it's not spelled out, you can be pretty sure it's not pronounced, either.

Written Elizabethan English uses this a lot more than we do, and not just for particular suffixes
  • O, what a noble mind is here o'erthrown!
  • My lord, you played once i' the university, you say?
  • Use every man after his desert, and who should 'scape whipping?
The 's for possessives is just one more example of this.  Chaucer, living a couple of centuries before Shakespeare, would write -es, to be pronounced as a syllable:

  • And in a glas he hadde pigges bones (again, the meter dictates that both the e in hadde and the es in pigges are pronounced)

We would write And in a glass he had pig's bones (never mind why).

The apostrophe seems to have more to do with pronunciation than omitting letters per se.  Where Chaucer wrote

  • And specially from every shires ende

we would write, and Shakespeare would have written

  • And specially from every shire's end

The e is still there, but silent, to make the i in shire long, and the two-syllable shires has become the one-syllable shire's.

Thus the apostrophe in the possessive is no different from any other apostrophe, at least etymologically.  The mystery, actually, is why we don't use it in plurals (except when we do -- more on that in a bit).  Chaucer's English uses -es for the plural as well as the possessive, giving it a full syllable

  • Whan that Aprille with his shoures soote

By Shakespeare's time, it's both spelled and pronounced without the e, and with no apostrophe

  • When April with its sweet showers

Why, exactly?  I don't know, and I can't be bothered to look it up.

Which brings us back to its.  The possessive pronouns my, our, your, his, her and their have been around in various forms as their own words forever (or at least, before people started using apostrophes in writing).  In Chaucer's writing, though, the possessive of it is his, as in the quote above.  The usage its only comes along later, by analogy with the other possessive pronouns.  As there was never any extra syllable to leave out, we have its from the start, and not ittes becoming itt's or it's.

If you buy that, it's not hard to see how we got to the present-day standard of apostrophe use
  • Contractions, such as he'd and would've, but only a limited list.  The Apostrophe is no longer productive (meaning usable in new ways -- except when it is …)
  • Possessives, like a dog's breakfast or Joe's garage.
  • But not the possessive pronouns my, our, your, his, her, its and their

But how did we get from that to today's non-standard apostrophe use, particularly in forming the plural, as with the Employee's only sign (which I have actually seen)?  I really don't know, but my guess is that it started out in constructions where it's a bit odd to write a normal ending, as with 86'd.  You could well write 86ed, and people have, but presently it's much less common.  Probably spelling it out, 86ed, makes it harder to read, both because of the numbers and letters jumbled together, and perhaps because there's a little hesitation over whether to pronounce the e.

That makes the apostrophe a convenient way to break up number-letter combinations, and we get the 60's instead of (or as well as) the 60s.  Run into that enough, and it's easy to write employee's for employees.   Interesting, but is there any evidence?  Maybe …

Googling the sixty's gets you results for the sixties, with a link if you really want the sixty's, and sure enough there are more hits for the sixties.  But not a huge amount more.  Generally when there are two forms for a term, one gets many more hits than the other.  100:1 is not uncommon.  In this case, it's not quite that -- 29 million to 4 million.  Google hits are a fairly crude measure of how prevalent a term is, but good enough for our purposes here.  We're helped a bit here in that the sixty is not something you'd expect to possess anything, so most of those hits for the sixty's probably really are plurals.

On the other hand, "two babies" (I used "two" so that the baby's form is unlikely to be a possessive) gets around a million, while "two baby's" gets around 16,000.  I wouldn't read too much into two data points, but this at least suggests that constructions like the 60's are prototypical and constructions like two baby's are built from them by analogy, but not as readily.

I'm not condoning any of these usages, though I've been known to use constructions like 86'd and the 60's (and for that matter it's for its, but not so much after reading Eats, shoots and leaves).  You wouldn't want to advertise your skill's on your resume, but employee's on a handwritten sign somewhere is not a big deal.  My point, rather, is that non-standard usage is not a completely haphazard affair, any more than anything else to do with usage.  There is generally a reason, even if it's not likely to convince an English teacher or proofreader.

And don't even get me started on quotation marks.



Thursday, October 24, 2013

Arising by chance

Suppose you had a billion dice.  How many times would you expect to roll them before you got all sixes?  That would be six to the billionth power, or about ten to the 780 millionth, that is, a one with 780 million zeroes after it.  As big numbers go, that's bigger than astronomical, but still something you could print out, if only in tiny digits on a very big sheet of paper.  It's smaller than the monstrously big numbers I've discussed previously.  Archimedes' system could have handled it (see this post on big numbers  for more details on all that).

"Bigger than astronomical" means that there's essentially no chance that anyone will ever see a billion dice randomly come up all sixes, even if, say, we set every person alive to rolling a die over and over again, and on through the generations, even if we somehow colonized the galaxy with hordes of dice-rolling humans.

Now suppose that instead of rolling all the dice repeatedly, we just re-roll the ones that didn't come up sixes.  In that case, a bit more than 100 rolls will do.  Why?  With the first roll, about a sixth of the dice -- around 167 million, will come up sixes.  On the second roll, around a sixth of the 833 million or so remaining, or about 139 million, will come up sixes, leaving about 694 million.  Since we're rolling random dice here, these numbers won't be exact, but because we're rolling a whole bunch of dice, they'll be pretty close, percentage-wise.  With each roll there are about 5/6 as many dice left to roll as with the roll before.

At some point, you can no longer assume that close to 1/6 of the dice will come up sixes, but after 100 rolls you should be down to about a dozen, and it won't take too long to get the rest.

One more game before I explain what I'm up to:  Same billion dice, but this time, after an initial roll, you pick one die at random and roll it if it's not a six.  How many times do you have to do this pick-and-roll (sorry) before you have a complete set of sixes?

At the beginning, you have about 833 million non-sixes and it will take about seven tries before you change one of them to a six.  As more and more dice get changed to sixes, it gets harder and harder to find one that isn't already there.  The last die will take about 6 billion tries -- you'll need to roll it about six times, but you'll only get a chance to one in a billion tries.  All told, according to Wolfram Alpha's handy sum calculator, it will take about 20 billion tries before you get all your sixes.  That's not something you could do in an afternoon.  If you could do one try every second, it would take somewhat more than 600 years.  Not really feasible, but not unimaginable.


If we want to talk about something arising by a random process, it matters, and it matters a lot, what kind of random process we're talking about.  In a purely random process, where everything is re-done from scratch at every step, most interesting results will be completely, beyond-astronomically unlikely.  But a process can proceed randomly and still produce a highly-ordered result with very high probability, as long as there is some sort of state preserved from one step to the next.

For example, when sugar crystalizes out of sugar water to make rock candy, it is for all practical purposes completely random which sugar molecule sticks to which part of the growing crystal at any given point.  And yet, the crystal will grow, and grow in a highly, though not completely, predictable fashion, all without violating any laws of thermodynamics.

The end result will be something that would be completely implausible if sugar molecules behaved completely randomly, but they don't.  They behave essentially randomly when drifting around in a solution, but not when near a regular surface of other sugar molecules that's already there.  With each molecule added to the crystal, it's that much easier for the next one to find a place to attach (until enough sugar has crystalized out that the system reaches equilibrium).


Put another way, there is no single such thing as a random process.  There are infinitely many varieties of random process, some with more or less non-random state than others.  It's not meaningful to ask whether something could have arisen at random without specifying what kind of random processes we're talking about.

Saturday, August 10, 2013

Not in our lifetime vs. never in a million years

The great physicist Enrico Fermi once asked "Where is everybody?", by which he meant "It seems quite likely that there are other civilizations in the universe, so why haven't we seen convincing evidence?"

Without going into detail, I agree with Fermi that there's no convincing evidence that there are other civilizations in the universe.  However, despite the lack of smoking-gun evidence, I'm pretty well convinced there is life elsewhere in the universe, even in our own galaxy.  It seems reasonably likely that there is life within our neighborhood, and not out of the question that there is some form of life elsewhere in our solar system.

I also think it's pretty likely that there are intelligent civilizations (leaving aside exactly what that means) in our galaxy, and almost inevitable that there are such civilizations somewhere in the universe besides here.  So again, why haven't we heard from them?

When we use terms like "in our neighborhood", it's easy to forget that, when talking about astronomy, "neighborhood" is a very relative concept.  Here, I'll use "in our neighborhood" to mean "within 50 light-years, give or take a few percent".  That's close enough that we could send a signal and get a response in something on the order of a human lifetime.  It's also vastly farther than we have ever travelled, or could hope to travel with any kind of technology we know.  Within this 50 light-year radius there are about 2,000 stars.

Compared to our galaxy, this is a pretty cozy little corner.  Our galaxy is much bigger, on the order of 100,000 light-years with hundreds of billions of stars.  The observable universe is much, much bigger still, with some hundreds of billions of galaxies, depending on how you define "galaxy" and "the universe", each with a huge number of stars.

Summarizing: If you talk about "the galaxy", you are talking about on the order of a hundred million times more stars than our neighborhood, and if you're talking about "the universe" you're talking about on the order of a hundred billion times more stars than the galaxy, or on the order of ten quintillion times more stars than our neighborhood.  If only one in a million stars harbors an intelligent civilization, then there are almost certainly no others in our neighborhood, but some hundreds in the galaxy, and tens of trillions in the universe.



That one in a million figure is just for the sake of illustration.  At this point, we really don't know how likely or unlikely life is, if only because we don't have a lot of data points to go on.  We know for sure there's life on Earth.  It looks pretty unlikely that there's life on the Moon, or Mercury.  If there's life on the surface of Venus, it's got to be pretty bad-ass, but the best guess is probably not.  The jury's still out on Mars; we're pretty sure it had liquid water, but not at all sure either way about the life part.  Quite possibly there used to be but isn't any more.

There are a couple of other possibilities.  Jupiter's moon Europa probably has considerably more liquid water than we do, Saturn's moon Enceladus appears to have a large subsurface ocean, and Saturn's moon Titan has a dense atmosphere and pools of liquid.  Methane and ethane, that is, at a temperature of about -180C (-292F).  Could life develop in either of those environments?  We really don't know, but, maybe.  Certainly not a definite "no way", particularly since we've discovered life on earth in all kinds of extremely harsh environments where we used to think life had no business being.

It's also possible that there is some form of life in the clouds of the gas giants or floating in Venus's thick atmosphere, or on some less likely-looking moon than Enceladus, Europa or Titan, but at this point, Mars, Enceladus, Europa and Titan look like the best bets.

By that reckoning we have, in our solar system, one place that definitely has life and four others that plausibly might have, or might have had.  From what we know, our sun is not a particularly unusual star for our purposes here.  There are plenty of other main sequence stars of similar mass and age, and from recent discoveries, it looks like there are plenty of planets outside our solar system.  There are also plenty of stars not like our sun, but still with planets that might plausibly hold life.

Again, we don't know what the real odds are, but we can try to break things down more finely.  We might consider that any planet or moon with a large amount of liquid water is "favorable to life".  In our solar system, that would mean us, Europa or Enceladus (so far ... the jury is still out on Jupiter's moons Ganymede and Callisto).  Before too long we might have a good guess at how common such situations are.  For the sake of the argument, let's say that one in ten stars has such places.  Likewise, we could guess that there's a 50% chance that a place favorable to life actually develops life.  So that's one star in 50, or about 40 in our neighborhood.   And so forth.

This exercise of taking wild guesses at probabilities and multiplying them together goes by the formal name of the Drake equation (though it probably originates with Fermi).  Writing a formal equation doesn't reduce the wide error bars on our guesses about, say, how likely life is to develop or what portion of planets have favorable conditions, but it does give a well-defined framework for talking about such things.   That's helpful, but if you hear a statement like "According to the Drake equation there are N other technological civilizations in our galaxy," whether N is zero or a million ... um, no.  All that means is that under someone's particular set of guesses, there would be N technological civilizations.

You could make a reasonable argument that we're not just guessing at the numbers to plug into the Drake equation, we're guessing about what some of the terms even mean.  What is life, after all?  Does "technology" mean essentially the same thing for all possible kinds of life?



I suppose at some point I should explain the title of this post.  Why not start now?

Suppose that there's a planet fifty light-years away orbiting a star identical to the sun and with the exact same history and technology as us.  Could we detect signs of intelligent life from it?

The Earth (and so, therefore, Twin Earth) has been pumping out radio signals for about a century.  This means it's at least physically possible that we could pick up Twin Earth's broadcast signals from fifty light-years away.  Right now we would be picking up Twin Earth radio and TV shows from the early 1960s.

Before getting too excited about that, keep in mind that Twin Earth's radio signal is going to be very, very faint at that distance and right next to a much brighter radio source, namely Twin Sun (which is still pretty faint compared to most things we can pick up with radio telescopes).  Radio telescopes, even the really big lots-of-dishes-hooked-together kind, have considerably lower resolution than optical telescopes, and as far as I know we're not even close to being able to distinguish Twin Earth from Twin Sun in the radio frequencies, even if they were similarly bright.

Maybe we could, with a few more advances in technology and after careful observations, figure out that something unusual was going on around Twin Sun, but we're not just going to point a radio dish at Twin Earth and tune in to The Beverly Hillbillies.  Which may be just as well.

At this stage in our development, we are at the beginning of being able to contemplate detecting something like a civilization similar to ours orbiting a star in our immediate neighborhood.  Our telescopes (optical and radio) will doubtless improve, and we'll figure out ways of squeezing more and more information of of the signals they provide, but at the same time something else is going on: Earth, and therefore Twin Earth, is liable to go dark.

I'm not talking about civilization ending in the near future, or humanity morphing into some sort of cyber-species with no need for physical bodies.  Whatever you think the odds of those things may be, we're probably not going to spend too much more time spewing radio waves into empty space simply because it's wasteful.  Ultimately, it reduces bandwidth.  Even now, we can listen to the radio and watch TV over land-based connections.  That's probably just going to get more and more prevalent.  There's a good chance that through sheer technological progress we'll stop sending out whatever faint signal we've been sending.

So say that we, and thus Twin Earth, spend about 200 years sending out a radio signal indicating intelligence.  There are other ways we might detect Twin Earth and deduce that it has life, but only through a structured signal like our radio transmissions would it be clear that it was intelligent life -- OK, we could also look for Dyson spheres and such, but let's not go there just now.  It's also possible that Twin Earth could decide to deliberately send out a signal, permanently, to every star in its neighborhood, after it stops using high-powered radio broadcasts.  But "permanently" to creatures such as us is "momentarily" on planetary time scales.

To get a feel for what that last statement means, suppose that Twin Earth is like us in every way, except that it formed just a little bit earlier or later.  Say a tenth of a percent earlier or later.  Earth is about 4.54 billion years old.  A tenth of a percent of that is 4.54 million years.  If Twin Earth formed a tenth of a percent earlier than us, then we're several million years too late to pick up the brief flash of detectable signals of intelligent life it put out.  If it formed a tenth of a percent later, we won't have a chance to detect its hairless, tool-making social primates for millions of years yet.

This is why Drake's equation has a factor for how long we guess that an intelligent civilization would put out a detectable signal.  Obviously, the Twin Earth scenario is a gross simplification compared to the possibilities of life in the universe, but I think it sheds some light on the Fermi paradox.  There's a decent chance that everybody's out there, or will be at some point in the future, but we just plain missed them or they're not even here yet.



Electromagnetic radiation, which is all we currently know how to detect from other star systems, follows the inverse square law.  Twice as far away, a signal is four times fainter, three times farther away, nine times fainter, and so on.  That means that a star system 20 light-years away would have to produce a signal four times as strong as one 10 light-years away in order to be equally detectable.

Earth has has broadcast some sort of radio signal into space for the past hundred years or so, but at first that signal was very weak -- just a single small transmitter.  Eventually it grew, and quite likely it will eventually fade out.  The amount of time we've spent transmitting our brightest signal is shorter than the time we've spent broadcasting half that signal, and so forth.

Just so, the amount of time that a given civilization spends putting out a signal that we could detect decreases with distance.  At some point, probably well within our galaxy, it becomes effectively zero.  There could be civilizations 1,000 light-years away (again, the Milky Way is about 100,000 light-years across) that never have and never will put out a signal bright enough for us to detect.

In short, the search for extraterrestrial intelligent life probably boils down to watching a few thousand star systems in our immediate neighborhood for signatures of intelligence.  It seems quite plausible that some number of those planets harbor life, and that of those, a not-too-much smaller number of those have developed or will develop intelligent life and at some point in their histories, and for a brief time, put out something we could detect.

If that's the case, then some portion of them have already passed their detectable phase.  Maybe there are a dozen out there that have yet to announce themselves.  As always, a wild guess.  There might be none at all.  There might be hundreds, but probably not much more -- there are only so many stars close enough.  If there are such a dozen, and we can keep listening, we'll eventually spot one.  But "eventually" here likely means millions of years, not decades.

Are we likely to detect signals from civilizations around other stars?  Not in our lifetime, I'd say.  But some time in the next million years?  Maybe.



Postscript: I forget where I saw this mentioned, but another problem is that as our radio communications get more and more efficient, the signal we put out gets hard and harder to tell from noise.  Faint as it may be, a morse code radiotelegraph signal is clearly non-random and statistically unlike anything known to be naturally produced.  A compressed digital television signal looks much like random noise, which can come from any number of sources.  Mix together all the digital television signals currently broadcast on earth and you get something even more like noise.  Probably the only way we could detect a signal from Twin Earth and tell that it was a signal from something intelligent, would be for them to be sending a signal directly at us.  But if they're like us, they're only beaming signals to a few stars, and for relatively short periods of time.

Post-postscript: Randall Munroe's What If makes most of the same points as here, with a lot fewer words (and a couple of pictures).

Wednesday, August 7, 2013

Colonies and organisms

Is an ant colony an organism?  Strictly speaking, no.  Individual ants are organisms.  An ant colony is ... something else, a something else called a "colony" or "superorganism" or some similar term.

Why even ask?  My purpose here is to try to pin down what "colony" and "organism" might mean.  As with most terms, there are quite a few choices, once you start looking.

If someone speaks of, say, a city as an organism, there's a strong element of metaphor.  Yes, a city can be said to collectively eat, and breathe, and even make decisions, but a city isn't actually an organism.  It just has enough of the features of one to make for interesting comparisons and analogies.

On the other end, there are stands of aspen (and other plant species) that appear to be individual organisms, but are actually connected by a common root system and are genetically identical.  Technically, this is a clonal colony, but we would generally think of each tree as an individual organism.

We might similarly think of a cluster of mushrooms as consisting of several organisms, but in fact mushrooms are just reproductive organs.  It's the mycelium, a web of root-like structures in the soil, that carries on the day-to-day activities of a fungus, whether or not any mushrooms are evident.  Since mushrooms are temporary structures, analogous to flowers on plants, and don't survive on their own, it seems reasonable to think of the mycelium and any attached mushrooms taken together as an organism.

On the other hand, trees are permanent structures and it's normal (depending on the species) to find a tree living independently, or next to other trees of the same species that aren't genetically identical.  This probably makes it less intuitive to say that a stand of aspen is a single organism, so we hedge and say clonal colony.

Banyan trees are an interesting case.  As their branches spread, they drop aerial roots, which eventually grow into the soil and support the further spread of the branches.  Banyans can grow to cover several hectares (or several acres, if you prefer).  Since everything is connected in plain sight, it's easy to speak of a single large tree, even though it may not be immediately obvious that all the "trunks" in what might seem to be a grove of youngish trees are actually roots of a single tree.  If the aerial roots and the low branches they drop from were below the ground, though, would it then be a clonal colony?

To a large extent this is just a mater of nomenclature.  What matters more is whether the pieces are connected or not, and whether they are genetically identical or not.  All four combinations are possible:
  • A banyan tree or aspen grove is connected, and the parts are genetically identical
  • The trees in an apple orchard are separate but genetically identical.  That is, they are clones (strictly speaking they collectively make up a clone -- we've been genetically engineering plants for millennia).  It's also possible for a clonal colony like an aspen grove to be split into disconnected parts.
  • Lichen -- which Wikipedia calls a "compound organism" -- is a symbiosis of a fungus and a photosynthetic partner, generally either an alga or a cyanobacterium.  They are physically intertwined and the one could not survive without the other, but they are quite different genetically.
  • Typical stands of forest consist of physically and genetically distinct trees, and this is the normal pattern for plants and animals that we distinguish as individuals.
Where does that leave our ant colony?  Clearly ants are physically distinct.  Genetically, the picture is a bit more complex.  Ants, along with other hymenoptera and a few other species, are haplodiploid.  Males carry only one set of chromosomes, rather than the usual two, while females carry both, because males develop from unfertilized eggs.  Further, the queen of a colony generally mates with only one male over a given time period, and only one female in a colony (the queen) is fertile (or at least only a small portion of females are fertile).  This has a number of interesting consequences:
  • A male gets 100% of his genes from his mother
  • A male has no father and cannot have sons, but does have a grandfather and can have grandsons (This one is worth working through in slow motion.  All the clues are in the paragraph above)
  • A female gets 50% of her genes from her mother and 50% from her father, as usual, but has 75% of her genes from the same source as her sisters and only 25% from the same source as her brothers.
  • Lethal and highly harmful genes get weeded out quickly, since they'll kill off the males that carry them.  With only one set of chromosomes, there's no place to hide.
"From the same source" is distinct from "the same".  If the mother and father carry the same version of a gene -- the same allele -- then it doesn't matter which source it comes from.  But if (to take a human example) mom has blond hair and dad has brown hair but a blond mother, then on average half the kids will have mom's blond hair, with a blond gene from both parents, and half will have dad's brown hair, with a blond gene from mom.  They all have dad as the source of one of their sets of hair genes, but they don't all have the same hair genes from dad.

Selection cares about the variations, so it will tend to act the same on genetically identical individuals, and more and more differently on less related individuals.  Workers in an ant colony are much closer to identical than ordinary siblings.  This probably helps explain why ants and related species tend to be eusocial, that is, so socially cooperative that individuals will routinely act against their direct self-interest.

In particular, eusocial species typically have entire castes of sterile individuals.  This makes no sense in the narrow sense of individuals competing to pass on genes, but more sense when you look at the overall picture of which genes are liable to survive.  It's not as simple as a sterile soldier ant dying to save two of her sisters, though.  If the sisters are also sterile, this makes no direct difference to which genes ultimately survive.

Probably being 75% related to one's sister makes it more likely that an altruistic behavior will take hold.  That is, an instinct to protect the queen and eggs is more likely to work if one's relatives in the colony share it.  Seems plausible, but the details are complex, and I haven't looked up what real biologists have to say on the topic.  The question here is: If a fertile female has a large number of offspring, significantly more closely related than normal siblings, under what conditions are the queen's genes (and her consort's) more likely to be passed on by children who mostly forego reproducing in favor of one or a few fertile siblings, as opposed to by children who look after themselves?

In any case, haplodiploid genetics don't explain naked mole rats, which are genetically normal rodents, but eusocial nonetheless.   But there can be multiple causes for the same effect.  Naked mole rats are the only known eusocial mammals (or non-insects, I believe).  Perhaps they just happened to be the one diploid organism that developed eusocial behavior far enough for it to remain stable.

Besides being head-hurtingly counter-intuitive to reason about, haplodiploidy, or anything that tends to make behavior more uniform and focused on protecting a small group of fertile individuals and their eggs, tends to make the group look less like a bunch of individuals and more like a single organism.  And I think that's probably where we have to leave the original question.  An ant colony is just that: a colony of individuals which, collectively, has some qualities analogous to those of an organism, and has more of those qualities than groups in many other species.  It is not, however, an organism per se.



But just what is an organism?  In particular, what is a multi-celled organism?  Leaving aside the question of the microbiome -- the microbes living on and inside us that are nearly as different from us genetically as can be, and collectively outnumber our own cells handily -- a multicellular organism is a collection of individual cells, genetically identical (with exceptions like the germ cells -- sperm and egg -- which have a single set of chromosomes instead of a pair).

Most individual cells have specialized roles, and most of these cells are limited reproductively.  In most cases they can divide and reproduce, but not without limit, or at least not in a healthy organism.  Real reproduction, at least in sexually-reproducing organisms. is handled by a small set of germ cells which the other cells, it may be said, act to protect.

You don't have to squint very hard to see this as similar to the case of a eusocial colony.  To be sure, there are some important differences.  Cells in a multicellular organism are basically 100% related.  They are generally unable to survive on their own for any significant length of time.  They tend to reproduce in a fairly well-established pattern.  That is, the organism grows coherently, and consistently from generation to generation.

Should we consider a multi-celled organism really to be a colony of one-celled organisms?  Well, that's one way to look at it, but because those cells act so coherently and consistently, and because they're simple units (Shh!  Don't mention mitochondria and other organelles!), and they're not viable on their own, and I'm sure for a number of other reasons, it's not useful to push this too far, much less claim that's "really" what's going on.

Nonetheless, I think it's still a useful comparison to study.

Saturday, April 6, 2013

Big Numbers

Warning: This post is fairly long and contains a lot more mathematical notation and jargon than I generally like to include, even when the topic is mathematical.  In this particular case it seems pretty near unavoidable, so I'm hoping that the extra work to the reader is worth it.

A wise man once said of numbers "There are too many of them" (or words to that effect).  To which I'd add "and most of them are too big."

In our minds, we have some concept of numbers beyond merely seeing two apples and two oranges and knowing there is one apple for each orange and vice versa.  If I showed you a pile of coins, say, and asked if there were a dozen or so, a hundred or so, or a thousand or so in the pile, you could probably make a reasonable guess as to which was the case, even without knowing the exact number.  Along with a concept of numbers, we have a rough concept of their size.  Which makes sense.

Mathematicians have made the concept of number rigorous in a variety of ways.  I've described some of them, particularly the natural numbers, in a previous post on counting.  The natural numbers are 0, 1, 2 and so forth on and on forever.  They answer the question "How many (of some kind of discrete object)?", which requires a whole number that may be zero but can't be negative.  They generally can't answer "How much (of some substance)?", which need not come out to a whole number of whatever unit you're using, or "What was my score for the first nine holes?" which will be a whole number of strokes but might be negative.

In some sense, the naturals the are the simplest kinds of numbers.  All other numbers can be defined in terms of them.  They certainly seem friendly and familiar at first blush.  I aim here to show that the natural numbers we're comfortable dealing with -- 0, 1, 2, 42, 1024, 14 trillion or whatever -- are an insignificant part of the mathematical picture.  Almost all numbers are far, far to big for us to comprehend in any meaningful way.

Big numbers for puny humans

Let's start with human-sized big numbers.  A thousand might seem like a big number, but if you think about it, it's pretty small, even in puny human terms:
  • You can count to 1000 in a few minutes
  • Crowds of a thousand are commonplace
  • You've probably met more than a thousand people in your life
  • Communities of a thousand or more are commonplace
  • If you can read this, you're almost certainly more than a thousand days old
  • This post has over a thousand words
and so forth.

A million is big, but still not all that big.  It is, though, probably the biggest round number that most of us can relate to directly, even if it may take a little effort.
  • If you spray a reasonably large picture window with water, there are likely a million or so droplets visible on it.
  • You can see see an individual pixel on a megapixel display.
  • Crowds of a million people or more have gathered on many occasions.
  • Many people, though certainly not most, will make $1 million in their lifetimes.
  • $1 million in $100 bills doesn't take a lot of space.  Even in dollar bills, it will fit in one room of a house.
  • Many people have practiced some basic skill a million times.  For example, a typical professional basketball player has almost certainly made a million baskets (counting practice shots); I once met a baseball scout who quite plausibly claimed to have driven a million miles; I've probably written millions of words, all told.
A billion is probably not readily comprehensible, but examples are not rare
  • Human population is a few billion.  Two countries have populations over a billion.
  • A billion dollars is about ten dollars per US household.
  • RAM is currently measured in gigabytes.
A trillion is probably the biggest with well-known commonplace examples
  • Large economies are measured in trillions of dollars.
  • You can buy terabyte disks at the store.
  • You have trillions of cells in your body (and even more bacterial cells).
It's perfectly possible to distinguish a million from billion from trillion, but it requires conscious computation ... oh, a gigabyte of disk will hold a thousand photos of a megabyte each.

A trillion, probably even a billion, is beyond the human scale.  We can speak of trillions of cells or bacteria in the human body, but these are abstractions.  No one has actually counted them, whereas a moderate team of people could count millions of objects (as happens during elections, for example).

Astronomical numbers

The physical universe goes well beyond this scale.  There's a reason we talk of "astronomical" numbers.
  • The observable universe (using "comoving coordinates") is around 1,000,000,000,000,000,000,000,000,000 meters in diameter (one octillion, in US terms as I'll use here, or one thousand quadrillion in "long scale" terms).  When dealing with numbers this big, we generally just count the digits, and say, for example, 1027.
  • There are 6×1023 (Avogadro's number) atoms in a gram of hydrogen (assuming it's purely the light isotope, which it won't be).
  • There are somewhere around 1057 atoms in the sun
  • The smallest distance that can possibly be measured, even in principle, according to quantum theory, is called the Planck length (after Max Planck).  In practice, no one has come even remotely close to directly measuring anything at that small a scale.  The volume of the observable universe in Planck volumes (cubic Planck lengths), that is, the biggest volume we know of measured in the smallest measurable volume units, is on the order of 10184.
Consider that last number.  Ten is a nice, familiar number.  One hundred eighty-four is not intimidating.  So 10184 can't be that big a deal, right?  Well, let's try to put it in terms we can understand.  I've claimed a million is about as big a number as we can really grasp, but maybe we can build up from there.  I have well over a thousand digital pictures, and on average there are a few million pixels in each, so it's not too hard to imagine what a billion pixels would look like.  You can find pictures of a million people gathering, so imagine that each one of them has a similar image collection.  That's a quadrillion pixels -- a thousand million million.  Not bad.

With a little more thought, one could probably put together images for, say, a million trillion or a billion billion, but even my image for a billion pixels is stretching.  I can plausibly say that if I'm looking at a computer monitor I can imagine that each of the pixels is its own unit (it's probably not coincidence that the human eye has megapixel resolution, more or less).  If I'm imagining a thousand photos, though, I'm not imagining each of their pixels as a separate unit.  The unit is photos, not pixels.  At best there's the implication that I could mentally switch scales and think of pixels, at which point the photos fade into abstraction.

If I'm imagining a crowd of a million people with a thousand megapixel photos each, it's harder to argue that I'm really keeping the whole image in my head.  The technique of imagining collections of collections of collections gets less and less useful as we approach the limits of human short-term memory, typically seven or so items.  Maybe, maybe, a person could claim to comprehend a million million million million million million million things.  Maybe.

But 10184 is ten thousand million million million million million million million million million million million million million million million million million million million million million million million million million million million million million million.


Now we're ready to talk about some big numbers.

Archimedes' Sand Reckoner

In The Sand Reckoner, Archimedes set out to do the same kind of measurement as above, of the biggest  known volume in the smallest units.  He wanted to measure the number of sand grains it would take to fill the universe as he understood it.  This was a universe with the Sun (not the Earth) at the center, and the fixed stars in a sphere far enough out that they did not seem to move as the Earth went around the Sun.  In modern terms, it was about a light-year in radius, not too shabby coming from someone from a world with no telescopes or motorized transportation.

The number system in use at the time could count up to myriad, or 10,000.  Archimedes called the numbers from 1 to myriad the first numbers and called myriad the unit of the first numbers.  The second numbers were myriad, two myriads, three myriads and so on up to a myriad myriads (one hundred million), which he called the unit of the second numbers.  Likewise, the unit of the third numbers was that many myriads (one trillion), and so on up to the unit of the myriadth numbers.

This is a decent-sized number.  It's a one with 800 million zeroes after it, much bigger than the size of the modern universe in Planck volumes.  But Archimedes went further yet.  He called the numbers up to this number the first period, and the number itself the unit of the first period.  From that, of course, you can define the second period, and so on.  Archimedes went on to the myriad-myriadth period, ending with 108×1016, or a one with 80 quadrillion zeroes after it.  That's a huge number, but you could still print it if you had, say, enough paper to cover the surface of the Earth (and a printer to match).

As it turns out, this was overkill.  Archimedes calculated the volume of his universe in sand grains to be  1063, a number so small I can write it right here:

1,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000

Archimedes was trying to make a point.  The grains of sand are not beyond reckoning, even if no one person could possibly count them.  They are not infinite in number.

Building big numbers

To build his number system, Archimedes used a simple but powerful approach:
  • Start with some set of numbers
  • Define a rule for making bigger numbers
  • Apply that rule repeatedly to get a larger set of numbers
  • Repeat, using the new, larger set as a starting point
A slightly different way of looking at this is
  • Start with some set of numbers
  • Define a rule for making bigger numbers
  • Define a new rule, namely applying the first rule repeatedly, to get a second rule
  • Define a third rule from the second rule, and so on, repeatedly
For example, start with the numbers from 1 to N, and the simple rule of adding one
  • Starting with N and adding 1 N times gives you N + N, so the new rule is "add N"
  • Starting with N and adding N N times gives you N x N, so the new rule is "multiply by N"
  • Starting with N and multiplying by N N times gives you NN, so the new rule is "take to the Nth power"
There are various names and notations for what happens next, repeatedly taking to the Nth power, but it will get you very big numbers from small numbers very quickly.  You can actually do this two different ways:
  • First take NN, then take that to the N, and so forth. If N is 3, you get (33)3, which is 273, or 19683
  • Take NN, and then take N to that power, and so forth. If N is 3, then you get 333, which is 327, which is 7625597484987
Since the second way gets bigger numbers faster, let's do it that way.

4(44) is 

13,407,807,929,942,597,099,574,024,998,205,846,127,479,365,820,592,393,377,723,561,443,721,764,030,073,546,976,801,874,298,166,903,427,690,031,858,186,486,050,853,753,882,811,946,569,946,433,649,006,084,096

That's big, but 4444 is 4 times itself that many times. The number of digits in the result is itself a number with 154 digits.  This is already much, much, much bigger than Archimedes' big number.  Much too big to write down, even if we used the universe for paper and subatomic particles for ink.  And this is just from applying the third rule on the list to a small number.

Let's not even talk about 55555, or trying to do the same thing with myriad.

[In an earlier version, I'd taken the first option.  It still ended up with big numbers, but not as dramatically.  (44)4 is 2564, or 4,294,967,296, rather than the monster above, and 4,294,967,2964 is 340,282,366,920,938,463,463,374,607,431,768,211,456.  This is astronomically large, but not too-big-to-fit-in-the-known-universe large.  Even (((55)5)5)5 has only 437 digits --D.H. Mar 2022]

But of course, you can repeat the rule building process itself as much as you like.  What if I start with 4444 -- let's call it Fred -- and apply the Fredth rule to it.  Call that number Barney.  Now apply the Barneyth rule to Barney.  And so on.  Just as you can always add one to a number to get a bigger one, you can repeat any hairy big-number-building process some hairy big number of times to get an unimaginably hairier big-number-building process.  Or rather, you can define a process for defining processes and so forth.  You could never, ever come close to actually writing out that process.

(If all this seems similar to the process for building ordinal numbers that I described in the counting post, that's because it is similar.)

Ackermann's function

Ackermann's function, generally denoted A(m,n), boils this whole assembly down to three very simple rules which can generate mind-bogglingly big numbers much more quickly than what I've described so far.  Since we're in full-on math mode in this post, here's the usual definition (other variants are also used, but this one is as monstrous as any of them):

A(m, n) =
  • n + 1, if m = 0
  • A(m - 1, 1), if m > 0 and n = 0
  • A(m - 1, A(m, n - 1)) otherwise
We're just adding and subtracting one.  How bad can it be?

Ackermann's function normally takes two numbers and produces a number from them, but you can easily define A'(n) = A(n,n).  A'(4) is 22265536 - 3, which is vastly bigger than any number I've mentioned so far in this post except for Barney.  Howard Friedman (more from him below) has this to say about A (I've modified the notation slightly to match what's in this post):
I submit that A'(4) is a ridiculously large number, but it is not an incomprehensibly large number. One can imagine a tower of 2’s [that is, a tower of exponents] of a large height, where that height is 65,536, and 65,536 is not ridiculously large.
However, if we go much further, then a profound level of incomprehensibility emerges. The definitions are not incomprehensible, but the largeness is incomprehensible. These higher levels of largeness blur, where one is unable to sense one level of largeness from another.
For instance, A(4, 5) is an exponential tower of 2’s of height A'(4).  It seems safe to assert that, say, A'(5) = A(5, 5) is incomprehensibly large. We propose this number as a sort of benchmark. 
In other words, A'(4) is, as I've argued, far, far too big to comprehend, calculate fully or even write down, but at least we can more or less understand in principle how it could be constructed.  The recipe for constructing A'(5) contains so many levels of repetition that we can't even really understand how to construct it, much less the final  result.

Combinatorial explosions

Everything I've mentioned so far is constructive.  That is, each number is defined by stating exactly how to construct it from smaller numbers by some set of operations, ultimately by starting with zero and adding one repeatedly.  It's also possible to specify numbers non-constructively, that is, without saying exactly how one might construct them.

The field of combinatorics is particularly notorious for defining huge numbers.  Combinatorics deals with questions such as enumerating objects with some particular set of properties.  A simple example would be "How many ways can two six-sided dice show seven spots?" For bonus points, list them exactly, or at least describe their general form.  In this case, it's easy.  There are six, assuming you can tell the two dice apart: {(1,6), (2,5), (3,4), (4,3), (5,2), (6,1)}.

A slightly different kind of combinatorial question is "How large can a collection of objects subject to some particular constraint get before it has to have some property?"  For example, how many natural numbers less than 5 can you put in a set before there must be two numbers in the set that differ by 3?  So {0, 1} is fine but {1, 4} isn't since 4 - 1 = 3.  The answer in this case is 3: {0, 1, 2}, has no members that differ by three, but any larger set must.  In this case, we can easily check because there are only five sets of four natural numbers less than five.  For a larger version, say the same question but for the numbers less than 1000, there's no way to check all the combinations and you'll need a real proof.

Friedman gives a somewhat more involved example that produces large numbers astonishingly quickly.  Consider strings of letters from a given alphabet.  A string of length n has what I'll call Friedman's property if, for at least one i and j up to n/2, with i < j, the portion of the string from positions i to 2i appears in the portion from j to 2j.  In other words, cut the string into overlapping portions:
  • The first and second letters (two total)
  • The second through fourth letters (three total)
  • The third through sixth letters (four total) ...
  • ... and so forth, starting one letter later and going one letter longer each time
Friedman's property says at least one of those is contained in at least one of the later ones, and the question is, how long does a string have to be before you know it must have this property (for whatever reason, Friedman actually phrases the question as how long can a string be and not have this property, but this way seems clearer and is more in line with Ramsey Theory in general).

If the alphabet in question is just one letter, say a, then it's a simple problem:
  • Start with aa.  That's the one and only string with two letters, using our alphabet, and there is only one portion to look at (the whole string).
  • Add another a to get aaa.  There's still only the one portion, so we're still good.
  • Add another a to get aaaa.  Now there are two portions to look at 1-2 (aa) and 2-4 (aaa).  The first one is contained in the second, so we're done.  Any four-letter string (that is, the one and only four-letter string), using one letter, must have Friedman's property.
If the alphabet is just the two letters a and b, then
  • ababba, for example, has the property, because the portion from position 1 to 2 (ab) appears in the portion from 2 to 4 (bab)
  • (taking an example with three letters) aabcabbca also has the property, because abc from positions 2 to 4 appears in abbca from positions 5 to 9.  The letters in the first string don't have to be consecutive in the second one, but they do have to all appear in order.
  • abbbaaaaaaa on the other hand, does not have Friedman's property: ab doesn't appear in bbb, bbaa, baaaa or aaaaaa, and more generally, none of those portions appears in any of the ones after it.
  • If you add either an a or a b to the end of abbbaaaaaaa, though, the result has to have Friedman's property.  If you add an a then aaaaaa (positions 5-10) appears in aaaaaaa (positions 6-12).  If you add a b, then ab (positions 1-2) appears in aaaaaab (positions 6-12).
  • With some more fiddling (at the worst, trying out all 4096 12-letter strings), you can determine that any string, using two letters, 12 or more letters long has Friedman's property.
What if we use three letters, say a, b and c?  You need a somewhat longer string before you can no longer avoid Friedman's property.  How long?  Friedman finds a lower bound (the real answer may be bigger), of A(7198, 158386).  Recall that we've already established that A(5,5) is deeply incomprehensible.  Adding one to either parameter of A just kicks things up another unfathomable notch, and here we're doing so hundreds of thousands of times.

For four letters, Friedman gives a lower bound obtained by applying A' over and over again, starting with A'(1) = 3.  How many times?  A'(187196) times.

Friedman goes on to define a similar construction on trees (groups of objects with parent/child/sibling relationships, more or less like family trees but without fun stuff like double cousins).  Again, things start small but then go completely haywire.  If n is the number of letters you can use in labeling the objects in a tree, and Tree(n) is the largest sequence of trees you can have (subject to a couple of restrictions) before there must be at least one tree that's contained in a later one, then
  • Tree(1) = 1
  • Tree(2) = 3
  • Tree(3) is much, much larger than the result we got above for strings using three letters.  It's much, much larger than the result above for four letters.  It's so large that you have to dive deeply into the foundations of mathematics to be able even to describe it.  Maybe you can.  I can't.
And, of course, once you've got an out-of-control function like Tree, you can use it as grist for the constructive mill.  What's A'(Tree(Tree(Barney))) taken to its own power Fred times?  Can't tell you, but it's certainly big, and we can keep this tomfoolery up all day.

(How do we know that there is a limit on how big a set of strings or trees can get before it has to have Friedman's property?  Friedman gives a proof.  It's a pretty standard proof, but I didn't understand it and didn't take the time to dive into and figure it out.)


It's all just so ... big

As Friedman says, such gigantic numbers (whether defined constructively or non-constructively) are not at all like the numbers we're familiar with.  I can easily tell you that 493 has a remainder of one when divided by three (4+9+3 = 16, 1+6 = 7, 7 divided by three has one left over).  I can't easily tell you whether Fred has a remainder of one or two.  I know there will be a remainder, since at no point in constructing it did we multiply by three, but to figure out which remainder we'd have to carefully examine the definition of Fred and track the remainders all the way through.

Likewise I know that 17 is a prime number and 39 isn't.  With a little effort I can figure out that 14,351 isn't prime (it's 113x127), but is A'(4) - Fred a prime number?  No idea.  Probably not, as the odds of any number that size being prime are very small (though not quite zero), but I have no idea how to go about proving it.

For that matter, it's not always immediately obvious whether one huge number is larger than another.  If they were constructed by different means -- say, one uses Ackermann's function and another came out stacking up exponents some particular way and repeatedly applying three different big-making functions in turn, then there may be no feasible way to compare them.  It may even be possible to prove that the number of steps needed to make the comparison would itself be huge.


We're used to simplifying numbers when we do calculations with them.  If I tell you a room is four meters by three meters with a one meter by two meter closet cut out of it, you can easily tell me the area of the room is ten square meters.  If I did a similar calculation with four arbitrary huge numbers, quite likely all anyone can say is the answer is ab - cd, if a, b, c and d are the numbers in question.

Nonetheless, such numbers are just as mathematically real as any others.  If you make a claim about "all natural numbers", you're not just saying it's true for numbers you can easily manipulate.  You're saying it's true for really big ones as well, and keep in mind that for every huge number we can describe there are vastly many more of similar size that we have no hope of ever describing.  Fermat's last theorem doesn't just say there are no cases where a3 + b3 = c3.  It says that there are no cases where aBarney + bBarney = cBarney, and so forth for every ridiculous number I've mentioned, and all the others as well.

It's also important to point out that there is nothing particularly special about most of these numbers, unless, like Tree(3), they are the solution to some specific problem.  The number of numbers we know to be special for one reason or another is limited by our human capacity to designate things as special, which runs out long before we get to the astronomical realm, to say nothing of the territory Friedman explores.

If a number is too big to relate to our everyday experience, or to compare with other numbers, or to comprehend how it might be constructed, about the only thing we can really say about it is that it's a number, and it's big.

And that's all we can say about almost all numbers.

Tuesday, January 29, 2013

We're #1. So what?

On the radio today I heard that a certain statistic was at its highest (or lowest) level in seventeen months.  Certainly sounds impressive, but what does it mean?  Without having followed the history of the statistic, I'd have know way of knowing.

For example, if it's 100 now, and it was 99 seventeen months ago and 98 for the other months (including last month), it may not mean much at all.  On the other hand, if the sequence had been more like 99, 82, 64, 57, 43, 51, 46 ... 54, 47, 100, that jump from 47 to 100 might be very significant, particularly if the original fall from 99 to the 40s and 50s had been significant.


Suppose I'm part of a community of gamers in which each gamer has a numerical rating.  Last month I had the 1523rd-highest rating.  This month I'm 1209th.  I've just rocketed 314 places up the rankings. Pretty awesome, huh?

Well, maybe.  Suppose there are  704 people with a rating of 98, 313 people with a rating of 99 and 1208 people with higher ratings.  The top rating is 106.  Last month my rating was 98, so I was one of the 704 tied for 1523rd - 2226th.  This month, by virtue of a one-point improvement, I'm now one of the proud 313 tied for 1209th - 1522nd.  Last month I was good, though not quite as good as the best.  This month I got a little closer to the top.  Maybe not so impressive.

On the other hand, suppose there are three million or so players.  Most of them have fairly unremarkable ratings, but once you get to the top ranks the scores start to increase dramatically.  The 1523rd best ranking is 12,096, the 1209th is 451,903 and the top player has an unbelievable 75,419,223.  I've made really amazing strides in the last month, but I'm still far, very far, from the top.


Ok, that's a lot of made-up numbers for just four paragraphs.  What's going on here?

First, any measurement is meaningless without context.  I originally said "a statistic" instead of "measurement", but the whole point of statistics, that is, pulling (abstracting) concise metrics out of a pile of data, is to provide context.  If I say that the mass of a sample is 153 grams, that doesn't tell me much, but if you tell me that the average (mean) mass of past samples is 75 grams and the standard deviation is 8 grams, I know I'm dealing with an extremely rare high-mass sample.  Or my scale is broken, or I'm actually measuring a completely different kind of sample, or something else significant is going on.  The mean and standard deviation statistics provide context for knowing what I'm dealing with.

Simply saying "highest in seventeen months" or "jumped 314 places in the rankings" doesn't provide any meaningful context.  Either or both of those could be highly significant, or nothing in particular.

Second, citing rankings like highest, 1209th and so forth implies that something noteworthy about a ranking is also noteworthy about the underlying measurement that's being ranked.  But this is misleading.  Depending on how the rating is distributed, a large change in rating could mean a small change in ranking, or a large one, and likewise for "highest in N time periods."  Technically, ranking can be highly non-linear.

Rankings are not entirely useless.  For example, there have been many more record high temperatures than record low temperatures in recent decades.  Given that short term temperature fluctuations over more than a few days are fairly random (or at least, chaotic), this strongly suggests that temperatures overall are rising.  More sophisticated measurements bear this out, but the simple comparison of record highs versus record lows quickly suggests a trend in the climate as a whole.  Even then, though, it's the careful measurement of the temperatures themselves that tells what's really going on.  Looking at record highs and lows just points us in a useful direction.

In general, when someone cites a ranking or a record extreme, it's good to ask what's going on with the quantity being ranked.