Mark Chu-Carroll (aka MarkCC) is a PhD Computer Scientist, who works for Google as a Software Engineer. My professional interests center on programming languages and tools, and how to improve the languages and tools that are used for building complex software systems.
The last major property of a chaotic system is topological mixing. You can
think of mixing as being, in some sense, the opposite of the dense periodic
orbits property. Intuitively, the dense orbits tell you that things that are
arbitrarily close together for arbitrarily long periods of time can have
vastly different behaviors. Mixing means that things that are arbitrarily far
apart will eventually wind up looking nearly the same - if only for a little
while.
Let's start with a formal definition.
As you can guess from the name, topological mixing is a property defined
using topology. In topology, we generally define things in terms of open sets
and neighborhoods. I don't want to go too deep into detail - but an
open set captures the notion of a collection of points with a well-defined boundary
that is not part of the set. So, for example, in a simple 2-dimensional
euclidean space, the contents of a circle are one kind of open set; the boundary is
the circle itself.
Now, imagine that you've got a dynamical system whose phase space is
defined as a topological space. The system is defined by a recurrence
relation: sn+1 = f(sn). Now, suppose that in this
dynamical system, we can expand the state function so that it works as a
continous map over sets. So if we have an open set of points A, then we can
talk about the set of points that that open set will be mapped to by f. Speaking
informally, we can say that if B=f(A), B is the space of points that could be mapped
to by points in A.
The phase space is topologically mixing if, for any two open spaces A
and B, there is some integer N such that fN(A) ∩ B &neq; 0. That is, no matter where you start,
no matter how far away you are from some other point, eventually,
you'll wind up arbitrarily close to that other point. (Note: I originally left out the quantification of N.)
Now, let's put that together with the other basic properties of
a chaotic system. In informal terms, what it means is:
Exactly where you start has a huge impact on where you'll end up.
No matter how close together two points are, no matter how long their
trajectories are close together, at any time, they can
suddenly go in completely different directions.
No matter how far apart two points are, no matter how long
their trajectories stay far apart, eventually, they'll
wind up in almost the same place.
All of this is a fancy and complicated way of saying that in a chaotic
system, you never know what the heck is going to happen. No matter how long
the system's behavior appears to be perfectly stable and predictable, there's
absolutely no guarantee that the behavior is actually in a periodic orbit. It
could, at any time, diverge into something totally unpredictable.
Anyway - I've spent more than enough time on the definition; I think I've
pretty well driven this into the ground. But I hope that in doing so, I've
gotten across the degree of unpredictability of a chaotic system. There's a
reason that chaotic systems are considered to be a nightmare for numerical
analysis of dynamical systems. It means that the most miniscule errors
in any aspect of anything will produce drastic divergence.
So when you build a model of a chaotic system, you know that it's going to
break down. No matter how careful you are, even if you had impossibly perfect measurements,
just the nature of numerical computation - the limited precision and roundoff
errors of numerical representations - mean that your model is going to break.
From here, I'm going to move from defining things to analyzing things. Chaotic
systems are a nightmare for modeling. But there are ways of recognizing when
a systems behavior is going to become chaotic. What I'm going to do next is look
at how we can describe and analyze systems in order to recognize and predict
when they'll become chaotic.
So, remember back in December, I wrote a post about a Cantor crank
who had a Knol page supposedly refuting Cantor's diagonalization?
This week, I foolishly let myself get drawn into an extended conversation
with him in comments. Since it's a comment thread on an old post that had been inactive for close to two months before this started, I assume most people haven't followed it. In
an attempt to salvage something from the time I wasted with him, I'm going to
share the discussion with you in this new post. It's entertaining, in a pathetic sort of way; and it's enlightening, in that it's one of the most perfect demonstrations of the behavior of a crank that I've yet encountered. Enjoy!
I'm going to edit for formatting purposes, and I'll interject a few
comments, but the text of the messages is absolutely untouched - which you can
verify, if you want, by checking the comment thread on the original post. The
actual discussion starts with this comment, although there's
a bit of content-free back and forth in the dozen or so comments before that.
During his life, he suffered from dreadful depression. He was mocked by
his mathematical colleagues, who didn't understand his work. And after his
death, he's become the number one target of mathematical crackpots.
As I've mentioned before, I get a lot of messages either from or
about Cantor cranks. I could easily fill this blog with nothing but
Cantor-crankery. (In fact, I just created a new category for Cantor-crankery.) I generally try to ignore it, except for that rare once-in-a-while that there's something novel.
A few days ago, via Twitter, a reader sent me a link to a new monstrosity
that was posted to arxiv, called Cantor vs Cantor. It's novel and amusing. Still wrong,
of course, but wrong in an amusingly silly way. This one, at least, doesn't quite
fall into the usual trap of ignoring Cantor while supposedly refuting him.
You see, 99 times out of 100, Cantor cranks claim to have
some construction that generates a perfect one-to-one mapping between the
natural numbers and the reals, and that therefore, Cantor must have been wrong.
But they never address Cantors proof. Cantors proof shows how, given any
purported mapping from the natural numbers to the real, you can construct at example
of a real number which isn't in the map. By ignoring that, the cranks' arguments
fail: Cantor's method still generates a counterexample to their mappings. You
can't defeat Cantor's proof without actually addressing it.
Of course, note that I said that he didn't quite fall for the
usual trap. Once you decompose his argument, it does end up with the same problem. But he at least tries to address it.
It's been quite a while since my last chaos theory post. I've
been caught up in other things, and I've needed to do some studying. Based
on a recommendation from a commenter, I've gotten another book on Chaos
theory, and it's frankly vastly better than the two I was using before.
Anyway, I want to first return to dense periodic orbits in chaotic
systems, which is what I discussed in the previous chaos theory
post. There's a glaring hole in that post. I didn't so much get it
wrong as I did miss the fundamental point.
If you recall, the basic definition of a chaotic system is
a dynamic system with a specific set of properties:
Sensitivity to initial conditions,
Dense periodic orbits, and
topological mixing
The property that we want to focus on right now is the
dense periodic orbits.
In the Haskell stuff, I was planning on moving on to some monad-related
stuff. But I had a reader write in, and ask me to write another
post on data structures, focusing on a structured called a
zipper.
A zipper is a remarkably clever idea. It's not really a single data
structure, but rather a way of building data structures in functional
languages. The first mention of the structure seems to be a paper
by Gerard Huet in 1997, but as he says in the paper, it's likely that this was
used before his paper in functional code --- but no one thought to formalize it
and write it up. (In the original version of this post, I said the name of the guy who first wrote about zippers was "Carl Huet". I have absolutely no idea where that came from - I literally had his paper on my lap as I wrote this post, and I still managed to screwed up his name. My apologies!)
It also happens that zippers are one of the rare cases of data structures
where I think it's not necessarily clearer to show code. The concept of
a zipper is very simple and elegant - but when you see a zippered tree
written out as a sequence of type constructors, it's confusing, rather
than clarifying.
A lot of people have been sending me links to a numerology article,
in which yet another numerological idiot claims to have identified the
date of the end of the world. This time, the idiot claims that it's going to
happen on May 21, 2011.
I've written a lot about numerology-related stuff before. What makes this
example particularly egregious and worth writing about is that it's not just
an article on some bozo's internet website: this is an article from the
San
Francisco Chronicle, which treats a pile of numerological bullshit as if it's
completely respectable and credible.
As I've said before: the thing about numerology is that there are so many
ways of combining numbers together that if you're willing to spend enough
time searching, you can find some way of producing any result that you want. This
is pretty much a classic example of that.
As you've surely heard by now, on christmas day, some idiot attempted to
blow up an airplane by stuffing his underwear full of explosives and then
lighting his crotch on fire. There's been a ton of coverage of this - most of
which takes the form of people running around wetting their pants in terror.
One thing which I've noticed, though, is that one aspect of this whole mess
ties in to one of my personal obsessions: scale. We humans are really,
really lousy at dealing with big numbers. We just absolutely
have a piss-poor ability to really comprehend numbers, or to take what we
know, and put it together in a quantitative way.
One thing that continually amazes me is the amount of email I get from
readers of this blog asking for career advice. I usually try to just politely
decline; I don't think I'm particularly qualified to give personal
advice to people that I don't know personally.
But one thing that I have done before is shared a bit about my own
experience, and what I've learned about the different career paths that you
can follow as a computer science researher. About six months after I started
this blog, I wrote a post about working in academia versus working in
industry. I've been meaning to update it, because I've learned
a bit more in the last few years. When I wrote the first version, I
was a research staff member at IBM's T. J. Watson research center. Since
then, I left IBM, and I've been an engineer at Google for 2 1/2 years.
Having spent a couple of years as a real full-time developer has
been a seriously educational (and humbling) experience. If you'd like
to look at the original to see how my thinking has changed, you can find it
here.
At least as a computer scientist, there are basically three kinds of work
you can do that take advantage of a strong academic background like a PhD. You
can go into academia and do research; you can go into industry and do
research; or you can go into industry and do development. If you do
the last, you'll likely be doing what's sometimes called advanced
development, which is building a system where you've got a specific
goal, where you need to produce something real - but it's out on the edge of
what people really know how to do. You're not really doing research, but
you're not doing run-of-the-mill programming either: you're doing full-scale
development of systems that require exploration and experimentation.
I'm going to talk about what the differences are between
academic research, industrial research, and advanced development in
terms of the basic tradeoffs. As I see it, there really five fundamental
areas where the three career paths differ:
Freedom: In academia, you've got a lot of freedom to do
what you want, to set your agenda. In industrial research, you've
still got a lot of freedom, but you're much more constrained: you
actually need to answer to the company for what you do. And in AD,
you're even more constrained: you're expected to produce a particular
product. You generally have a decent amount of freedom to choose
a product to work on, but once you've done that, you're pretty much
tied down.
Funding: In academia, you frequently need to devote huge amounts
of your time to getting funding for your work. In industrial research,
there's still a serious amount of work involved in getting and
maintaining your funding, but it's not the same order of magnitude
as in academia. And in AD, you don't really need to worry about funding
at all.
Time and Scale: Academic projects frequently have to be limited
in scale - you've got finite resources, but you can plan out
a research agenda years in advance; in industrial
work (whether research or AD), you've got access to resources that
an academic can only dream of, but you need to produce results
now - forget about planning what you'll be doing five years
from now.
Results: What you produce in the end is very different
depending on which path you're on. In academic research, you've got
three real goals: get money, publish papers, and graduate students.
In industry, you're expected to produce something of value to
the company - whether that's a product, patents, reputation, depends
on your circumstances - but you need to convince the company that
you're worth what they're paying to have you. And in AD, you're
creating a product. You can publish papers along the way, and that's
great, but if you don't have a valuable product at the end, no number
of papers is going to convince anyone that your project wasn't a failure.
Impact: what kind of affect your work will have on
the world/people/computers/software if it's successful.
Naftule's Dream, "Speed Klez": Naftule's Dream is a
brilliant progressive klezmer band. I happen to love klezmer,
but I think that anyone into jazzy prog rock would also enjoy
them. They're terrific.
Oregon, "Celeste": Oregon is a band that I can't make
up my mind about. They're a jazz trio, with most melodies played by
a wonderful oboist. They tend to really push the boundaries -
playing with unusual tonalities, really pushing the edge of
the envelope with their improvisation. It's quite impressive. And yet,
they frequently leave me feeling cold, like there's nothing under
the technique.
The Flower Kings, "The rainmaker": Ok, you've heard me
babble about the Flower Kings before. They're the best prog band in
the world today, and quite possibly the best ever. They're wonderful,
and I've yet to hear anything by them that I didn't absolutely love. Go
buy their recordings.
Parallel or 90 degrees, "Jitters": Po90 has a new album! Po90
is Andy Tillison's original band. Tillison is the co-founder, with Roine
Stolte from the Flower Kings, of The Tangent, another wonderful band.
Po90 has been mostly inactive for quite a while - but they just came
back with a new album, and it's absolutely terrific. It's interesting
how different it is from the Tangent - Tillison is the primary composer
for both, but they manage to have very different sounds. Highly
recommended.
Do Make Say Think, "In Mind": fantastic post-rock. DMSY is one
of the best at what they do. If you like Godspeed or Mt. Zion, you should
enjoy DMST.
Isis, "False Light": More fantastic post-rock, but from a very
different style. Where DMST is post-alternative, Isis is sort of
post-metal. The vocals take a bit of getting used to, but the overall
quality of the music makes it worth the effort.
The Clogs, "Tides of Washington Bridge": Still more fantastic
post-rock, from still another style. As you can tell, I'm a very big
post-rock fan. Part of what I love about it is the breadth of the
genre - it ranges from almost classical like the Clogs, to almost
thrash, like Isis - and yet, it also manages to have a common form
that makes it post-rock. The Clogs are one of my two favorites from
the classical side of the genre. (The other being "Rachel's".)
Red Sparrowes, "Buildings Began to Stretch Wide Across the Sky":
iTunes seems to be in a post-rock mood. Red Sparrowes are another
terrific group, from the same stylistic family as DMST.
Bach, "Wiewohl Mein Herz in Traenen Schwimmt", from the St. Matthew Passion:
In my opinion, Bach is quite simply the finest composer who ever lived.
And the St. Matthew Passion is probably my favorite of his compositions.
It's a work of sheer musical perfection. Music just doesn't get
any better than this. If you can listen to this and not be moved,
then you have no heart.
Thinking Plague, "Consolamentum": Every time Thinking Plague
comes up in a FRT, I manage to get something about them wrong. Their
guitarist either has a Google alert set up, or he reads my blog, because
he shows up and patiently corrects my errors. I think of
Thinking Plague as a very unusual post-rock group; lot's of people try
to categorize them differently, because exactly what they are is a bit
hard to pin down. They've got a very unique style that really isn't
much like anything else I've ever heard. They work with odd tonalities,
sometimes verging on atonal; they've got vocals, but the voice isn't
a lead, it's treated as just another instrument in the mix. It's not
the easiest thing to listen to - but if you like interesting,
complex, beautiful music that doesn't stick with conventional
tonality, then these guys are amazing. I found a couple of youtube clips to
include below the fold to give you a taste.
An alert reader pointed me at a recent post over at Uncommon Descent by a guy who calls
himself "niwrad", which argues (among other things) that life is
non-computable. In fact, it basically tries to use computability
as the basis of Yet Another Sloppy ID Argument (TM).
As you might expect, it's garbage. But it's garbage that's right
up my alley!
It's not an easy post to summarize, because frankly, it's
pretty incoherent. As you'll see when we starting looking
at the sections, niwrad contradicts himself freely, without seeming
to even notice it, much less realize that it's actually a problem
when your argument is self-contradictory!
To make sense out of it, the easiest thing to do is to put it into the
context of the basic ID arguments. Bill Dembski created a concept called
"specified complexity" or "complex specified information". I'll get to the
definition of that in a moment; but the point of CSI is that according to
IDists, only an intelligent agent can create CSI. If a mechanical process
appears to create CSI, that's because the CSI was actually created by an
intelligent agent, and embedded in the mechanical process. What our new friend
niwrad does is create a variant of that: instead of just saying "nothing but
an intelligent agent can create CSI", he says "CSI is uncomputable, therefore
nothing but an intelligent agent can create it" - that it, he's just injecting
computability into the argument in a totally arbitrary way.
