Shelley started it, then PZ joined in. Who am I to stop it?
GM/BM in the Card Catalog
Leave a reply
Programs as Poetry: Fishy Programming in Homespring
I’m hitting on something deeply twisted this week. It’s called homespring. Homespring is interesting for two reasons. First, it’s got a sort of reverse flavor to it: it consists of active agents in a passive structure. So, for example, you can’t do anything like control flow – that’s a dynamic change in the control flow of the program; in Homespring, you need to trick the agents into doing something using the static, unchanging structure of the program. And second, it challenges you to write your program in the form of a poem! And the icing on the cake? The agents are salmon,
and the passive structure is a network of streams.
Another Example Sheaf: Vector Fields on Manifolds
There’s another classic example of sheaves; this one is restricted to manifolds, rather than general topological spaces. But it provides the key to why we can do calculus on a manifold. For any manifold, there is a sheaf of vector fields over the manifold.
Probabilistic Complexity
As I’ve mentioned in the past, complexity theory isn’t really one of my favorite topics. As a professional computer scientist, knowing and loving complexity up to the level of NP-completeness
is practically a requirement. But once you start to get beyond P and NP, there are thousands of complexity classes that have been proposed for one reason or another, and really understanding all of them can get remarkably difficult, and what’s worse, can feel like an utterly pointless exercise,
particularly if the writer/teacher you’re learning from isn’t very good.
I’m not going to write a long series of posts on the more esoteric complexity classes. But there
are a few that are interesting, and might even have some relevance to actual practical problems in
selecting algorithms for a software system.
Basic Complexity Classes: P and NP
Now that we’ve gone through a very basic introduction to computational complexity, we’re ready
to take a high-level glimpse at some of the more interesting things that arise from it. The one
that you’ll hear about most often is “P vs NP”, which is what I’m going to write about today.
Basic Computational Complexity
In the comments thread of the post on Turing Equivalent vs Turing Complete, there’ve been a flurry of questions and comments about some stuff involving computational complexity. So I thought it would be interesting to write a couple of posts about computational complexity. I’m not going to get into a lot of detail, because I would need to dig out some books that I really don’t want to read again :-). But I can do the basics without them. It’ll take a few posts to get through this.
Friday Random Ten, Jan 5
As an experiment, I decided to try making a iMix of the items in my FRT that are available via iTunes. Please let me know if you like this; it’s a bit of extra work for me which I don’t mind doing, as long as people use it… but if no one wants it, then I’d rather not spend the time setting it up.
- Dirty Three, “I offered it up to the stars & the Night Sky”. As usual from my
random lists, it’s a post-rock ensemble. Dirty Three are classical leaning; not quite so much as
the Clogs, but still very much on the classical side. They tend to be slow and mellow, with
a gradually building intensity. Great stuff. - Hamster Theatre, “Oye Comatose”. Wierd, but cool, from a “Thinking Plague” spinoff band. (Incidentally, I received an email this week from the TP guitarist letting me know that I was wrong that he was a
GuitarCraft graduate. I’d heard this from the store I bought the CD at, and his playing sounds very crafty, but apparently the similarity in sound is just a coincidence that was turned into a rumour.) - Martin Hayes, “The Lark’s March/Kilfenora Jig/The Cliffs of Moher”. Beautiful traditional Irish music
played by a violin virtuoso at speeds that you could actually dance to. Martin is one of my favorite trad Irish artists. - The Fiddlers 4, “Atchafalaya Pipeline”. An old-timey folk tune from one of Darol Anger’s latest projects. Darol is brilliant as always.
- Gyorgi Ligeti, “Hamburg Concerto”. Very interesting modern classical. Definitely a piece of music with
a learning curve, but well worth the effort. Take some time to learn to understand it; it’s a wonderful piece of music. - Lunasa, “The Dingle Berries”. A rollicking fun Irish jig from a brilliant band.
- Dysrhythmia, “Appeared at First”. Very rock-oriented post rock. This was recommended to me
by a friend who’s also into post rock. I can appreciate it on a technical level, but I’ve never
really been able to enjoy listening to it; something about it just doesn’t work for me. - Godspeed You! Black Emperor: “Lift Your Skinny Fists like Antennas to Heaven…”. My favorite Godspeed track. Godspeed was introduced do me by Orac, and I’m terribly hooked. One of the very best Post-Rock ensembles around.
- Sonic Youth, “Rats”. Sonic Youth is a brilliantly strange band. This is from their most
recent album. Overall, the album is less blatantly strange than some of their past work. It’s still full of weird guitar playing and microtones, but they’re done subtly. Great stuff. - The Clogs, “My Mister Never Ending Bliss”. Post-rock from one of the best neo-classical post-rock
ensembles. This is off of “Stick Music” which is not one of their more accessible albums, but it is
my favorite.
Pathological Macros for BrainF**k
Today, I have something really fun and twisted for you. It’s my favorite variation on
BrainF**k, called “BFM”, which is short for “BrainFunct-Macro”. It’s a doubly-Turing-equivalent language – it’s got two complete and distinct Turing equivalent computing systems in it: it’s
got regular BF on the bottom… But before BF gets going to run the program,
the program is pre-processed by a complete lambda-calculus macro expander.
Turing Equivalent vs. Turing Complete
In my discussion with Sal Cordova in this post, one point came up which I thought was interesting, and worth taking the time to flesh out as a separate post. It’s about the distinction
between a Turing equivalent computing system, and a Turing complete computation. It’s true
that in informal use, we often tend to muddy the line between these two related but distinct concepts. But in fact, they are distinct, and the difference between them can be extremely important. In some sense, it’s the difference between “capable of” and “requires”; another way of looking at it is
“sufficient” versus “necessary”.
Stupidity from our old friend Sal
Over at [Dispatches][dispatches], Ed Brayton has been shredding my old friend Sal Cordova.
Ed does a great job arguing that intelligent design is a PR campaign, and not
a field of scientific research. Ed does a fine job with the argument; you should definitely click on over to take a look. But Sal showed up in the comments to defend himself, and made
some statements that I just can’t resist mocking for their shallow stupidity and utter foolishness.
[dispatches]: http://scienceblogs.com/dispatches/2007/01/answering_cordova_on_ids_goals.php