Monday Night Geekazoid Bullets

Some things that research in theoretical computer science teaches you:

• To escape a garden maze, always turn left at any intersection.  (Also known as depth-first search.)
• Being a good Tetris player is exactly as hard as finding the shortest tour of a group of cities that visits each city exactly once.  Well, in an asymptotic sense, anyway.
• There is no such thing as intelligence, at least the way we commonly think of it.  Over forty years ago, researchers wrote a computer program that arguably passed the Turing test for artificial intelligence, at least back then.  Interestingly, that same program probably would not pass today, in our more machine-enlightened society.   Besides factual knowledge, intelligence is also fundamentally biased by emotion and perception: there are varieties of intelligence, from bean counting to empathy, none of which is lesser than another.  Most people have intuitively known this in some form for a long time, but it is starting to become formalized.  This has deep implications for, e.g., communication with dolphins (who are possibly just as "intelligent" in some sense as we are).
• Observations on the random motions of miniscule tea leaves led to the basis of modern financial market analysis.  Not really computer science, per se, but we got our fingers in that pie in the end, and pretty deeply at that.
• We can be paid to think about marriage, at least insofar as it is just a metaphor for scientifically interesting abstractions.  Which is not to say that real human marriage doesn't fall in that category somewhere, just that computer science theorists wouldn't touch that reality with a million-foot pole.  That's sociology.
• An individual person can never comprehend all comprehensible scientific problems, but a group distributed over an infinite period of time can.  Social cooperation, which seems to be encoded into our behavior, is the basis for all success.  The question now becomes: is time infinite?
• There exist infinitely many incomprehensible scientific problems.  This is neither a refutation of science nor a support of mysticism, it is simply a numerical reality in the sense that neither an individual nor a group can survive for an uncountably infinite period of time since both are countable.
• DNA is just a formal language.  Its expression therefore becomes a computational problem, and so, say, the possible cure of all possible genetic diseases nothing more than a matter of computer time, at least in theory.  And yet the bulk of our computer power is reserved for the NSA: breaking codes.  One wonders if we 21st century humans are really that far removed from our ancestors in 10,000 BCE.

These are the things that I think about on a monday night.  Perhaps we should have made fish tacos again, instead of turkey burgers; I have always found turkeys to be problematic animals.  Anything that makes a loud noise directly before settling in for the night seems to me to be troubling in some sense.

On Chaos

Postulate a model of a population of creatures that live a year,  a model that could be used to predict what the population of those creatures will be next year, given this year's population and some lumped parameter that captures the combination of their ability to reproduce and the predatory influence upon them. One such model is:

x_n+1 = rx_n(1-x_n)

Here, x_n is the population at year n (ranging between 0, or no individuals, to 1, or the maximum number that the habitat can support), and r is that lumped parameter.  This particular model has been used for (among other things) predicting populations of temperate latitude insects such as univoltine lepidoptera,
whose adults emerge in the spring, mate, lay their eggs, and die. The eggs in their turn hatch into caterpillars that feed during the summer and overwinter as pupae. Come the following spring, the cycle repeats.

This type of equation is called a map.  This one in particular is called the logistic map.  What this map basically says is: next year's population is proportional to three things, (1) the reproduction/predation constant for this year, (2) the current population, and (3) the remaining empty carrying capacity of the habitat to support new individuals.  (Here a low value for r means that predation is high and reproduction low.)

Here's what the map looks like, when plotted in cartesian coordinates:

Simple, eh?  A concave-down parabola.  The maximum is at r/4, by the way.  This is all pretty simple stuff -- basic first year algebra, the kind of stuff that we took in high school.  But it starts to get interesting if you start putting real numbers into that map.  Say you start with some value, x₁, and you crank through the map and compute x₂ (having chosen some arbitrary value for r). Now say you keep going, computing successively more iterations. What happens? Well, maybe this:

A bit of explanation. You see on the right the concave-down parabola, but there's also a diagonal line.  This line is the line x_n+1 = x_n.  That is, it's where the x-axis equals the y-axis: 1=1, 2=2, etc.  The reason it's there is because this is a map: we choose an x₁, which maps to a point on the parabola, and that point becomes x₂, which maps to a new point on the parabola, ad infinitum.  So the diagram on the right is showing this successive series of steps, in what is called a Cobweb Diagram.  (The graph on the left is just illustrating the yearly change in population, how much x_n+1 differs from x_n.)

Why do we care about this?  Well, if you look carefully, you can see that iterating this map with these values is causing it to collapse to a single point -- the very point where the diagonal line intercepts the parabola.  If you enter that value into the map, you'll get the same value back out.  In mathematical terms, this is called a stable attractor, and in biological terms, it means that the population has reached homeostatis -- predators and environment and reproduction are at a point of equalization, with the population regenerating itself each year (neither growing nor declining).

Now, here's the thing: if there are stable attractors, then there are also unstable attractors.  Populations that grow and dwindle regularly.  A boom, a bust, a boom, a bust, etc.

Nonlinear dynamicists such as myself call that sort of behavior a 2-cycle: there is a single attractor, with two orbits around it.  Boom, bust, boom, bust.  But there is nothing magical about the number two; the Logistic Map can exhibit 4-cycles, too.  And 8-cycles.  And 3-cycles: it doesn't have to be even.  But here's the thing: as you change "r," the cycle changes happen regularly.  First there's a single orbit.  Then two.  Then four. Then eight.  In fact, it's so regular that you can even plot it the number of orbits as a function of "r," and it looks like this:

If you've read this far, then at this point, if I were you, I would be saying WHAT. THE. FUCK.  Because, seriously, what the hell is that diagram, and how did it come from the simplest possible conic section formula known to mankind?  As in, a parabola?  The simplest thing that we learn in algebra?  In HIGH SCHOOL?

Brief explanation: at approximately r=3.0, the Logistic Map enters a 2-cycle.  Hence the branch there, and the two paths.  At about r=3.45, it enters a 4-cycle.  And so on.  The interesting bits are the busy dark areas: that is Chaos.

In the simplest, we find the most complex.

Ringtones

I'm bored and making ringtones for my iPhone.  So far I've made one from the Python theme, the Planet Unicorn theme, and a random Bean Song.  What else should I make?  Oh, and does anyone have a special request?  I'm like a ringtone fountain of youth here.

Right now the Python theme is my active ringtone.  Heh.

By the way, that Rancho Gordo bean video was pretty much spot on, and we had a damn good bean dinner because of it.  Oh, and we were very jolly the entire time!  Amusingly, I was in another room trying to read when Laura fired up that you tube video, and all that I heard was the music.  I couldn't help thinking What In God's Name Is She Watching Out There?  A video about beans was probably the last thing that I would have guessed.

Geek Jokes I

Q: What is a polar bear?
A: A cartesian bear after a change in coordinates.
 

Curious Facts About Time

Years ago, I wrote a dissertation on the synchronization of clocks to earn my Master of Science degree, a fact that has come in handy for some work that I'm currently doing now.  Also, it's just freaking interesting stuff.  Some thoughts:

• Every few years, scientists at NOAA introduce a leap second into the official time.  Why?  Because the rotational speed of the earth is slowing down due to tidal friction.  There have been 24 leap seconds added since 1972, which comes out to about 0.65 added leap seconds each year.  At this rate, the day will have 25 hours in about five and one-half millenia.  If you can wait the same span of time since Julius Caesar crossed the Rubicon in his coup d'etat against the Senatus Populusque Romanus (SPQR), then you'll get an extra half hour for your lunch break.
  
• Those same kind folk at NOAA broadcast an AM radio signal from station WWV that reports the current time, accurate to within about a second or so.  That's what all those self-setting clocks listen to, and it's how they set themselves.
  
• There is no such thing as simultaneity, at least not for everyone.  This is a consequence of relativity.  Events that I perceive as being simultaneous may not appear the same way to you, with one or the other happening first.  This has deep implications for cause-and-effect, and it places fundamental limits on just how synchronized two clocks can be. 
  
• Einstein's investigation into relativity began in his childhood.  He reports that he wondered what he would see in a mirror, were he to hold it and go faster than the speed of light.  The fundamental insights of Special Relativity are nothing more than simple algebra problems that follow from the assumption that the speed of light is fixed and the fact that the hypotenuse of a right triangle is longer than its other two sides.  From these two facts, Einstein deduced gravitational lensing and the bending of light itself, time dilation between reference frames moving at wildly different speeds, and the heady conclusion that space itself can be warped and bent.
• Before the Big Bang, there was no time.  Hence it makes no sense to say "before the Big Bang."  Astronomers now know the structure of the universe after only the tiniest of increments after the Big Bang, but nobody can yet say what was there "before," and they never will because there was no before.  The $1,000,000 question is: what started time?  Who wound the clock?
  
• The universe is now bigger than there is time enough for light from one end to reach the other, and it's still expanding faster.  Hence light from the most distant star on your left will never reach the most distant star on your right.
• Buddhists have a saying that the only time is the Now; everything else is simply noise in our minds.  That to find happiness, one need only quiet that noise and live in this moment, the one right now.
• Although today we keep track of local time via standardized time zones, these are only rough approximations.  There exists the notion of a true local time at every point on the globe.  The local time for you, a few miles away from me, is a few minutes different than my own.  Mariners once used this notion (along with a sextant) to find when the sun reached its apex at noon, and by comparison to a known standard (GMT) could compute how far east or west they were of that standard based on the difference between local noon and GMT noon.  Every 15º change in longitude represents one hour's difference in local times.
  
• To make that computation, they needed accurate clocks.  Even a small drift in the clock time could lead to many miles of error in the longitude calculation.  Pendulum clocks -- the most accurate of mechanical land-based clocks -- are useless on a pitching and rolling ship.  In 1714, Britain announced a prize of £20,000 for the first person who could design a non-pendulum clock that would be accurate enough for longitude calculations at sea.  The winner, John Harrison, labored until 1761 before finally succeeding.  The golden age of the British Navy followed shortly thereafter as they used this new tool to build (and later defend) an Empire.
  
• Pendulum clocks placed in proximity on the same wall will eventually synchronize their pendulum motions due to subtle physical feedback motions imparted to the wall.  What appears to be a solid wall is in fact an elastic medium through which the two clocks find a common harmonic swing.
  
• The motion of a pendulum, although described by what may be among the simplest of physical equations, becomes indeterminate and chaotic -- the most complex of dynamic behavior -- when driven by an outside force.  (Hence the unusability at sea!)
• It is possible to determine North if you're lost using only an analog watch.  In our northern hemisphere, point the hour hand towards the sun, and then bisect the angle between the hour hand the the 12 o'clock mark.  That line is the north/south line; north will be the direction further from the sun.  (Same deal in the southern hemisphere, except north is the direction closer to the sun.)  Don't have an analog watch, but you know the correct time, you digital watch wearer, you?  A drawing of an analog watch on a piece of paper works just as well.  Can't see the sun due to overcast?  As long as you can cast a shadow, you do the same thing with a drawing on the ground and a stick.  If all this is too much to remember, then just remember this: wait until noon, and then walk away from the sun.  You'll be walking north.  (Or towards the sun, for you lucky Southern Hemisphereans.)
  
• Not exactly a time fact, but a lost-persons fact: if you are lost, and an aircraft flies overhead and spots you, do NOT wave your arms to attract attention.  That is the "wave-off" signal that signifies that all is well and that you do not need help.
• The Global Positioning System (GPS) that you use in that TomTom navigator in your car works by comparing differential time updates between satellites.  Each satellite is, in effect, an orbiting atomic clock with a radio transmitter.  The GPS you use knows where the satellites should be, and by comparing the differences in reported time from several, it can triangulate its location relative to the satellites.  Commercial and military GPS systems probably have the same precision (i.e., not much variability in their estimates), but the commercial signal is intentionally downgraded in accuracy (i.e., the exact location they decide you're at is not as good).  Even so, the high precision means that even if you don't know where you are to within +/-30 feet, you can still see a two-foot change in position, anywhere on the earth's surface.  Such is the power of the nanosecond.