Monthly Archives: January 2007

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.

  1. 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.
  2. 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.)
  3. 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.
  4. The Fiddlers 4, “Atchafalaya Pipeline”. An old-timey folk tune from one of Darol Anger’s latest projects. Darol is brilliant as always.
  5. 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.
  6. Lunasa, “The Dingle Berries”. A rollicking fun Irish jig from a brilliant band.
  7. 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.

  8. 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.
  9. 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.
  10. 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.

Continue reading

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”.

Continue reading

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

Continue reading

Examples of Sheaves

Since the posts of sheaves have been more than a bit confusing, I’m going to take
the time to go through a couple of examples of real sheaves that are used in
algebraic topology and related fields. Todays example will be the most canonical one:
a sheaf of continuous functions over a topological space. This can be done for *any* topological space, because a topological space *must* be continuous and gluable with
other topological spaces.

Continue reading

Law vs. Thuggery: The Execution of Saddam

The big news over the last couple of days has been the execution of Saddam Hussein. I
want to put in my own two cents about it. It’s not math, but it does at least involve a bit of logic.
I wish I could remember who first said this, but I really don’t know. But the important thing,
in a moral sense, about the whole mess with Saddam is that he was a thug. A vicious,
bloodthirsty, sadistic, evil thug who believed that *power* justified itself. *He* was the
strongest thug in Iraq; therefore, according to his own worldview, he got to do whatever he
wanted until someone stronger came along. Rape, torture, murder were all perfectly acceptable
to him – he had the power to do it, therefore he was *allowed* to do it.
We, Americans, claim to not believe in that calculus of power. We claim to believe in
the idea of *law*: a set of fundamental rules that transcend the individual humans who are in positions of power, that limit them and their actions. No matter who you are, no matter how strong you are, no matter how many guns or bombs or soldiers you have, there are some things
that you simple *are not* allowed to do.
And that’s where the problem with the execution of Saddam comes in.
Did he get what any objective observer would call a fair trial? No. The justification
we keep hearing is *”we know he was guilty”*. But that’s not the point: if we really believe in the rule of law, then *even if the accused is obviously, undeniably, unquestionably guilty*, we have to give them a full and fair trial, with the right to hear the evidence against them, confront their accusers, and present their own defense. Not because they *deserve* it – but because **we** require it. The laws, the fundamental rules that
make us different from thugs like Saddam, say that we must do it; if we ignore our laws,
even in the case of an outrageously evil person like Saddam, then we *validate* the things he did, the way he acted.
After the trial is over, and a sentence is selected, the way that the sentence is carried
out is also dictated by laws. Even in the case of a death sentence, there are rules that
must be followed about how the condemned criminal is treated, and about how and when his
execution must be performed.
Under pressure from the American government, the Iraqi government executed Saddam *in violation of their laws concerning executions*. In the execution chamber, being led to his death, the guards spit at him and cursed at him. Witnesses were allowed to bring in cellphone video cameras and tape his execution, and take souvenir photos of his dead body. His execution
was illegal under the law of the land, and it was carried out with the same kind of
spectacle as the executions that he commanded when he was in charge.
Saddam himself summed it up well. On the way to his execution, he said “I am a militant and I have no fear for myself. I have spent my life in jihad and fighting aggression. Anyone who takes this route should not be afraid.” He spent his life as a thug ruling because he had the power to do it. Now we came along, and we were stronger than him. So by his own standards, his own rules, he did nothing wrong. He wasn’t being *punished*; he was simply being killed
because his opponents were stronger than he was. He knew it; everyone who sees the
video of reads the news reports about his execution will know it. He was killed by
a mob of thugs.
We *could* have done something different. We could have given him a fair and open trial,
with all of the charges against him clearly set out, enumerated, and presented with evidence. We could have allowed him to try to defend himself and justify his actions. We could have seen a genuine, fair conviction of him on the basis of public, open evidence. If (as one would expect), the fair trial ended with the sentence of death, we could have executed him in accordance with the law, with the dignity that he denied to his victims, but which is *required* by law.
We could have shown that we were different from him. But we didn’t. In the end, we and the Iraqi government we created acted as a gang of thugs. We allowed Saddam Hussein to die secure in the knowledge that his view of power was correct, and that he was justified in doing
all of the evil things that he did in his life. We *betrayed* everything we claim to stand for, everything we claim to believe, and everything we claimed that this war was meant to bring to the people of Iraq.
It’s a crime. Literally.

Balanced Binary Trees in Haskell

unbalanced-trees.jpg

So, we’ve built up some pretty nifty binary trees – we can use the binary tree both as the
basis of an implementation of a set, or as an implementation of a dictionary. But our
implementation has had one major problem: it’s got absolutely no way to maintain balance. What
that means is that depending on the order in which things are inserted to the tree, we might
have excellent performance, or we might be no better than a linear list. For example, look at
these trees. As you can see, a tree with the same values can wind up quite different. In a good insert order, you can wind up with a nicely balanced tree: the minimum distance from root to leaf is 3; the maximum is 4. On the other hand, take the same values, and insert them in a different order and you
get a rotten tree; the minimum distance from root to leaf is 1, and the maximum is 7. So depending on
luck, you can get a tree that gives you good performance, or one that ends up giving you no better than a plain old list.

Today we’re going to look at fixing that problem. That’s really more of a lesson in data
structures than it is in Haskell, but we’ll need to write more complicated and interesting
data structure manipulation code than we have so far, and it’ll be a lollapalooza of pattern
matching. What we’re going to do is turn our implementation into a red-black tree.

Continue reading