MarkCC February 28, 2007 Basics / Computational Complexity / information theory
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.
MarkCC February 27, 2007 Basics
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.
MarkCC February 26, 2007 Bad Physics
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.
MarkCC February 24, 2007 Intelligent Design
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?”
MarkCC February 23, 2007 pathological programming
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!
MarkCC February 23, 2007 goodmath
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.
MarkCC February 21, 2007 Chatter
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…
MarkCC February 21, 2007 Uncategorized
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.
MarkCC February 20, 2007 Haskell
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…