Multiple people have written to me, after seeing yesterday’s algorithms basics post, asking me to say more about sorting algorithms. I have to say that it’s not my favorite topic – sorting is one of those old bugaboos that you can’t avoid, but which gets really dull after a while. But there is a kernel of interest to it – sorting can be used to demonstrate a lot of interesting ideas about
computational complexity.
A kind reader pointed out that I frequently mention algorithms, but that I haven’t defined them in the basics posts. To me, they’re so fundamental to the stuff I do for a living that I completely forgot that they’re an interesting idea.
It’s really pretty simple: an algorithm is description of a mechanical procedure for performing a mathematical task. But that’s actually a fairly sophisticated idea – the general concept of things that describe a procedure, and which can be discussed, described, and reasoned about as entities in their own right is something quite different from nearly anything that came before it.
Over in the thread about Engineer Borg and his wacked-out electromagnetic theory
of gravity, a commenter popped up and pointed at the web-site of someone named Tom Bearden, who supposedly has shown how to generate free “vacuum” energy using electronic and/or electromagnetic devices.
I hadn’t heard of Dr. Bearden before, and promised to take a look at his website.
So I went and took a look. And wow, I hit the jackpot! This is an absolute masterwork of crackpottery. Dr Bearden’s lunacy covers just about every conceivable topic, from conspiracy theories, to HIV denalism, to wacky physics, magical woo healing devices, post-Soviet KGB collaborations with the Japanese government to shoot down American planes and manipulate weather….
To give you a bit of flavor: he’s got a bibliography of information that allegedly supports his theories. If you take a look at it, the first thing you see is listed as “National Science Foundation letter favorably reviewing Bearden Paper”. The contents of that link consist of a scanned letter from the NSF replying to an email sent by Dr. Bearden, which consists of a basic standardized form letter inviting him to submit an actual proposal, and warning that he’d better include some proof that his perpetual motion machine really works, and an explanation of how.
PZ has already commented on this, but I thought that I’d throw in my two cents. A surgeon, Dr. Michael Egnor, posted a bunch of comments on a Time magazine blog that was criticizing ID. Dr. Egnor’s response to the criticism was to ask: “How much new information can Darwinians mechanisms generate?”
What we have here is a truly warped language.
Back in the very early days of what eventually became computer science, many of the people working in the field invented all sorts of automatons/computing formalisms. The one that I’ve always found the most confounding is the Tag machine invented by Emil Post.
The tag machine is simple to the point of triviality. The machine is a queue of characters (with one character designated as “Halt”), and a set of rules. Each rule has a different character that selects the rule, and a string of characters. Each step, the machine looks at the first character of the queue, and selects the rule that that is associated with that character. If the character is “Halt”, the machine just stops, and whatever is left on the queue is the result of the computation. Otherwise, it appends the selected rule’s string of characters to the end of the queue, and then removed a fixed number of characters from the front of the queue. The machines are called “n-Tag” machines where “n” is number of character dropped each step.
That’s it. Look at the front of the queue, use it to pick a set of characters to append, and then remove and discard the first N characters from the queue..
For any N≥2, a Post N-tag machine is Turing equivalent.
Like I said above – I’ve always found the Post Tag machine to be thoroughly confounding. I can grasp why it’s Turing equivalent, but for the life of me, I’ve never been able to figure out how to actually implement anything interesting on one. So, I figured, there are tons of esoteric/pathological language fans out there who love nothing more than the challenge of writing interesting programs for bizarre languages; I’ll write a post-tag language, and throw it to the wolves, and see what happens!
Please make sure you read to the end. A couple of late submissions didn’t get worked into the main text, and a complete list of articles is included at the end.
Oy. So I find myself sitting in my disgustingly messy office. And I’ve got a problem. The Math Carnival is coming to town. All those geeks, and the chaos that they always cause. Oy.
Today, the ACM announced the winner of the Turing award. For those who don’t know, the Turing award is the greatest award in computer science – the CS equivalent of the Nobel prize, or the Fields medal.
The winner: Fran Allen. The first woman ever to win the Turing award. And the first Turing award winner that I’ve personally known. Fran deserves it, and I’m absolutely overjoyed to see her getting the recognition she deserves. Among her many accomplishments, Fran helped design Fortran and create the worlds first optimizing compiler.
One of my fondest memories of work is from 8 years ago. My advisor, Lori Pollock, was up for tenure. Fran was picked as one of the outside reviewers for her tenure case. So in the course of doing the review, she read the papers that Lori and I wrote together – and liked them. The next time she was in my building, she came to my office to introduce herself and talk to me about the papers I’d written. I was absolutely stunned – Fran Allen came looking for me! to talk to me!
Since then, I’ve learned that that’s just the kind of person she is. Fran is a brilliant woman, one of the smartest people I’ve had to opportunity to meet: a person who has done amazing things in her career. And she’s also one of the nicest people you could ever hope to meet. She’s approachable and friendly, and has searched out many junior researchers to give them a bit of encouragement. She’s been a mentor to more people that I could hope to count. She’s just a thoroughly amazing person.
I can’t even begin to say how happy I am for her. She’s earned the greatest award that exists for computer science, and I’m thrilled to see that the ACM recognized that. And knowing Fran, I’m particularly happy that she’s the first woman recipient of the award, because she’s worked so hard in her career to help women overcome the biases of so many people in the mathematical sciences.
Congratulations, Fran!
Many of my fellow SBers have been mocking the recently unveiled Conservapedia. Conservapedia claims to be a reaction to the liberal bias of Wikipedia. Ed, PZ, Afarensis, Tim, John, and Orac have all piled on already. But why should they get to have all the fun?
Conservapedia has an extensive list of what they claim to be examples of the liberal bias of Wikipedia. My SciBlings have already covered most of the nonsense to be found within, but one point is clearly mine to mock: grievance number 16:
Wikipedia has many entries on mathematical concepts, but lacks any entry on the basic concept of an elementary proof. Elementary proofs require a rigor lacking in many mathematical claims promoted on Wikipedia.
So, after our last installment, describing the theory of monads, and the previous posts, which focused on representing things like state and I/O, I thought it was worth taking a moment to look at a different kind of thing that can be done with monads. We so often think of them as being state wrappers; and yet, that’s only really a part of what we can get from them. Monads are ways of tying together almost anything that involves sequences.
So as many other folks have been pointing out, the Koufax awards have come out with their “Best Expert Blog” nominations, and I’m incredibly pleased to say that GM/BM was nominated!
In case you’re not familiar, the Koufaxes are one of the really serious, prestigious web-awards, aimed primarily at the left-leaning blogosphere.
I realize that my chances of actually winning are pretty damned slim; on the other hand, since PZ is disqualified because he won last year, that means that the rest of us have a chance. Voting isn’t open yet, but when it is, I’ll mention it here. I would really like to make a good showing. The BlogAwards, where GM/BM came in fourth are a very sloppily run silly award; the Koufaxes mean something.
Thanks to whoever nominated me!