Good Math/Bad Math

Reminder: GM/DM doesn't live here anymore

2006-06-15T14:26:00.000-04:00

Just a reminder for folks who haven't updated their links yet:

Good Math, Bad Math no longer lives here at blogger. It's now part of the ScienceBlogs coterie, and can be found here.

There've been a lot of new posts over at SB since the move:
- Category theory.
- More bad gematria gibberish.
- More debunking of creationists
- More programming language discussions

Category Theory at GM/BM's new home

2006-06-07T10:06:00.000-04:00

The first post in my new series on category theory is up at the new home of GM/BM.

New GoodMath post at scienceblogs: Election Fraud?

2006-06-06T13:27:00.000-04:00

I've gotten an absolutely unprecedented number of requests to write about RFK Jr's Rolling Stone article about the 2004 election. I've written about it over at GM/BM/s new home at scienceblogs.

More AiG lying with statistics: John Woodmorappe and Noah's Ark

2006-06-05T10:19:00.000-04:00

Today's sample of bad math is something I talked about way back in my talk.origin days in usenet; and which has also been discussed by lots of other people. I thought it was too old, too well covered to be worth taking time and space here, but I keep having people forward it to me, suggesting I post something on it here. So who am I to stand in the way of the desires of the readers of this blog?

Back in 1996, a guy publishing under the pseudonym of "John Woodmorappe" wrote a book called "Noah's Ark: A Feasibility Study." AIG has an article discussing the basic ideas of the book here, and it is this article that I'll be using as the focus of my post.

Woodmorappe's text purports to be a details study of whether or not it was technically feasible for the biblical story of the ark to be true. He tries to demonstrate the possibility of truth by purportedly showing how all of the animals could fit on the ark, and proposing mechanisms by which they could be fed, wastes could be disposed of, etc.

The AiG article focuses on that first issue: is it possible that the ark, as described in the bible, have enough room to fit all of the animals? They admit that the answer to this comes down to two questions:

How many animals needed to be on the ark?
How much space was needed for each animal?

They play a few games to try to reduce the number of animals that they need to make space for, ending up with 16000 individual animals. The reasoning to get that number of pretty questionable, but it's not worth quibbling over, because of what comes next.

Woodmorappe wants to figure out how much space is needed by 16000 animals. How does he do that? Easy. He figures out an average amount of space needed by each animal, and multiplies it by the number of animals. Doesn't sound bad as a way of making an estimate, right?

Except... How does he figure out how much space is needed by each animal?

He figures out the median size of the animals in the ark; and determines that the median-sized animal would need a space of .5 by .5 by .3 meters - that is less than 1/10th of a cubic meter per animal. Multiply that by the number of animals, and you come up with 1200 cubic meters. Not terribly much space at all - which would mean that there would be plenty of room for food for the animals.

So what's wrong?

There are two different figures in statistics that can be used as an 'average' value, the mean, and the median. The mean is what we normally mean by average: take all of the values, add them up, and divide by the number of values. The median is a way of selecting a "typical" individual to represent the average: take all of the values, lay them out in order, and pick the value in the middle.

Woodmorappe uses the median. The median represents a "typical" individual; it's the value in the center. The nice thing about the median is that it gives you an idea of what a typical individual is like, without having it shifted by outliers in your data. But it's useless for trying to extrapolate to things about the population - because the outliers are part of the population; you can't eliminate them from your calculations about the population.

For example, I've had 7 pets in my lifetime. Their weights were 18lbs (a big fat cat), 15 lbs (a tiny poodle), 20 lbs (a smallish mutt), 20 lbs (another mutt), 10 lbs (a normal sized cat), 18 lbs (another poodle), and 78lbs (a golden retriever).

The median size of my pets? Well, in order they were (10, 15, 18, 18, 20, 20, 78); so the median was 18 lbs.

The mean size of my pets? (10+15+18+18+20+20+78)/7 = 25.5lbs.

If I use the median to reason about the group of pets, I'd conclude that all of my pets together would weight 126 lbs. But that's not true: they would weigh 179lbs! I'd be off by 54 lbs! Because by using the median instead of the mean, I've ignored the outlier.

That's exactly what Woodmorappe does. He concludes that the median animal is the size of a rat, and a rat, 1/10th of a cubic meter is more than enough space. But he's very deliberately eliminated the effects of elephants, dinosaurs (which Woodmorappe claims were on the ark!), horses, cows, antelope. They're all outliers in his data. By using the median, he's been able to reduce the space requirement by a huge factor - by at least something between one and two orders of magnitude!

This isn't sloppiness. No one would reasonably even compute a median size for something like this. This is a deliberate attempt to lie with numbers: by taking advantage of the fact that most of his readers aren't going to notice that he uses the median rather than the mean for an average (or in fact by relying on the fact that most don't even know the difference), he's lying to them to help them reach the conclusion that they really want.

Quite simply, Woodmorappe deliberately makes a mathematical error, and then uses that error to lie.

Site changes complete

2006-06-03T16:00:00.000-04:00

Sorry for the burst of index posts for those of you reading via RSS aggregators. The site changes are done now; there's a menu in the sidebar linking to the topic indices, and I've added a couple of links to the (still too small) blogroll. I might still make a polish change or two to the site, but nothing that should trigger any new RSS updates. Please let me know if you happen to notice any problems with the indices or sidebar.

Information Theory (index)

2006-06-03T15:33:00.000-04:00

Group Theory (index)

2006-06-03T15:32:00.000-04:00

Automata Theory (index)

2006-06-03T15:31:00.001-04:00

Rebutting Creationism (index)

2006-06-03T15:31:00.000-04:00

Logic (index)

2006-06-03T15:30:00.000-04:00

Rebutting PEAR (index)

2006-06-03T15:29:00.000-04:00

Lamda Calculus (Index)

2006-06-03T15:23:00.000-04:00

Reader poll about topics; and some site maintenance stuff

2006-06-03T12:31:00.000-04:00

I'm going to be doing a bit of work on the site this weekend to try to create a couple of indices for some of the series of posts that I've written. (After three months, I'm starting to realize that the site could use a bit or organization :-) ) So there's going to be a flurry of activity around here that's not terribly interesting, but it will make things easier to find as a result.

I'm also trying to decide what subjects I should write about next. I've got a few possibilities in mind, and I thought I'd ask you folks what you're interested in. Let me know which of the following interest you most; or feel free to "write in" your own suggestions.

Topology. I'm far from an expert on the subject, but it's an interesting one, and I'm willing to study up and write about it, so long as people are patient with me when I inevitably make mistakes.
More group theory. I've got enough time to be able to continue the series of posts on group theory.
Modal logics. In the whole lambda calculus thing, I mentioned the idea of modal logics. There are some really fascinating modal logics (I particularly like temporal and linear logics) that allow you to reason in different ways.
Graph theory. Graph theory is a fascinating area of discrete math that think is a lot of fun.
Category theory. Category theory is similar to group theory; it's one of those fields based on abstracting something down to its bare essentials. In cat theory, it's the concept of a function as a mapping from one thing to another.

Astoundingly Stupid Math: the Bullshit of Homeland Security Funds Allocation

2006-06-02T13:33:00.000-04:00

Hat tip to Making Light for the following.

As you must have heard, this week, the US Department of Homeland Security released information about the allocation of anti-terrorism funds to US cities. New York City, which is about 15 miles south of where I'm sitting right now, had its funding cut by 40%. The mayor of NYC pointed out the stupidity of this, saying "Whenever we catch someone involved in a terrorist plot, they've got a map of NYC in their pocket".

More information about the allocation has gradually been getting out. It turns out that the allocation method was remarkably simple. In their applications for funding, cities listed assets that they needed to protect. What DHS did was take the number of listed assets from all of the cities that were going to be recipients of funds, and give each city an amount of funding proportional to the number of assets they listed.

So, the Empire State building is equal to the neighborhood bank in Omaha. The stock exchange on Wall Street is equal to the memorial park in Anchorage, Alaska. Mount Sinai hospital is equal to the county hospital in the suburbs of Toledo, Ohio. The New York subway system (18.5 billion passenger-miles per year) is equal to the Minneapolis transit system (283 million passenger-miles per year). The Brooklyn Bridge is equal the George Street bridge in New Brunswick, NJ.

We know, perfectly well, how to estimate relative values and risks - the insurance company does it every day. Did our government do that? No. They ignored the established math of how to do it right, in favor of a stupid, a mind-bogglingly stupid, a deliberately stupid formula that would screw over every single actual high-risk location in the country, so that they could shove the money at people who don't need it.

Finally, Modeling Lambda Calculus: Programs are Proofs!

2006-06-02T11:31:00.000-04:00

Now that we've worked through intuitionistic logic and it's model; and we've worked from the untyped lambda calculus to the simply typed lambda calculus; we're finally ready for the model of lambda calculus. And this is where it gets really fun.

Think about the types in the simple typed language calculus. Anything which can be formed from the following grammar is a lambda calculus type:


type ::= primitive | function | ( type )
primitive ::= A | B | C | D | ...
function ::= type -> type

The catch with that grammar is that you can create type expressions which, while they are valid type definitions, you can't write a single, complete, closed expression which will actually have that type. (A closed expression is one with no free variables.) When there is an expression that has a type, we say that the expression inhabits the type; and that the type is an inhabited type. If there is no expression that can inhabit a type, we say it's uninhabitable.

So what's the difference between inhabitable type, and an uninhabitable type?

The answer comes from something called the Curry-Howard isomorphism. For a typed lambda calculus, there is a corresponding intuitionistic logic; a type expression is inhabitable if and only if the type is a theorem in the corresponding logic.

Look at the type "A -> A". Now, instead of seeing "->" as the function type constructor, try looking at it as logical implication. "A implies A" is clearly a theorem of intuitionistic logic. So the type "A -> A" is inhabitable.

Now, look at "A -> B". That's not a theorem, unless there's some other context that proves it. As a function type, that's the type of a function which, without including any context of any kind, can take a parameter of type A, and return a value of a different type B. You can't do that - there's got to be some context which provides a value of type B - and to access the context, there's got to be something to allow the function to access its context: a free variable. Same thing in the logic and the lambda calculus: you need some kind of context to establish "A->B" as a theorem (in the logic) or as an inhabitable type (in the lambda calculus).

It gets better. If there is a closed LC expression whose type is a theorem in the corresponding intuitionistic logic, then the expression that has that type is a proof of the theorem. Each beta reduction is equivalent to an inference step in the logic. The logic corresponding to the lambda calculus is it's model. In some sense, the lambda calculus and intuitionistic logic are just different reflections of the same thing.

There are two ways of demonstrating the isomorphism: there's the original way that Curry did it, using the combinator calculus; and there's something called the sequent calculus. I learned it using the combinator version, so I'll run through that quickly. Another day, probably early next week, I'll do the sequent version.

Let's recall what a model is. A model is a way of showing that every statement in the calculus is valid in some concrete universe of values - that there is a correspondence between some set of real entities and the entities in the calculus, where statements in the calculus correspond to valid statements about the real entities. So we don't actually need to do the full isomorphism; we just need to show a homomorphism from calculus to logic. (An isomorphism means you can go both ways: from calculus to logic and from logic to calculus. Homomorphism is only from calculus to logic.)

So what we need to do is explain exactly how to take any complete lambda calculus expression, and translate it into a series of valid intuitionistic logic statements. Since the intuitionistic logic itself has been proven valid, if we can translate lambda calculus to IL, then we'll have proven the validity of lambda calculus - meaning that we'll have shown that computations in the lambda calculus are valid computations, and the lambda calculus is, indeed, a fully valid, effective computing system.

How do we get from combinators (which are just a shorthand for lambda calculus without variables) to intuitionistic logic? It's actually amazingly easy.

All proofs in an intuitionistic logic come down to a series of steps, each of which is an inference using one of two fundamental axioms:

A implies B implies A
(A implies B implies C) implies ((A implies B) implies (A implies C))

Let's rewrite those using arrows, like a type: A -> B -> A; and (A -> B -> C) -> (A -> B) -> A -> C.

Do those types look familiar to you? Take a look back at the post on simple typed lambda calculus if they don't. Those are the types of the S and K combinators.

The steps to the model should be pretty obvious now. Types in a lambda calculus correspond to types of atoms in an intuitionistic logic. Functions are inference rules. Each function can be reduced to a combinator expression; and each combinator expression is an instantiation of one of the fundamental inference rules of the intuitionistic logic. The function is a constructive proof of the theorem in the corresponding logic.

Now, is that cool, or what?

(To which any normal person would respond "what". But then, I'm obviously not a normal person, I'm a math geek.)

Friday Random Ten, 6/2

2006-06-02T09:39:00.000-04:00

Yes indeed. it's friday again. Where did my week go?

Phish, "My Friend, My Friend". I actually really like certain jam bands. Phish is often quite good. This is one of my favorites of their studio tracks. (And, if you look at the cover of the album, and you draw a line through the arm of the guy on the bed, you can make a 23.5 degree angle! Phish is in on the secret!)
Deanta, "The Rocky Reels". Deanta is a wonderful traditional Irish band, which prominently features one of my favorite Irish flutists, Deirdre Havlin. Beautiful music, arranged in a wonderfully sparse way. Bouzouki, flute, fiddle, piano, and harp. Just stunning.
Porcupine Tree, "Prodigal". Pretty much what you expect from PT: somewhat odd dark chords, an unexpectedly smooth voice, kinda catchy melody. Cool stuff. Not their best, but still awfully good.
Sonic Youth, "Disappearer". Sonic Youth often do things with interesting tonalities, microtones, and strange extended jams involving playing distorted guitars with all sorts of peculiar implements. This is a perfect example of that.
King Crimson, "The Power to Believe 1: a Capella". I love the stuff that Fripp and company have been up to in the last couple of years. They've been getting even stranger with time. After the ProjeKCts work, they did this album, and it really shows the way that all that free-improv work affected them.
Miles Davis, "Deception". It's Miles, what more do you need to say?
Nightingale, "The Discharged Drummer". Nightingale is a wonderful French-Canadian acoustic folk trio, and one of the best contradance bands in the world. Beautiful little track, this one.
Pain of Salvation, "Rope Ends". Neo-progressive spin-off of the Flower Kings. Very cool band.
Broadside Electric, "With her head tucked underneath her arm". Broadside is a Philadelphia based electric folk band which plays a lot of stuff based on ballads from Childe's compilation. They also mix in traditional irish, klezmer, and progressive rock influences. The usual lineup is lead singer/guitarist/dulcimer, electric violin, chapman stick, tinwhistle/oboe, and drum. This is one of their humorous songs, about the ghost of Ann Boleyn haunting the tower of London. (Who doesn't love lyrics like " Along the draughty corridors for miles and miles she goes/She often catches cold, poor thing, it's cold there when it blows/And it's awfully awkward for the Queen to have to blow her nose/With her head tucked underneath her arm!") It's not one of their originals, but who else has recorded it with a klezmer violin solo?
Pat Donohue, "The Other End of the Mississippi River Blues". Pat is the guitarist from the Guys All-Star Shoe Band on Prairie Home Companion. He's the best finger-style guitarist that I've ever seen in person. He's also quite a goof: Pat's own description of what he does is "go out and find perfectly good songs, and then ruin them". This one is one of his originals. Silly, but fun. ("They've got magnolia trees, sweet southern breeze; I've got ice and snow, 26 degrees below".)

Improbable is not impossible, redux

2006-05-31T20:39:00.000-04:00

I actually decided to say a bit more about the concept of improbable vs. impossible after my last post.

As I've said before, the fundamental idea behind these arguments is what I call the "big numbers" principle: We (meaning human beings) are very bad at really grasping the meaning of very large numbers. It's hard to really grasp what a million is: if you counted one number a second, with no breaks of any kind, it would take you more than 11 days to count to one million. When we start getting to numbers that dwarf a million, our ability to really understand what they mean - to really grasp on a deep, intuitive level what they mean - just completely goes out the window.

What does 10^20 mean? If it takes 11 days to count to one million, then it would take roughly 11 times 10^14 days - or 3 times 10^12 (aka 3 trillion) years to count to 10^20. That just doesn't mean anything on an intuitive level. So what does 10^100 mean?

What happens when we start to look at probability? Well, it's really easy to get huge numbers in probability calculations - the kinds of numbers that we can't really grasp. And because those numbers are so meaningless to us, so utterly beyond the reach of what we really comprehend, the probabilities of astonishingly common events can seem like they're entirely beyond the realm of possibility: they must be impossible, because how could anything so easily comprehensible create numbers so incomprehensible?

Who hasn't shuffled cards? Who hasn't played a game of klondike solitaire? And yet, every time we do that, we're witnessing an event with a probability of roughly 1 in 8 times 10^67!

If something as common as shuffling a deck of cards can produce a result with odds of 1 in 10^67, then think of the probability of something uncommon: what's the probability of the particular arrangement of molecules in a particle of dust? Or the shape of a comets tail? Those are all natural, possible events - and the probability of them happening the way that they do is pretty much beyond our capacity to imagine.

When you grasp that, then you start to realize just how meaningless the big numbers argument is. No matter how improbable something is, that does not mean that it is impossible. Impossible is a probability of 0. And any probability, no matter how small, is almost certainly the probability of something that's occurring in the universe, somewhere, right now.

Repeat after me: Improbable IS NOT Impossible

2006-05-31T19:53:00.000-04:00

I got a request to respond to look at this. It's yet another one of those innumerate jackasses arguing that god must exist, because life is too unlikely otherwise.

It's the same old crap, but with one interesting twist - this guy tries to provide an argument for why anything less probable than a specific level of improbability is absolutely physically impossible. In his own words:

In a previous post, I presented a logical, factual argument for the existence of God. But one of my readers, Seanny McShawn, took issue with my syllogisms, saying that I was simply making an argument “from incredulity”.

When someone tries to win an argument based on simple probabilities, this is called an “argument from incredulity.” This is a logical fallacy. In other words, the sheer unlikeliness of a scenario does not preclude its possibility and cannot be proof against it.

But was I arguing from “incredulity”?

The answer is, pretty much, "yes".

Physicists estimate that in our universe there are 10^80 particles. Mathematicians say that the mathematical level of absolute impossibility is 1 chance in 10^50.

Not any competent mathematician.

However, the physical level of absolute impossibility is 1 chance in 10^80, and here’s why:

On the basic level, probability is defined by the ‘particle’ example: finding a specially marked particle among 500,000 particles is beating odds of 1 in 500,000. In a universe that has 10^80 individual particles, the most improbable scenario is finding a specially marked particle in the entire universe. Due to the size of our universe, it is impossible to have a more improbable set of odds than 1 chance in 10^80. Anything that is more improbable than the most improbable is by all standards absolutely impossible.

I have never seen this particle example nonsense. But nonsense is what it is. It is, in fact, astoundingly easy to demonstrate.

Ready? Are you sure? Ok. Here goes:

adfjiopwqeruoipboisdupoqwerbjksggfiuqwerup9ujdknc
blkjdbfqlijwecna34kjvldjfghqiopewufnadsmvbviuhwro
wprotiudvncmbcxbnajkhgpqrjwopeporewgjvdlkfmfkpowe
ri3nwe9mfwkdgnguipewiofkxnvcvpuiweklhhjnjwrn9fpuo
isdhpvjpndjkgnewqhtrepiuwifjoxcjvkneqotiurhwepafk
makdlgnqwejrhpqfioudshnfeiqjhweiufh

That's 286 random characters, produced by pounding my hands on my keyboard, and then deleting any punctuation characters (because I'm too lazy to figure out how many unshifted characters there are on my keyboard, so I stuck to numbers and letters.) The odds of generating that particular string are 36^286. That's quote a bit less likely than 10^80. But guess what? It's possible!

Or, just to annoy the fundies, go get yourself a deck of Tarot cards. (Hey, they're good to have. There are some damned neat poker variants that you play with a Tarot deck, not to mention some funky solitaires.) A tarot deck has 78 cards. Shuffle the deck. Lay the cards out in order. The odds of that ordering? Less than 1 in 10^115. But entirely possible.

What is the probability of a solar flare taking a specific shape? Think of the trillions of trillions of particles in a flare, and the unique shape of each one. The probability of those shapes? Quite a bit worse than 1 in 10^80.

This one in 10^80 stuff is pure nonsense. It's just another attempt to create an arbitrary threshold beyond which we can say something is impossible.

He then goes on to repeat yet another variant of the "odds of life based on the probability of a particular protein" gibberish. I've covered that plenty of times on this blog; for example, my analysis of Berlinski's version of this argument here.

So this guy concludes with:

This is not an argument from incredulity. This is an argument from facts: cold, hard facts. Since any set of odds above 1 in 10^80 is absolutely impossible, random chance could not and did not produce life.

Except that it is an argument from incredulity, utterly lacking in cold, hard facts. In fact, it's trivially refuted by cold hard facts; and it's based on one of the most pathetic attempts I've seen so far to define "impossible" in terms of probability.

Magic 23.5 update: Osborne runs away.

2006-05-31T14:29:00.000-04:00

Just thought I'd put up a quick little note here. I found that the author of the "23.5" stuff, after giving up on responding here, has set up a nice little website - sans comments - in which he defends himself from the criticisms here.

Since I went to the trouble of publically presenting his defense on the front page of this blog, and engaging in a civil discussion with him in the comments, I'm more than a little bit ticked at this. He's obviously welcome to handle things as he wants, but I find it rather cowardly of Gary to silently drop out of a public, open discussion here, and then continue it on a private site, where no one who disagrees with him is permitted to respond.

I'm not going to link to it, since he's got rather a lot of advertisements set up (you actually have to sit through an ad on the main link to the site before you're allowed to read any content), and I'd rather not send cash in his direction as a reward for this. If you really care, you can find it either through google, or through the sitemeter referrals link on the bottom of the front page of this blog.

Practical Applications of Good Math: Type Checking in Programming Languages

2006-05-31T13:46:00.000-04:00

(Since I see that there are still links pointing at this post, I'll point out here that this blog has moved to scienceblogs. This discussion was continued in a post there.)

I thought today I'd go a bit off topic, and rant a little bit about stuff that's been bugging me lately in my real work. It does, in its bizzare way, relate to the lambda calculus series I've been writing lately.

What I do professionally is research in a field called collaborative software development: how to build tools that help groups of people work together to build large systems. It's an interesting thing to do, with a huge range of things that can be done, ranging from better programming languages to better configuration management systems to better programming environments to entirely new kinds of collaborative tools. It involves practical programming, math, psychology and human factors, and a few other interesting things.

My approach to this kind of work is to view the key problem as being one of communication. Most problems in large systems are ultimately not algorithmic errors - they're errors where some key piece of information was not correctly communicated between developers. For example, one of the most common bugs in large systems occurs when the implementor of a piece of code makes assumptions about how their code is going to be called; and the developer who uses that code makes different assumptions. To be concrete; I experienced this recently on my project at work. I'm working on a bit of code, and one function I call takes a lot of parameters, each of which is an array of objects. Most of the time, you only supply a real value for one or two out of a list of 8 parameters. I assumed that for unused parameters, it made sense to pass null - that's how I would have written that method. The person who wrote it expected callers to never pass null, but to use empty arrays for unused parameters. Program compiles, deploys, and boom: exceptions out the wazoo. (There was a dynamic check for null, but because of some proxy stuff we do, it was very hard to track it down.)

This isn't a result of incompetence on anyone's part. This project has some of the finest developers that I've ever met working on it. The person who wrote that method with the awful parameter list is actually a pretty great programmer - one of the top people from one of the top groups of developers that I know of. I don't think I'm incompetent either :-). So why did the error happen?

Because a key piece of information didn't get passed between us. Between the size of our system, the number of people involved, the way the code is partitioned into components, and where the documentation lives, the information about what to do about empty parameters got lost.

What does any of this have to do with lambda calculus? Types.

That problem wouldn't have happened if we were programming in my favorite programming language, OCaml. In OCaml, to be able to pass a "null" value, I actually need to specify that in the parameter declaration (as an Option type). There's no way I can pass a null to a function that wasn't expecting one.

It's a common assertion among a lot of the elite hackers out there that "real programmers don't use strongly typed languages", or the Paul Graham line about strongly typed languages. For example, here's Paul on Java:

It's designed for large organizations. Large organizations have different aims from hackers. They want languages that are (believed to be) suitable for use by large teams of mediocre programmers-- languages with features that, like the speed limiters in U-Haul trucks, prevent fools from doing too much damage.

This attitude really bugs me. The thing is, types are meta-information about a program - and useful meta-information. And the more people you have involved in a system, the more important it becomes to have strong, formal information about parts of the system that allow automatic checks.

The elitism issue. "Yeah, I'm a super-duper programmer who doesn't make mistakes; people who don't work the way I do are just inferior." Yeah, tell that to the guys who wrote OCaml.
The cluelessness issue: "I write programs in Perl/Python/CommonLisp/... with three other guys who are all lisp wizards, and if we don't have a problem, then no one should, so that typing stuff is just nonsense to cover up for incompetence." There are problems that emerge as the size of a system and the number of people working on it increase. Three people hacking on something is very different from 30 people hacking on it, which is very different from 300 people. As the number of people involved increases, you need to do more to ensure that information gets to where it's needed.
The information loss issue. This is the one that actually bugs me the most. Programmers know what types they're using. They know what types they're passing. They know information about the parameters they're taking, and the parameters that they're passing. Good type system give them a way to write that down - and not just write it, but make it a part of the code, so that it can be tested. Writing it down as a part of the code means that the information is recorded; that it's maintained; and that it's checked. Not declaring types saves you a bit of keyboard time - but it means that there's important information in your head which you're not writing down. (I have exactly the same rant about parallelizing compilers, which is that you have to structure your code very carefully and precisely to allow the compiler to figure out the information that you knew before you wrote the code; but instead of letting you write it down, you have to trick the compiler into figuring it out on its own.)

The most common response from people like Paul to rants like mine is "Strong testing, not strong typing." The idea being, type checking is really something like a very simple kind of compile time testing, which is inferior to a real, complete test suite.

Sure, strong typing in a language is no replacement for testing. But why on earth should I write tests to verify correct typing, when I can just put the type information in line in the code and have it tested automatically? Typing and type checking is one part of the process; having a typed language doesn't mean you shouldn't write tests; writing tests doesn't mean that compile-time type checking is useless. Pulling the typing information out of line into a test is, frankly, just dumb: the more you spread the information around between multiple places, the less likely it is to be maintained, or even found.

I'm a huge unit testing fan; but one of the major limitations of testing is information scattering. You're putting information about the invariants and requirements of your code in the logic of the tests - and because of the multidimensional nature of software systems, that inevitably means that some of the information is here, some there. Trying to assemble the information you need from a list of test failures can be incredibly frustrating; and those tests often don't get maintained, so things change, but the tests aren't changed to thoroughly respect the new semantics. Compile time checking can't get out of synch with the current state of the code.

Types in Lambda Calculus

2006-05-30T13:01:00.000-04:00

Now that we've got intuitionistic logic under our belts, we're ready to get back to lambda calculus: we've got the logical tools we need to define the model. Of course, nothing is ever quite that simple, is it?

What we've talked about so far is the simple untyped lambda calculus. That's how LC started; it's the first version that Church invented. But it did end up with some problems, and to get around that, a concept of types was introduced, leading to the simple typed lambda calculus, and on from there to a world of variants - SystemT, SystemF, the Lambda Cube (not related to the time cube :-)), and so one. And eventually, people realized that the untyped lambda calculus was really just a simple pathologically simple case of a typed lambda calculus - it's a typed LC with only one type.

The semantics of lambda calculus are easiest to talk about in a typed version. For now, I'll talk about the simplest typed LC, known as the simply typed lambda calculus; and how it's ultimately semantically equivalent to an intuitionistic logic. (In fact, every version of typed LC corresponds to an IL; and every beta reduction in an LC corresponds to an inference step in an IL proof; that's why we needed to sidetrack into intuitionistic logic to get here.)

The main thing that typed lambda calculus adds to the mix is a concept called base types. In a typed lambda calculus, you have some universe of atomic values which you can manipulate; those values are partitioned into simple types. Base types are usually named by single lower-case greek letters; since that's a pain on Blogger, I'll use upper-case english letters for type names. So, for example, we could have a type "N", which consists of the set of natural numbers; a type "B" which corresponds to boolean true/false values; and a type "S" which corresponds to strings.

Once we have basic types, then we can talk about the type of a function. A function maps from values of one type (the type of parameter) to values of a second type (the type of the return value). For a function that takes a parameter of type "A", and returns a value of type "B", we write its type as "A -> B". "->" is called the function type constructor; it associates to the right, so "A -> B -> C" means "A -> (B -> C)".

To apply types to the lambda calculus, we do a couple of things. First, we need a syntax update so that we can include type information in lambda terms. And second, we need to add a set of rules to show what it means for a typed program to be valid.

The syntax part is easy. We add a ":" to the notation; the colon has an expression or variable binding on its left, and a type specification on its right. It asserts that whatever is on the left side of the colon has the type specified on the right side. A few examples:

lambda x : N . x + 3. This asserts that the parameter, x, has type "N", which is the natural numbers. There is no assertion of the type of the result of the function; but since we know that "+" is a function with type "N -> N", which can infer that the result type of this function will be "N".
(lambda x . x + 3) : N -> N. This is the same as the previous, but with the type declaration moved out, so that it asserts the type for the lambda expression as a whole. This time we can infer that "x : N" because the function type is "N -> N", which means that the function parameter has type "N".
lambda x : N, y : B . if y then x * x else x. A two parameter function; the first parameter is type "N", the second type "B". We can infer the return type, which is "N". So the type of the full function is "N -> B -> N". This may seem surprising at first; but remember that lambda calculus really works in terms of single parameter functions; multi-parameter functions are a shorthand for currying. So really, this function is: lambda x : N . (lambda y : B . if y then x * x else x); the inner lambda is type "B -> N"; the outer lambda is type "N -> (B -> N)".

To talk about whether a program is valid with respect to types (aka well-typed), we need to introduce a set of rules for type inference. When the type of an expression is inferred using one of these rules, we call that a type judgements. Type inference and judgements allow us to reason about types in a lambda expression; and if any part of an expression winds up with an inconsistent type judgement, then the expression is invalid. (When Church started doing typed LC, one of the motivations was to distinguish between values representing "atoms", and values representing "predicates"; he was trying to avoid the Godel-esque paradoxes, by using types to ensure that predicates couldn't operate on predicates.)

I'm going to have to adopt a slightly unorthodox notation for type judgements; the standard notation is just too hard to render correctly with the software I'm using currently. The usual notation is something that looks like a fraction; the numerator consists of statements that we know to be true; the denominator is what we can infer from those. In the numerator, we normally have statements using a context, which is a set of type judgements that we already know; it's usually written as an uppercase greek letter. For type contexts, I'll use the names of greek letters written in uppercase letters. If a type context includes the statement that "x : A", I'll write that as "CONTEXT |- x : A". For the fraction inference notations, I'll use a two lines labelled "Given:" and "Infer:". (You can see what the normal notation looks like by visiting wikipedia's STLC page.)

Rule1: (Type Identity)


Given: nothing
Infer: x : A |- x : A

The simplest rule: if we have no other information except a declaration of the type of a variable, then we know that that variable has the type it was declared with.

Rule2: (Type Invariance)


Given: GAMMA |- x : A, x != y
Infer: (GAMMA + y : B) |- x : A

This is a statement of non-interference. If we know that "x : A", then inferring a type judgement about any other term cannot change our type judgement for "x".

Rule3: (Parameter to function inference)

 
Given: (GAMMA + x : A) |- y : B
Infer: GAMMA |- (lambda x : A . y) : A -> B

This statement allows us to infer function types: if we know the type of the parameter to a function is "A"; and we know that the type of the value returned by the function is "B", then we know that the type of the function is "A -> B".

And finally, Rule4: (Function application inference)


Given: GAMMA |- x : A -> B, Gamma |- y : A
Infer: GAMMA |- (x y) : B

If we know that a function has type "A -> B", and we apply it to a value of type "A", the result is an expression of type "B".

These four rules are it. If we can take a lambda expression, and come up with a consistent set of type judgements for every term in the expression, then the expression is well-typed. If not, then the expression is invalid.

Just for kicks, here's how we'd write types for the SKI combinators. These are incomplete types - I'm using type variables, rather than specific types. In a real program using the combinators, you could work out the necessary substitutions of concrete types for the type variables. Don't worry, I'll show you an example to clarify that.

I combinator: (lambda x . x) : A -> A
K combinator:: (lambda x : A . ((lambda y : B . x) : B -> A)): A -> B -> A
S combinator: (lambda x : A -> B-> C . (lambda y : A -> B . (lambda z : A . (xz : B -> C) (yz : B)))) : (A -> B -> C) -> (A -> B) -> C

Now, let's look at a simple lambda calculus expression: lambda x y . y x. Without any type declarations or parameters, we don't know the exact type. But we do know that "x" has some type; we'll call that "A"; and we know that "y" is a function that will be applied with "x" as a parameter, so it's got parameter type A, but its result type is unknown. So using type variables, we can say "x : A, y : A -> B". We can figure out what "A" and "B" are by looking at a complete expression. So, let's work out the typing of it with x="3", and y="

lambda a : N. a*a". We'll assume that our type context already includes "*" as a function of type "N -> N -> N".

(lambda x y . y x) 3 (lambda a : N . a * a)
Since 3 is a literal integer, we know its type: 3 : N.
By rule 4, we can infer that the type of the expression "a * a" where "a : N" is "N"; (* : N -> N -> N; it's applied to an N and an N) and therefore, by rule 3 the lambda expression has type "N -> N". So with type labelling, our expression is now: (lambda x y . y x) (3 : N) (lambda a : N . (a * a):N) : N -> N
So - now, we know that the parameter "x" of the first lambda must be "N"; and "y" must be "N -> N"; so by rule 4, we know that the type of the application expression "y x" must be "N"; and then by rule 3, the lambda has type: N -> (N -> N) -> N.
So, for this one, both A and B end up being "N".

So, now we have a simply typed lambda calculus. The reason that it's simply typed is because the type treatment here is minimal: the only way of building new types is through the unavoidable "->" constructor. Other typed lambda calculi include the ability to define parametric types, which are types expressed as functions ranging over types.

PEAR yet again: the theory behind paranormal gibberish

2006-05-29T19:49:00.000-04:00

I've been looking at PEAR again. I know it may seem sort of like beating a dead horse, but PEAR is, I think, something special in its way: it's a group of people who pretend to use science and mathematics in order to support all sorts of altie-woo gibberish. This makes them, to me, particularly important targets for skeptics: if they were legit, and they were getting the kinds of results that they present, they'd be demonstrating something fascinating and important. But they're not: they're trying to use the appearance of science to undermine science. And they're incredibly popular among various kinds of crackpottery: what led me back to them this time is the fact that I found them cited as a supporting reference in numerous places:

Two different "UFOlogy" websites;
Eric Julien's dream-prophecy of a disastrous comet impact on earth (which was supposed to have happened last thursday);
Three different websites where psychics take money in exchange for psychic predictions or psychic healing;
Two homeopathy information sites;
The house of thoth, a general clearinghouse site for everything wacky.

Anyway, while looking at the stuff that all of these wacko sites cited from PEAR, I came across some PEAR work which isn't just a rehash of the random number generator nonsense, but instead an attempt to define, in mathematical terms, what "paranormal" events are, and what they mean.

It's quite different from their other junk; and it's a really great example of one of the common ways that pseudo-scientists misuse math. The paper is called "M* : Vector Representation of the Subliminal Seed Regime of M5", and you can find it here.

The abstract gives you a pretty good idea of what's coming:

A supplement to the M^5 model of mind/matter interactions is proposed wherein the subliminal seed space that undergirds tangible reality and conscious experience is characterized by an array of complex vectors whose components embody the pre-objective and pre-subjective aspects of their interactions. Elementary algebraic arguments then predict that the degree of anomalous correlation between the emergent conscious experiences and the corresponding tangible events depends only on the alignment of these interacting vectors, i. e., on the correspondence of the ratios of their individual ‘‘hard’’ and ‘‘soft’’ coordinates. This in turn suggests a subconscious alignment strategy based on strong need, desire, or shared purpose that is consistent with empirical experience. More sophisticated versions of the model could readily be pursued, but the essence of the correlation process seems rudimentary.

So, strip out the obfuscatory babble, what does this actually say?

Umm... "babble babble complex vectors babble babble babble algebra babble babble ratios babble babble correlation babble babble." Seriously: that's a pretty good paraphrase. That entire paragraph is meaningless. It's a bunch of nonsense mixed in with a couple of pseudo-mathematical terms in order to make it sound scientific. There is no actual content to that abstract. It reads like a computer-generated paper from SCIgen.

(For contrast, here's a SCIgen-generated abstract: "The simulation of randomized algorithms has deployed model checking, and current trends suggest that the evaluation of SMPs will soon emerge. In fact, few statisticians would disagree with the refinement of Byzantine fault tolerance. We confirm that although multicast systems [16] can be made homogeneous, omniscient, and autonomous, the acclaimed low-energy algorithm for the improvement of DHCP [34] is recursively enumerable.")

Ok, so the abstract is the pits. To be honest, a lot of decent technical papers have really lousy abstracts. So let's dive in, and look at the actual body of the paper, and see if it improves at all.

They start by trying to explain just what their basic conceptual model is. According to the authors, the world is fundamentally built on consciousness; and that most events start in a a pre-conscious realm of ideas called the "seed region"; and that as they emerge from the seed region into experienced reality, they manifest in two different ways; as "events" in the material domain, and as "experiences" or "perceptions" in the mental domain. They then claim that in order for something from the "seed region" to manifest, it requires an interaction of at least two seeds.

Now, they try to start using pseudo-math to justify their gibberish. I'm going to modify the notation slightly to make it readable without using any symbols that are problematic on blogger; you can check the paper to see that I'm not changing anything but trivial notation.

Suppose we have two of these seed beasties, S_1, and S_2. Now, suppose we have a mathematical representation of them as "vectors". We'll represent that as a function, rep(S).

A "normal" event, according to them, is one where the events combine in what they call a "linear" way (scare-quotes theirs): rep(S_1) + rep(S_2) = rep(S_1 + S_2). On the other hand, events that are perceived as anomalous are events for which that's not true: rep(S_1) + rep(S_2) != rep(S_1 + S_2).

We're already well into the land of pretend mathematics here. We have two non-quantifiable "seeds"; but we can add them together... We're pulling group-theory type concepts and notations, and applying them to things that absolutely do not have any of the prerequisites for those concepts to be meaningful.

But let's skip past that for a moment, because it gets infinitely sillier shortly.

They draw a cartesian graph with four quadrants, and label them (going clockwise from the first quadrant): T (for tangible), I (for intangible - aka, not observable in tangible reality), U (for unconscious), and C (conscious). So the upper-half is what they consider to be observable, and the bottom half is non-observable; and the left side is mind and the right side is matter. Further, they have a notion of "hard" and "soft"; objective is hard, and subjective is soft. They proceed to give a list of ridiculous pairs of words which they claim are different ways of expressing the fundamental "hard/soft" distinction, including "masculine/feminine", "particulate/wavelike", "words/music", and "yang/yin".

Once they've gotten here, they get to my all-time favorite PEAR statement; one which is actually astonishingly obvious about what they're really up to:

It is then presumed that if we appropriate and pursue some established mathematical formalism for representing such components and their interactions, the analytical results may retain some metaphoric relevance for the emergence of anomalous mind/matter manifestations.

I love the amount of hedging involved in that sentence! And the admission that they're just "appropriating" a mathematical formalism for no other purpose than to "retain some metaphoric relevance". I think that an honest translation of that sentence into non-obfuscatory english is: "If we wrap this all up in mathematical symbols, we can make it look as if this might be real science".

So, they then proceed to say that they can represent the seeds as complex numbers: S = s + i(sigma). But "s" and "sigma" can't just be simply "pre-material" and "pre-mental", because that would be too simple. Instead, they're "hard" and "soft"; even thought we've just gone through the definition which categorized hard/soft as a better characterization of material and mental. Oh, and they have to make sure that this looks sufficiently mathematical, so instead of just saying that it's a complex, they present it in both rectangular and polar coordinates, with the equation for converting between the two notations written out inside the same definition area. No good reason for that, other than have something more impressive looking.

Then they want to define how these "seeds" can propagate up from the very lowest reaches of their non-observable region into actual observable events, and for no particular reason, they decide to use the conjugate product equation randomly selected from quantum physics. So they take a random pair of seeds (remember that they claim that events proceed from a combination of at least two seeds), and add them up. They claim that the combined seed is just the normal vector addition (which they proceed to expand in the most complex looking way possible); and they also take the "conjugate products" and add them up (again in the most verbose and obfuscatory way possible); and then take the different between the two different sums. At this point, they reveal that for some reason, they think that the simple vector addition corresponds to "rep(S_1) + rep(S_2)" from earlier; and the conjugate is "rep(S_1+S_2)". No reason for this correspondence is give; no reason for why these should be equal for "non-anomalous" events; it's just obviously the right thing to do according to them. And then, of course, they repeat the whole thing in polar notation.

It just keeps going like this: randomly pulling equations out of a hat for no particular reason, using them in bizzarely verbose and drawn out forms, repeating things in different ways for no reason. After babbling onwards about these sums, they say that "Also to be questioned is whether other interaction recipes beyond the simple addition S_12 = S_1 + S_2 could profitably be explored."; they suggest multiplication; but decide against it just because it doesn't produce the results that they want. Seriously. In their words "but we show that this doesn't generate similar non-linearities": that is, they want to see "non-linearities" in the randomly assembled equations, and since multiplying doesn't have that, it's no good to them.

Finally, we're winding down and getting to the end: the "summary". (I was taught that when you write a technical paper, the summary or conclusion section should be short and sweet. For them, it's two full pages of tight text.) They proceed to restate things, complete with repeating the gibberish equations in yet another, slightly different form. And then they really piss me off. Statement six of their summary says "Elementary complex algebra then predicts babble babble babble". Elementary complex algebra "predicts" no such thing. There is no real algebra here, and nothing about algebra would remotely suggest anything like what they're claiming. It's just that this is a key step in their reasoning chain, and they absolutely cannot support it in any meaningful way. So they mask it up in pseudo-mathematical babble, and claim that the mathematics provides the link that they want, even though it doesn't. They're trying to use the credibility and robustness of mathematics to keep their nonsense above water, even though there's nothing remotely mathematical about it.

They keep going with the nonsense math: they claim that the key to larger anomalous effects resides in "better alignment" of the interacting seed vectors (because the closer the two vectors are, in their framework, the larger the discrepancy between their two ways of "adding" vectors); and that alignments are driven by "personal need or desire". And it goes downhill from there.

This is really wretched stuff. To me, it's definitely the most offensive of the PEAR papers. The other PEAR stuff I've seen is abused statistics from experiments. This is much more fundamental - instead of just using sampling errors to support their outcome (which is, potentially, explainable as incompetence on the part of the researchers), this is clear, deliberate, and fundamental misuse of mathematics in order to lend credibility to nonsense.

Finally: the Kripke Model for Intuitionistic Logic

2006-05-26T20:13:00.000-04:00

As promised, today, I'm going to show the Kripke semantics model for intuitionistic logic.

Remember from yesterday that a Kripke model has three parts: (W, R, ||-), where W is a set of worlds; R is a transition relation between worlds; and "||-" is a forces relation that defines what's true in a particular world.

To model intuitionistic logic, we need to add some required properties to the transition and forcing relations. With these additional properties, we call the transition relation "<="; "A <= B" means that B is accessible from A. For an intuitionistic Kripke model, the transition relation "<=" must be both reflexive (A <= A) and transitive (if A <= B and B <= C, then A <= C), making it a pre-order relation - that is, a relation that has the essential properties of "<=" that is necessary to define a partial order over its domain. The forces relation, "||-" also needs some additional conditions: (these conditions are based on the definitions from the wikipedia article on Kripke models; I can't remember them without help, so I used the article as a reference.)

for all w,u in W such that w <= u, for all statements s if w ||- p, then u ||- p. This condition basically says that if a statement is true/valid in a particular world w, then it must be true in all worlds accessible from w - meaning that in intuitionistic logic, once a statement is proven, it can't be taken back.
for all w in W, w ||- A and B if/f w ||- and w ||- B. "A and B" is provable in w only if both A and B are provable.
for all w in W, w ||- A or B if/f w ||- A or w ||- B. "A or B" is provable in w only if either A or B is probable in w.
w ||- A implies B if/f for all u such that w <= u, (u ||- A) implies (u ||- B). Being able to prove that "A implies B" in w means that in every world accessible from w, if you can prove A, then you can prove B.
There is no contradictory statement (written _|_) such that w ||- _|_.

The last line in there is actually a bit of a cheat: you can think of intuitionistic logic as a logic where at a given point of time, a statement can have three truth values: T (top), which means provably true; _|_ (bottom) which means provably false, and unproved. The last property of the forces relationship means that under no conditions can the "forces" relation say that a proposition is true if it is provably false.

So: suppose we have an intuitionistic logic consisting of a set of statements, which we'll call X. The Kripke model for X is the triple (W, <=, M), where W is the set of worlds related by a "<=" relation that has the intuitionistic properties that we just discussed. M is a set of sets: for all w in W: exists one M_w in M, where M_w is an L-structure for X. (An L-structure is a formal way of defining what statements are proved true - and for statements with variables, the bindings of those variables to values for which the statement has been proved true. For the purposes of understanding, you can think of M_w as a function that takes a logical statement, and a list of values for the variables in that statement, and returns "true" if the statement is proved true, and false if the statement is proved false; and the statement is not in the domain of the function if it's truth value hasn't been proved.) The M_w's for intuitionistic logic have a set of properties that come from the meaning of statements in the logic:

if u <= v, then domain(M_u) subset domain(M_v)
For any function f, in the logic, for all a in domain(f) in M_u, f(a) in M_u = f(a) = M_v.
For any predicate P(a_1,a_2, ..., a_n), if P(a_1,a_2, ..., a_n) is true in M_u, then it is true in M_v.

Now, finally, we can get to the last step in defining our model of intuitionistic logic: the forces relation based on M. What we need to do to make M work as a forces relation is to separate it into two parts: the truth/validity of concrete statements (that is, statements with all variables bound to specific values), which we write using the old forces notation, ||-; and the mapping of variables and functions to values. We call that mapping an evaluation function; for a statement A in X, we write A[e] for A with variables bound by e.

So: given an evaluation e of variables from M_w, w ||- A[e] is defined by:

w ||- P(a_1,...a_n)[e] if/f P(a_1[e],...,a_n[e]) is in M_w: Evaluating a predicate means the same thing as keeping the predicate unchanged, and evaluating each of its parameters separately.
w ||- (A and B)[e] if/f w ||- A[e] and w ||- B[e]: a typical and definition.
w ||- (A or B)[e] if/f w ||- A[e] or w ||- B[e]: a typical or definition.
w ||- (A implies B)[e] if/f forall w <= u: u ||- A[e] implies u ||- B[e]: an implication is true if, in the model, you can prove its constituents in the next step. (This is the opposite of its definition in the logic: in logic, we'd say that given A implies B and A, you can conclude B. In the model, we go the other way, and say that you can conclude that A implies B if, for all possible transitions, the next world allows you to conclude either A or not B.)
w NOT ||- _|_: no w can force a contradiction.
w ||- (exists x : A)[e] if/f exists a in M_w such that w ||- A[e], and e maps x to a. An exists statement is provable only if we can show a concrete, specific value for which the statement is true.
w ||- (forall x : A)[e] if/f forall u such that w <= u: forall a in M_u: u ||- A[e] where e maps x to A: a universal statement is provable if every possible next world can prove that the statement with all possible bindings of variables are true.

What we've done now is to define a way of describing the meaning of any statement in intuitionistic logic, and any reasoning step in intuitionistic logic in terms of sets, in a way where if we do the translation of the logical statement down to the sets, the statements about the sets will always be true and correct; and if we reason from the sets that correspond to the logic, anything we can do will produce a well-defined, meaningful, and valid statement in the logic.

The particularly nice thing about an intuitionistic logic with a Kripke model is that for any statement which is provably true, we can use the model to find specific values for the variables in the statement for which its true; and if a statement is false, we can find specific values for the variables in the statement that produce a concrete counterexample. We can't always do that in regular predicate logic: regular predicate logic allows us to do inferences from things like "exists" statements if we know that some value must exist for which the statement is true, even if there's no way for us to figure out what that value is. Likewise, in regular predicate logic, we can infer that a forall statement is false if we know that there must be some value for which it's false; in intuitionist logic, we need to be able to show a specific example for which it's false.

Friday Random Ten, 5/26

2006-05-26T09:18:00.000-04:00

Lunasa, "Punch". Trad irish, by the best in the business.
Dirty Three, "In fall". The Dirty Three is one of those "post-rock ensembles" which have me seriously hooked. Very, very cool stuff, which kind of defies description. Just get some and listen to it!
The Flower Kings, "Monsters and Men". A 20 minute long track of the newest FK release. As usual for the Flower Kings, it's bloody brilliant.
Peter Hammill, "The Wave". Peter Hammill is one of the original progressive rock guys, the founder of "Van Der Graff Generator". This is off of a live solo CD with Peter doing vocals and keyboards, accompanied by an electric violin. That's it - no drums, no guitars, just voice, keyboard, and violin.
Glass Hammer, "Run Lissette". Glass Hammer is a recent discovery of mine; they're an American neo-progressive band. They sound something like a cross between Yes and old Genesis, with a bit of Flower Kings for good measure. They're a really great band.
Porcupine Tree, "Sleep of No Dreaming".
John Corigliano, "Etude Fantasy 5: Melody" from "Phantasmagoria". Corigliano is one of the finest composers working today, and this is a great piece of his work. Not quite up there with his clarinet concerto, which is one of my very favorite modern compositions, but with stuff this good, "not as good as his best" is also "100 times better than anything else".
ProjeKct Two: "Sector Drift [The Planet Zarg Quartet Pt. 6]". Goofy free improv from one of the King Crimson projects - Fripp, Belew, and Gunn, with Belew playing a percussion synthesizer instead of a guitar. Surprisingly good considering that Belew had no experience with the instrument before recording this, live.
Tempest, "The Barrow Man". An neoprogressive electric folk band. These guys are interesting. The leader of the band is Swedish; they play a blend of Swedish and Celtic based melodies, in a progressive rock style. Sort of Fairport Convention on steroids, led by an electric mandolin.
Whirligig, "Through The Bitter Frost And Snow". A really beautiful ballad from a NYC based trad Irish band. There's also an Irish trad Irish band called Whirligig, which has nothing to do with the NYC band - one of those unfortunate collisions that tends to happen with very small-label bands.

Magic-23 update: the author responds

2006-05-25T18:32:00.000-04:00

I received a response to my post Magic-23 from the author of the article I was mocking. As I did earlier with Berklinski, I think that if the author is willing to take the time to respond to me, it's only fair to let their response be seen by readers. Mr. Osborne took the time to write a very civil response, and so I'm going to post it here, with my own comments at the end. His message is unedited, and quoted verbatim:

Hi Mark,

I read your essay 'Good Math, Bad Math', which criticizes my work on the 23.5-degree references and makes it all look rather silly, which is disappointing really.

I'm not really that interested in the '23' number phenomenon, neither am I "in on a joke", as one of your correspondents states, and neither am I out to exploit anything and make a quick buck.

This is a real phenomenon. I have spent years researching this, and many others have verified my findings.
I think my presentation is well balanced and is merely based on what I have discovered despite my own beliefs, if any.
Someone has to discover and bring attention to this. Surely it was intended that someone should.

Attached is a chapter from my book. This is what all these references are leading to and more.

Also, viewing the images would help. See here, another version.

http://www.freewebs.com/garyosborn/235degrees.htm

Also take a look at this version of the 23.5 Degree presentation on my website.

http://garyosborn.moonfruit.com/revelations

Also I don't have a book entitled 'Revelations'.

So at the end of the day, I am merely bringing attention to the things I have discovered and I don't see that as wrong, and I don't think my findings are "chock full of insanity" either.

Don't want to lecture you Mark, but first and foremost. I'm always careful not to believe in something that will stop me finding other alternatives, and most of the time, and if I search long enough within my own mind, I find that I really don't believe in anything 100%.
I always try to remain neutral and balanced.
We are all prone to experiencing, seeing and believing whatever it is we are focusing on at the time and really because we are creating everything ourselves, and many of us don't realise it.

Read my article The Synchroholoform on my website. There's a "bigger picture" to all this and it appears to be related to the creative nature of our own consciousness and that's something I always consider.

Oh and I too like The Flower Kings and go to see them whenever the opportunity arises - so that's something we have in common.

Kind Regards,
Gary Osborn

My response is going to be brief.

Every crackpot in the world, upon being confronted by a debunker, invariably comes back with some kind of comment about having an open mind. Having an open mind is important - but so is being skeptical. There's a lot of gibberish out there, and there are a lot of people who are either wrong, crazy, or deliberately deceptive: you should always be open to new ideas, but at the same time, you have to look at them very carefully. The reason that I think the 23.5 degree stuff is so goofy isn't because I don't have an open mind - it's because it doesn't meet the test of credibility.

For it to be believable, I would need to accept:

That you can, looking at a painting, distinguish between the
"perspective angle" of 22.5 degrees, and the axis angle of 23-23.5 degrees.
That painters throughout history could both distinguish and paint angles so accurately that they could deliberately make a line between 1/2 and 1 degree different from the standard perspective angle.
That there was such a threat from the church that this knowledge had to be kept secret, but at the same time, it was so widespread that there are dozens of different painters and architects who all not only knew about it, but visibly inserted it in their work.

I don't buy that, at all.

But it gets worse: to get to your conclusion about a catastrophe that pushed the earth onto its tilted axis, I would have to accept:

Our understanding of gravity - which tests out accurately to a incredible degree - is entirely wrong. We can plan space probe trajectories that do double gravitational slingshots and wind up in exactly the right position - travelling millions of miles, and yet reaching a very precise destination with near-perfect accuracy.
The stability of the solar system is an illusion. The fact that we have a uniform ecliptic plane, with a regular pattern of near-circular orbits is something close to impossible to explain mathematically if we assume that there was a catastrophic change in the solar system during the period of human history.
Something drastic enough to tilt the earth on its axis and reconfigure the entire solar system occurred, and yet life on earth was pretty much unaffected; and the event left no geological evidence at all.
A catastrophic change occurred recently enough that people like the Egyptians were able to record it; and yet there are no explicit records of the event - not from the Egyptians, the Babylonians, the Chinese - none of them recorded it in anything like explicit terms - all just used highly ambiguous metaphorical allegories.

Nope. No way this is credible - physics, mathematics, geology, and history all argue against it.

Moving towards models: Kripke Semantics

2006-05-25T10:02:00.000-04:00

To get the formal semantics of intuitionistic logic (and thus lambda calculus), we need a tool called Kripke Semantics. Kripke semantics is an amazing tool, which made it possible to define a lot of things in logics that weren't approachable before. In this post, I'm going to explain the basic ideas of Kripke semantics and how they're used for building models of logics; in my next post, I'll describe the Kripke semantics model for intuitionistic logic.

Modality

The basic idea of Kripe semantics is to associate the truth or validity of logical statements with something like a concept of time called a modality. In a modality, you have a set of states called worlds, with a transition relationship between them called accessibility. A world w assigns truth values to logical statements; and the accessibility relation defines what worlds can be reached from w. (For notation, we usually call the accessibility relation R, and write R(a,b) to mean that b is accessible from a.)

With modality, you have a new property in your logic: the truth value of statements can change when you transition from one world to another. To be able to talk about this, Kripke models have two modal operators that behave sort of like quantifiers over worlds.

L (also written as a square) for "necessarily": LP means that P is true in every possible world;
M (also written as a diamond) for "possible": MP means that P might be true in some world.

L and M are duals, very similar to a temporal version of "forall" and "exists". Just like "forall x : P(x)" is equivalent to "not exists x : not P(x)", Mp = not L not p.

Kripke Models

The semantics of Kripke models comes from the ability to make truth assignments; and truth assignments in turn come from something called a forcing relation. A world "w" in a Kripke semantics model forces statements in the logic if those statements are valid (provable) in that world. The forcing relation "w forces A" is usually written: "w ||- A". A valid forcing relation needs to have three properties:

w ||- not A if/f not(w ||- A): if w forces not A, then it cannot also force A.
w ||- A -> B if/f not(w ||- A) or (w ||- B). This is very close to one of the inference rules of normal predicate logic: A -> B if/f (not A) or B.
w ||- LA if/f forall u in W (R(w,u) implies u ||- A): we can say that a statement is necessarily true in a world w if and only if that statement is true in every world accessible from w.

With that, we've now got enough to be able to define what a model is in Kripke semantics: A Kripke model for a logic L consists of three things, usually written as a triple (W, R, ||-): W is a set of worlds; R is an accessibility relation between elements of W; and ||- is a forcing relation from members of W to statements in L. Without the forcing relation, given just the worlds and the accessibility relation, that piece of a model is called a Frame.

A logical statement or formula A is true in a model (W,R,||-) if forall w in W, w ||- A.

Building Kripke Models for Logics

Suppose we have a modal logic, X. What we want in a model for X is a way of saying what statements mean in a way that shows that they're consistent - that is, that the statements that are provable in the logic are really valid inferences from the axioms of the logic.

The basic construct of kripke models for logics is called maximum consistent sets. A set of statements S is consistent in a logic X if there is no way to derive a contradiction from any combination of statements in S, axioms of X, and standard inference (if A->B and A then B) over S and axioms of X. A maximum consistent set MCS for X is a consistent set for X where MCS is not a proper subset of any other consistent set in X.

The Kripke model of a logic X is a standard Kripke model (W,R,||-), where:

W is the set of all MCSs for X.
R(A,B) if/f for all statements s in X, (L s) in A implies s in B
A ||- s if/f s in A

One incredibly cool property of the MCS construction of a Kripke model of a logic X is: for every statement s which can be shown to be unprovable in X, the Kripke model contains a counterexample. This will turn out to be really valuable in the model for intuitionistic logic: it means that in intuitionistic logic, we can enumerate the values for which a statement is true.

Skeptics Circle

2006-05-25T09:59:00.000-04:00

The Skeptics Circle number 35 is up at Skeptico with a special guest blogger! Head on over and check it out, for a good laugh and a lot of good skeptical blogging.

Logic Fun: Intuitionistic Logic

2006-05-24T13:17:00.000-04:00

It's time for a bit of a side-track from the series of articles about lambda calculus. Models of lambda calculus are based on something called intuitionistic logic, so I'm going to write a bit about that. It's also quite interesting in its own right.

Syntactically, intuitionistic logic looks the same as first order predicate logic. But the meanings of statements in it are often quite different. The basic idea behind intuitionistic logic is that some of the statements that you can make in propositional logic are too strong. In intuitionistic logic, a statement is only true if there is a proof that it is true; a statement that something is false means that that statement cannot be proved - so the negative statement "not P" can be read as an affirmative statement: "There is a proof that there is no proof for P".

This has the implication that many inferences that we're used to in propositional logic are not accepted in intuitionistic logic:

In propositional logic, the statement "X or not X" is a tautology, that is a statement that is always true: the statement means that either X is true, or X is not true. In intuitionistic logic, it is not: the statement "X or not X" means that we can prove that X is true or we can prove that X is false. X is true in intuitionistic logic if and only if we have a proof that X is true; X is false if and only if we can prove that there is no proof for X. If we do not have a proof for either the truth or the falsehood of X, then "X or not X" is not a true statement: it's possible that X is true, but we don't have a proof for it.
In propositional logic, we can often infer statements like "exists X : P(x)", even though we don't know what x is. In intuitionistic logic, to infer that statement, it must be possible to demonstrate at least one value for which it's true. Similarly, in order to prove that a universal statement is false, we need to be able to show a concrete counterexample that demonstrates its falsehood.
In both propositional and intuitionistic logic, the statement that "P -> not not P" is true. But in intuitionistic logic, "not not P -> P" is not true. Since "not P" means "We can prove that there is no proof of P", the fact that P is true (i.e., that we have a proof that P is true) means that we can prove that "not P" is false - because the fact that there is a proof for P provides a concrete counterexample to the statement that there is no proof for P - so "not not P", which says "There is no proof that there is no proof for P" is proven true.

But going the other direction: the fact that we can't prove that there is no proof for P does not imply that there is a proof for P. Being unable to prove that there is no proof for something is a much weaker statement that saying that that thing is true.

One way to think of intuitionistic logic is to think of it as if there were actually three values that can be assigned to a predicate: it can be in one of two definite states (proved true or proved false) or it can be in an indefinite state (unproven). If a predicate P is unproven, then we can assert neither that P is true nor that P is false. But if the predicate is in an indefinite state, and we can show a proof, then we can move it to a definite state: if we can find a way to provide a proof of P, then it becomes true; or if we can show that it's unprovable (generally through a counterexample), then it becomes false.

The formal semantics of intuitionistic logic are more complicated than the semantics of predicate logic. They tend to involve things like lattice theory. In another post, I'll talk about one way of describing the semantics of intuitionistic logic called Kripke Semantics. Kripke semantics is useful not just for intuitionistic logic, but for a lot of other things, like temporal logics, modal logics, and model checking. (Wikipedia describes another version of the semantics of intuitionistic model based on something called Heyting Algebra, but I'm not familiar with it.)

Tangled Bank #54

2006-05-24T08:24:00.000-04:00

There's a new Tangled Bank up a Coturnix. Good stuff, go read.

In a related note, since Coturnix mentions his upcoming move, I'll also mention that "Good Math, Bad Math" will also be making the jump to ScienceBlogs in early June. The misery of coping with Blogger will soon come to an end!

Nyah, Nyah, my infinity is bigger than yours!

2006-05-23T21:20:00.000-04:00

One really weird thing that you can do with math is compare the sizes of infinitely large things. It's a really strange notion, but it's actually a fairly important one - and one which interesting ties together computation and pure mathematics in a very clean way.

Suppose I have two infinite sets. I can show that these two infinite sets are the same size, by showing that I can build a total one-to-one map between the two sets.

For example, take the set of even numbers, and the set of odd numbers. They're the same size - because I can create a mapping function f from even to odd: f(n) = n + 1. For every even number, it maps to exactly one odd number; for every odd number, there's exactly one even number that maps to it.

A more counter-intuitive example would be: take the set of even integers, and the set of all integers. We know that the set of even integers is a subset of the set of all integers. Intuitively, most people would guess that the set of integers is twice as large as the set of even integers. But the two sets are the same size, because I can do a perfect mapping from integer to even integers: f(n) = 2*n. Every integer maps onto one even integer; every even integer is mapped to one by integer. So they're the same size.

Ok. How about the set of rationals and the set of integers? Same size. Make a two dimensional table with the integers on both dimensions. Now, trace the diagonal: 1/1, 2/1, 1/2, 3/1, 2/2, 1/3, 4/1, 3/2, 2/3, 1/4. Delete anything you've seen before. (1/1 is the same as 2/2, so we'd delete 2/2.) That gives us a list of every possible rational number. Map each rational to its position in the list, and poof! A one-to-one mapping from rational numbers to integers.

So, what's bigger?

The set of irrational numbers is larger than the set of rational numbers.

To remind anyone who doesn't remember: a rational number is either an integer, or a real number that can be represented as the ratio of two integers. So 1/2, 17/4, etc., are all rational numbers. On the other hand, pi, the square root of two, the root of the natural logarithm, and many other things are irrational numbers - numbers that can't be represented by a fraction. When you write in decimal expanded form, a rational number will always end in a repeating sequence of digits. 1/3 is 0.3333333 - the three repeats forever. 1/2 is 0.500000000... the 0 repeats forever. An irrational number will go on forever, never going into a continual repeating pattern. Here, you can find the first 4 million digits of pi.

How can I show that the set of irrationals is larger than the set of rationals?

Well, basically, I can't define a map from integers to irrationals. Irrationals are weird buggers, and I can't really say where they all are. They don't lay out nice and evenly the way that the rationals do.

In fact, it turns out that no matter how I try to form a map from integers to irrationals, I'll be missing something. Here's a quick version of why. It's a classic diagonalization argument.

Let's look at the set of all real numbers between zero and one. Now, suppose that this set is the same size as the set of integers. This would mean that there is a mapping from integers to real numbers between zero and one.

If that's true, then we can, in theory, make a list of the decimal expansions of all of the real numbers between zero and one.

Then we can define a function, r(n), which gives us the "r"th digit of the "r"th real number in the list.

Now here's where we pull a fast one. We define another function i(n). If r(n) = 1, then i(n) = 2. If r(n) != 1, then i(n) = 1. If we lay out a new number 0.(i(1),i(2),i(3),i(4),...), then that number is different from any number in our list of reals in at least one digit. So we have a real number between zero and one - and it's not in our list. Contradiction, therefore the list can't exist. (Note, this was corrected to fix a typo; originally, I accidentally wrote "0.(r(1),...)". Thanks to the anonymous commenter who pointed it out.)

So, now we know that the set of real numbers between zero and one is larger than the set of rational numbers between zero and one. But since we know that the set of rationals is the same size as the set of integers, then that means that the only way that the set of reals can be larger than the set of integers is if the set of irrationals is larger than the set of rationals.

How does this connect to computation? Well, there's a notion of something called a countable set. A countable set is a set which is either finite, or which has a one-to-one mapping from the integers. It turns out that the set of countable sets is a superset of the set of recursively enumerable sets. Infinite sets larger than the countable sets cannot be enumerated by any computing device. They are fundamentally non-computable things. (The last paragraph was heavily edited to correct an error pointed out in the comments. See the comment thread for the details. As usual, thanks to the commenters who pointed out the errors!)

RePEARing Bad Math

2006-05-22T21:00:00.000-04:00

I was looking at the site-meter statistics for this site, and who was referring to it, and I came across a discussion linking to the Global Consciousness Project. The GCP is a very flaky train-wreck which is trying to measure the purported cumulative affects of human consciousness on, well, on any old random thing they can think of. It turns out that the GCP is another face of PEAR at Princeton. Man, what is it with Princeton?

What GCP does is run the PEAR random number generators non-stop, all the time, logging the results. Then when there's an "interesting" event in the world, they got back to the logs, and see if they can find any "anomalous patterns" in the data, where anomalous patterns are short periods of time where the mean of the random numbers is different from the normal expected mean.

Here's an example of what they do, in their own words, from here:

The first formal prediction for the EGG project was made by RDN, in 1998-08-08, while traveling in Halifax. It concerned the Embassy bombings in Nairobi and Tanzania, on 1998-08-07 at 07:35 UTC. Upon my return home, prior to examining data, I made the specific predictions described below. These terrorist attacks exemplify a tearing of the social fabric that would shock a global consciousness temporarily. For this particular event, we had only the general outline for predictions: a period of time, say 10 minutes, surrounding the point event, and a period, say a few hours, following the event during which the world becomes conscious of what has happened.

An exploratory analysis based on 15-minute data segments from three eggs looked at the event-period from 07:15 to 07:45, and a three-hour consciousness-spreading period from 07:15 to 10:00. The associated probabilities indicate significant deviations for both time-periods. At that time we did not have sophisticated processing capabilities, but a hand calculation could be made using the automatically generated Z-scores for 15-minute blocks. It indicated significant deviations in both the short period defined for the event: Chi-square 18.039, 9 df, p=0.035, and for the aftermath, inclusive of the event: Chi-square 69.536, 36 df, p=0.00066.

So: they pick an event that they believe should affect the "global consciousness". Then they take short time periods associated with the event, and search for a time period where the mean value from their random number generator is not exactly what it should be.

They have an extensive list of events on their site, which they claim are used "rigorously" to test whether there are anomalous patterns associated with events. For most of them, they were able to discover one second intervals that were "anomalous".

What's wrong with this?

Given a huge database consisting of sequences of random numbers, you expect to see small deviations. If it never deviated from the mean, you would actually conclude that the data was fake; you expect to see some fuzz. Now, take that huge quantity of data (they're generating 200 bits per second at each of 98 different random number generators); and take a swath of time (minutes to hours) associated with an "event", and see if you can find a one-second period of time for which the random numbers deviate from the expected mean. For any event, at any point in time, you can probably find a "significant" deviation for a couple of seconds; and they consider one second enough to be meaningful.

They actually make data from their generators available through their website; when I get a chance, I'm going to try to prove my point by trying a few dates that have no particular significance to anyone but me: the times my children were born (7/30/2000, 9:35am, and 4/10/2003, 8:40pm), the tenth anniversary of my wedding (the specific 20 minutes of the ceremony) (6/5/2004, 2-2:20pm), and the only time my dog every bit anyone (that being me, for freaking out while he vomited all over my house on, I think, 7/10/1998, around 5pm).

I'll let you know the results.

Probability and Fine Tuning

2006-05-22T09:34:00.000-04:00

The ways that creationists play with "big numbers" games never ceases to amaze me. Over the weekend, I came across yet another extremely silly attempt to show that life on earth is so improbable that it must be the result of divine intervention.

The reason that I'm mentioning this one is that it's a different approach to generating the big number. Instead of sticking with the usual argument about the supposed probability of abiogenesis on earth, it tries to use a probabilistic version of the fine-tuning argument: that there are specific properties of the universe as a whole, and of the earth in particular, that make life possible, and that the likelihood of all of those properties having the correct values is so unlikely that they must be the result of deliberate divine intervention to make life on earth possible.

This bugger is just chock-full of problems. The most important one is what I call the fake numbers error: most of the numbers are just made up. For example, they cite the "local abundance and distribution of dark matter" as a property that must have a specific value, and state that the probability that this will fall within the range required for life as "0.1". At present, we don't know precisely what dark matter is, what properties it has (beyond the fact that it has a gravitational influence on bright matter), or how it's distributed. So claiming that it's distribution is a required property of the universe for life is silly, and assigning a meaningful specific probability number for that distribution matching the current unknown value is impossible. Many of their "parameters" for life are like this: they're just numbers pulled at random out of a hat. They've got 322 factors: my estimate is that at least 90% of those are fabricated. What's worse is that many of those aren't just made up numbers; they're utterly silly as parameters for life. I mean, "infall of buckminsterfullerenes from interplanetary and interstellar space upon surface of planet"?

They also make liberal use of the false independence problem. This is where you take two related factors, but treat them as if they were unrelated, in order to inflate your probabilities. A trivial example of this kind of problem is: what's the probability of flipping a coin twice, and getting heads both times? 1/4. What's the probability of flipping a coin three times, and getting heads all three times? 1/8. Good so far. Now, suppose that I've already flipped a coin twice, and gotten heads both times. What's the probability that I'm going to get 4 heads in a row? A false independence would say: 1/16th - because it ignores the fact that flipping heads twice affects the probability of flipping heads four times in a row: I'm already halfway there.

Examples of this from their list: they take "relative abundances of different exotic mass particles", and "decay rates of different exotic mass particles" as independent factors. They're not independent: the abundances of the exotic particles and their decay rates are both dependent on the properties of the universe that allow those particles to exist. Or even more obvious: "proximity to supernova", "timing of supernova", and "supernova rates and timing" as three different parameters. They play this game over and over again, creating lists of factors to inflate their improbabilities, even those those factors are not independent.

What's particularly humorous is the number of times that they include "parameters" for the probability of life on earth that are based on the existence of life on earth! By my count, they have at least 18 factors that explicitly depend on the existence of life on earth in order to argue that life on earth is improbable! (9 parameters specify quanities of certain kinds of bacteria, 1 specifying quantity of fungi, one specifying quantity and timing of vascular plants, 1 specifying quantity and timing of carbonate producing animals, etc.) In all, they argue that the existence of life on earth is responsible for a probability factor of "1/10^42" against the existence of life on earth! Yeah, the existence of life on earth sure does make for a strong case that life on earth is unlikely!

They also mix in a bunch of earth-specific factors ("position and mass of Jupiter relative to earth", "amount of outward migration of Neptune", etc.); but they claim to be computing the probability of life existing around any potential life-supporting body in the universe. Yep, the odds of any other earth-like planet having Jupiter as a neighbor is pretty unlikely all right!

They go on, and on, and on like this - with barely a single valid number in the entire exercise, to conclude:

Thus, less than 1 chance in 10^282(million trillion trillion trillion trillion trillion trillion trillion trillion trillion trillion trillion trillion trillion trillion trillion trillion trillion trillion trillion trillion trillion trillion trillion) exists that even one such life-support body would occur anywhere in the universe without invoking divine miracles.

Magic 23

2006-05-21T11:22:00.000-04:00

Since I posted a couple of items about gematria, and the kinds of gibberish that it can be used to create, I've been receiving tons of emails with people pointing me at silly gematria sites on the net. I had no idea this gibberish was so widespread!

In general, it's all the same kind of thing: stream-of-consciousness rambling, using numbers the guide the streams. It's very funny in its way, but it gets dull pretty quickly: read one of 'em, and you might as well have read them all.

But once in a while, you find a prize: something that's different, special in its own uniquely ridiculous way. And an anonymous person send me a link to one of those. This is really fantastically goofy, and there's a whole group of people who are actively obsessed with it. It's the "235" gang. They believe that there are all sorts of magical connections involving the numbers "2" and "3"; some also include "5", but others claim that 5 isn't special on its own, because it's just the sum of 2 and 3. A couple of their writeups are:

The first one is just the usual kind of gematriacal rambling, but it's got the most exhaustive list of the 235s that I could find. The second one is better; it's just chock-full of crunchy insanity.

Here's how it starts out:

For many years, we have been told by Egyptologists and historians that the pyramids of ancient Egypt were the tombs of the Pharaohs and nothing more.

This is the ‘official line’ and this could indeed be true as regards the majority of the pyramids in Egypt which were clearly built by the ancient Egyptians – many of which collapsed to rubble soon after being built.

But ask the many researchers (those not funded by institutions) who have made a life time study of the pyramids, and they would most likely tell you that the Great Pyramid of Giza is unique – not just because it is a perfect pyramid which has withstood the ravages of time – but because it appears that one of its purposes was to preserve knowledge.

They will also tell you that much meaningful information has already been derived from the Great Pyramid, even though many scholars and academics – i.e., those funded by the institutions and establishments – have never really accepted this data and continue to ignore it.

During the last months of 2002, I made a new major discovery about the Great Pyramid of Giza: that the Polar or Celestial Axis of the Earth, which is presently tilted at 23.43 degrees, (given the round figure of 23.5º in most text books on the subject) is clearly referenced in the geometrical structure of the Pyramid.

Such a bundle of silliness, just in the first 5 paragraphs!

The conspiracy! All of those people "funded by institutions" are trying to cover up the truth!
The mounds of "data" that everyone ignores!
The lone genius making spectacular discoveries all by himself!
The "rounding" of the angle of the earth's axis and the position of the Giza pyramid to get the magical "5" in, even though the egyptians did not use decimal angle measurements! (To the best of our knowledge, the egyptians used mathematical units derived from the babylonians, which is where the "degree" unit comes from; the babylonians used a sort of base-60 math - thus the 360 degrees, 60 minutes, 60 seconds angle measurements.)

Ah, but it gets much better. Because, you see, the conspiracy is trying to cover up the true history of the earth! But initiates of the great mysteries throughout history have been trying to provide hints! In the pyramids, in paintings, in maps, in the layouts of cities!

We also find that the Great Pyramid is actually pointing to its own location on the earth – being almost 30º N from the Equator, and this is the decisive factor for me as regards the credibility of this encoded information.

See, the pyramid is pointing out its own location, because it's got this angle of 23.5 degrees, which is the three magic numbers 2, 3, and 5; and it's 30 degrees north, which is not just 10 times the magic number of three, but it's also the angles of the "perfect" triangles that make up the sides of the pyramid!

This new discovery about the Great Pyramid is remarkable in itself; but how I actually uncovered this hidden information never fails to amaze me – even now as I reflect on it – as it involved a 17th century painter who on the surface appears to have had nothing to do with Egypt and the pyramids of Giza . . . an artist whose works of art are believed to contain a code which many researchers have endeavored for years to decipher with no real success.

It would surprise many to learn that I first discovered this information about the Great Pyramid through studying and deciphering the hidden codes in three paintings by the French artist Nicolas Poussin (1594–1665). These initial discoveries and my own interpretation of the data will be revealed for the first time in my book Axis of God.

And of course, we can't have all this yummy insanity without a sales pitch! See, he discovered this secret about the great pyramid because of the paintings of a french artist; and all you need to do to see how he discovered it is to buy his book!

However, the truth is, that the paintings or sources I have analyzed are all associated by theme, and also contain deliberately planned, conspicuous linear items and features that are just “begging to be measured” so as to obtain the angles being presented.

Hmmm... He sees "deliberately planned, conspicuous linear items that are begging to be measured" in all sorts of paintings? I wonder what Freud would think of that?

For the sake of balancing the argument and to try to prove myself wrong, I also looked into the fact that the angle of 22.5 degrees is also a common angle used in art for perspective, as 22.5º is one sixteenth of a 360º circle. I mention this so that others would be aware of this and could perhaps use this in their argument and so test this themselves if interested.
I must point out that I have examined many paintings, and have found that although some of the overall ‘perspective features’ in some paintings are in the ‘right ball-park’ and could therefore be associated with the 22.5º angle of perspective so as to support this given fact, I have found that many suspect features, such as staffs, poles, flagpoles, spears, lances, clubs, bones, limbs, swords and other linear objects, are definitely at an angle of 23.5º or even 23 degrees.

So, by carefully examining paintings, he finds that the linear items begging to be measured are all quite definitely at an angle of 23 or 23.5 degrees - and in a painting, he can clearly distinguish 22.5, 23, and 23.5 degrees. Hmm... Just for kicks, I decided to see how hard it would be to do that. Here's a little diagram, showing three overlapping angles: 22.5, 23, and 23.5 degrees:

Gosh, he's good. He can distinguish between those three angles in a painting! Wow!

But the meaning of the magical 23.5 is deeper than that. After all, what good would a conspiracy be, if there weren't a reason behind it?

But it is at this point that we may ask, ‘why’ is the earth’s inclined axis being referenced in all these sources? After all, some believe, and are of the opinion, that the tilt of the earth’s axis is a ‘natural phenomenon’, and that the 23.5º tilt is necessary as the summer and winter cycles govern life on our planet. But, if this is true, then why do we find references to the angle of 23.5º in paintings on the theme of death, battle, war and conflict?

What exactly did the ‘initiate’ artists know – those who gave reference to this angle? . . What were these people trying to tell us?

My own interpretation, based on a lot more evidence which I have found and have yet to present, is that it was believed by the ‘initiated’ that the tilt of the earth isn’t natural, nor is it an ideal situation. Indeed it is a fact that the early Greek philosophers considered the tilt of the earth to be an unnatural and “irregular condition” and not something that had been set in motion since the beginning of creation.

Yes, he's not just a gematria loony, he's a catastrophist, like the electric universe gang! The reason for the magical numbers 235 showing up all of the time are because we fell from paradise when the earths axis tilted from its perfect position to an angle of 23.5 degrees!

The more I researched into these discoveries; more remarkable data began to present itself: I found that the angle of 52 degrees is also referenced in these same sources and is almost as frequent as the 23.5-degree references.
This is interesting because the significant thing about the angle of 52º is that this is the angle of the inclined sides of the Great Pyramid of Giza . . .

See, 52 degrees is also part of the magical numbers of the great pyramid, and if you can find anything, anything at all that includes something with a measurement that looks like either 23 or 52 degrees, well then, it's obviously a reference to the hidden knowledge of the pyramid by initiates of secret knowledge. By why would they need to hide it?

The Catholic Church was very powerful during the Dark Ages and the Middle Ages – and really until the dawning of Science and the so-called Age of Enlightenment; so to be branded a heretic was very dangerous to one’s health.
Those who knew the truth behind the Church and Christianity would have had to be seen to “toe the line” and so information and knowledge which would have been seen as “heretical” and otherwise suppressed and stamped-out by the Church, would have been encoded – not only to preserve it, but also to secretly pass this knowledge onto others.

Of course! What good is a conspiracy if we can't connect it to the catholic church? You see, the magic numbers referred to hidden knowledge that predates Jesus, and so the church is out to get anyone who tries to talk about it. So, all of those initiates go and hide it in plain sight, so that the church won't notice it, but everyone else will. Because, you see, conspiracies that manage to keep secrets from the general population for thousands of years are incapable of noticing symbolisms which will be obvious to everyone else.

But you know what this conspiracy theory about the great magic numbers of the pyramid is missing? The Masons and the Illuminati! Every good conspiracy has to include them, doesn't it? Ah, don't you start worrying now, he's got it covered!

We find the angle of 23.5º and 52º repeated in Templar and Masonic symbolism – such as the Templar Cross Patee or Maltese Cross and also the Masonic Compass and Set-square which we will come to later. Most surprisingly we find the angle of 23.5º in Leonardo Da Vinci’s famous drawing, Vitruvian Man.

The angle of 23.5º is even referenced in one of the most infamous symbols of them all – the “All-Seeing Eye” in the detached and floating capstone of the pyramid from which rays of light radiate – which is really a reference to the Great Pyramid of Giza which is missing its capstone. This symbol is on every US Dollar bill and it’s amazing how people could have missed this.

Ok, Masons, check. DaVinci, check.

Aw, shucks. No illuminati. Hmmm... Wait a second, let's see if this author talks about the connection between 23 and the Illuminati somewhere else. Gosh, that other 23 theorist I linked to? He references another book by the author of this pyramid stuff, called "REVELATIONS":

Classic conspiracy authors Robert Shea and Robert Anton Wilson (RAW) account the significance of the number 23 as it appeared with great synchronicity in the weird and multi-dimensional voyage of their 'Illuminatus' books. In fact, there might be something much deeper to this message of 23 than the paranoid induced theories of tin foil hat wearing kooks. As we will see, there appears to be a secret message, a secret knowledge, encoded in the number 23.5, among many other recognized in Kabbalistic teachings and numerology.

Let's look at the Bavarian Order of the Illuminati, founded in 1776 by Jesuit trained Adam Weishaupt. There are many theories due to its founding in 1776 coinciding with the American signing of the Declaration of Independence, that Weishaupt and first President George Washington were in fact the same man. Whether they were indeed one in the same, or used as dopplegangers to each other, there are some very strange connections in regards to the 23 when comparing the life and death of these two individuals.

George Washington
Born: Feb 11th 1732
Death: Dec 14th 1799

Adam Weishaupt
Born: Feb 6th 1748
Death: Nov 18th 1811

Washington and Weishaupt were born 5 days, 16 years apart. They died 26 days, 12 years apart. If you add together 5+1+6+2+6+1+2 it again comes to the 'magic' number of 23. But this is just the beginning in an intricate web of deceptive metaphysics that makes up not only the history of the United States of America, but also takes us into the very core and foundation of the Secret Society and religious monument building.

For those interested with delving further into the relations of the 23 alignments, you can find more details at Gary Osborn's website; in a fascinating excerpt from his latest book entitled REVELATIONS. It sheds light on the possible meanings of this prominent and misunderstood number, detailing overlooked pieces of the puzzle which will be uncovered in his 'Axis of God' release, due in early 2007. Gary is also the co-author of underground best-selling 'The Shining Ones', and 'The Serpent Grail'.

Yep, we got our Illuminati connection! Along with the assertion that this is all sane stuff, not any of the tinfoil hat lunacy!

Not loony enough for your tastes yet? Well... take a look at one of the "supporting references" for the 23 gibberish here. Yes indeedy, 23 is even connected to H. P. Lovecraft and Cthulhu!

H. P. Lovecraft, who first wrote of the EOD, entered the Jane Brown Memorial Hospital where he died 5 days later, on 10/2/1937. The numbers in date of HP Lovecraft's leaving this world add numerologically to 23! 1 + 0 + 2 + 1 + 9 + 3 + 7 = 23.

In the H. P. Lovecraft tale, "The Call of Cthulhu," on March 23rd the crew of the Emma landed on an unknown island and left six men dead; and on that date the dreams of sensitive men assumed a heightened vividness and darkened with dread of a giant monster's malign pursuit, whilst an architect had gone mad and a sculptor had lapsed suddenly into delirium! It was on the 23rd that the sculptor, Wilcox, was struck with fever. It was on the 23rd that the sense impacts from Cthulhu were heard and sensitive people heard the Deep Ones chanting. It is of quite pivotal importance to the story. 23 = the number of Cthulhu's influence.

Human beings have 23 pairs of chromosomes. Anything humans might be able to mate with would also have 23 pairs of chromosomes.

About 100 years ago, Dr. Hermann Swoboda, professor of psychology at the University Of Vienna, became interested in the study of cyclical, internal changes affecting humans. He concluded that there were 2 basic rhythms in humans, a 23 day physical cycle is one of them (the other is a 28 day emotional cycle). Since Cthulhu does not have human emotions, It would only have a physical cycle, even if It is not made of matter we can understand. The physical cycle of Cthulhu is 23. In our 3 dimensions of space as we measure time on Earth, that's what it would be.

I can't take it anymore! I think I need to go have a beer. Wait a second - the beer bottles that I made my homebrew stout in... They're 23 ounce bottles!

Programming SKI

2006-05-19T17:58:00.000-04:00

As an interesting followup to the post on combinators: an extremely crazy individual actually implemented a SKI combinator calculus interpreter called Lazy K. And what's even crazier is, he implemented the Sieve of Eristathenes in LazyK. Here it is:


K
(SII(S(K(S(S(K(SII(S(S(KS)(S(K(S(KS)))(S(K(S(S(KS)(SS(S(S(KS)K))(KK)))))
(S(S(KS)(S(KK)(S(KS)(S(S(KS)(S(KK)(S(KS)(S(S(KS)(S(KK)(SII)))
(K(SI(KK)))))))(K(S(K(S(S(KS)(S(K(SI))(S(KK)(S(K(S(S(KS)K)(S(S(KS)K)I)
(S(SII)I(S(S(KS)K)I)(S(S(KS)K)))))(SI(K(KI)))))))))(S(KK)K)))))))(K(S(KK)
(S(SI(K(S(S(S(S(SSK(SI(K(KI))))(K(S(S(KS)K)I(S(S(KS)K)(S(S(KS)K)I))
(S(K(S(SI(K(KI)))))K)(KK))))(KK))(S(S(KS)(S(K(SI))(S(KK)(S(K(S(S(KS)K)))
(SI(KK))))))(K(K(KI)))))(S(S(KS)(S(K(SI))(SS(SI)(KK))))(S(KK)
(S(K(S(S(KS)K)))(SI(K(KI)))))))))(K(K(KI))))))))))(K(KI)))))(SI(KK)))))
(S(K(S(K(S(K(S(SI(K(S(K(S(S(KS)K)I))(S(SII)I(S(S(KS)K)I)))))))K))))
(S(S(KS)(S(KK)(SII)))(K(SI(K(KI)))))))(SII(S(K(S(S(KS)(S(K(S(S(SI(KK))
(KI))))(SS(S(S(KS)(S(KK)(S(KS)(S(K(SI))K)))))(KK))))))(S(S(KS)
(S(K(S(KS)))(S(K(S(KK)))(S(S(KS)(S(KK)(SII)))(K(S(S(KS)K)))))))(K(S(S(KS)
(S(K(S(S(SI(KK))(KI))))(S(KK)(S(K(SII(S(K(S(S(KS)(S(K(S(K(S(S(KS)(S(KK)
(S(KS)(S(K(SI))K))))(KK)))))(S(S(KS)(S(KK)(S(K(SI(KK)))(SI(KK)))))
(K(SI(KK))))))))(S(S(KS)(S(K(S(KS)))(S(K(S(KK)))(S(S(KS)(S(KK)(SII)))
(K(SI(K(KI))))))))(K(K(SI(K(KI)))))))))(S(K(SII))(S(K(S(K(SI(K(KI))))))
(S(S(KS)(S(KK)(SI(K(S(K(S(SI(K(KI)))))K)))))(K(S(K(S(SI(KK))))
(S(KK)(SII)))))))))))(K(SI(K(KI))))))))(S(S(KS)K)I)
(SII(S(K(S(K(S(SI(K(KI)))))K))(SII)))))

From Lambda calculus to Combinator Calculus

2006-05-19T14:47:00.000-04:00

After yesterdays description of the Y combinator in lambda calculus, I thought it would be fun to show some fun and useful stuff that you can do using combinators.

Let's take three simple combinators:

S: S is a function application combinator: S = lambda x y z . (x z (y z)).
K: K generates functions that return a specific constant value: K = lambda x . (lambda y . x).
I: I is the identity function: I = lambda x . x

At first glance, these look like a very strange selection. In particular, S is an odd application mechanism - rather than taking two parameters, x and y, and applying x to y, it takes two functions x and y and a third value z, and applies the result of applying x to z to the result of applying y to z.

But there's a reason. Watch this: each line in the following is one step of reduction:


S K K x =
(K x) (K x) =
x

Poof! We don't need I at all. We just created the equivalent of I using nothing but S and K. But that's just the start: in fact, we can create the equivalent of any lambda calculus expression using nothing but the S and K combinators with no variables.

For example, the Y combinator is:


Y = S S K (S (K (S S (S (S S K)))) K)

Before we go any further, there's one important thing to point out. Note that above, I said that with S K K we created the equivalent of I. It does not reduce to lambda x . x.

So far in lambda calculus, we've said that "x = y" if and only if x and y are either identical, or can be made identical through alpha conversion. (So lambda x y . x + y is equal to lambda a b . a + b, but not equal to lambda x y . y + x.) This is called intensional equivalence. But it's extremely useful to have another idea of equality, which is called extensional equivalence or extensional equality. In extensional equality, an expression X equals an expression Y if/f either X is identical to Y (modulo alphas), or for all a . X a = Y a.

From now on, when we use "=", it will be for extensional equality. We can translate any lambda expression into an extensionally equivalent combinator term. We'll define a transform function C from lambda terms to combinator terms:

(1) C{x} = x
(2) C{E1 E2} = C{E1} C{E2}
(3) C{lambda x . E} = K C{E} if x is not free in E.
(4) C{lambda x . x} = I
(5) C{lambda x. E1 E2} = (S C{lambda x.E1} C{lambda x.E2})
(6) C{lambda x.(lambda y. E)} = C{lambda x. C{lambda y.E}}, if x is free in E.

Let's try a walkthrough:

C{lambda x y . y x}
Curry the function: C{lambda x . (lambda y . y x)}
By rule 6: C{lambda x . C{lambda y . y x}}
By rule 5: C{lambda x . S C{lambda y. y} C{lambda y . x}}
By rule 4: C{lambda x . S I C{lambda y . x}}
By rule 3: C{lambda x . S I (K C{x})}
By rule 1: C{lambda x . S I (K x)}
By rule 5: S C{lambda x . S I} C{lambda x . (K x)}
By rule 3: S (K (S I)) C{lambda x . K x}
By rule 5: S (K (S I)) (S C{lambda x . K} C{lambda x . x})
By rule 1: S (K (S I)) (S C{lambda x . K} I)
By rule 3: S (K (S I)) (S (K K) I)

Now, let's try using "x" and "y" as parameters to that combinator expression, and reduce:

S (K (S I)) (S (K K) I) x y
Let's create some aliases, to make things easier to read: A=(K (S I)), B = (S (K K) I), so our expression is now: S A B x y
Expand S: (A x (B x)) y
Let's unalias B: (A x ((S (K K) I) x)) y
Now, let's get rid of the S: (A x ((K K) x (I x))) y
And get rid of the I: (A x ((K K) x x)) y
Reduce (K K) x: (A x (K x)) y
Expand out the A alias: ((K (S I)) x (K x)) y
Reduce (K (S I)) x, giving: ((S I) (K x)) y
Reduce S: I y (K x) y
Reduce I: y (K x) y
And finally reduce (K x) y leaving: y x

And there we go. Fun, huh?

Friday Random Ten 5/19

2006-05-19T09:52:00.000-04:00

Bach, "Wiewohl Mein Herz In Traenen Schwimmt" from "St. Matthews Passion". Wow, we're off to a good start this week! The St. Matthews Passion is, in my opinion, one of the finest pieces of music composed by one of the finest composers who ever lived. This section is a solo by a soprano; magnificent.
Phil Glass, "Concerto for Saxophone Quartet and Orchestra: Movement III ". Quite interesting how smooth the transition from the Bach to this turned out; but after listening to a two minute long fragment of Bach, the Glass sounds incredibly trite. Normally, I like this piece rather a lot; but listening it after Bach just doesn't work.
Norah Jones, "Seven Years". My sister gave me this CD as a gift; she thought that given the kinds of female vocalists that I like, this would be up my alley. For some reason, it grates on me horribly. Ugh, ugh, ugh. (Sorry Deb!)
Gordian Knot, "The Brook the Ocean". Spectacular instrumental progressive rock. Gordian Knot is an amazing bassist named Sean Malone, and whatever gaggle of folks he can convince to play with him; different tracks on GK CDs include Steve Hackett, Trey Gunn, John Myung, Bill Bruford. This is a great track.
The Clogs, "Sticks and Nails". The clogs call themselves a "post-rock ensemble". They're a quartet consisting of a violist, a bassoonist, a guitarist, and a percussionist. I really don't know how to describe them; they're like a fusion of modern classical, jazz, rock, and I'm not sure what else. But they're absolutely fantastic, fascinating stuff.
Pain of Salvation, "Martius/Nauticus II". Pain of Salvation is a great metalish prog band. This is off of their album "Be", which is an extremely ambitious concept album. It's not entirely successful, but it's got spectacular moments. This track is quite a good one.
Hugh Blumenfeld, "Longhaired Radical Socialist Jew". The greatest gospel song of all time. How can you not love lyrics like "Sometimes I fall into deep despair/When I hear those hypocrites on the air/But every Sunday gives me hope/When pastor, deacon, priest, and pope/Are all singing out their praises to/Some longhaired radical socialist Jew."?
Dirty Three, "It Happened". Another "post-rock ensemble". Dirty Three is slightly more accessible than the Clogs, but no less amazing. They're a trio consisting of a cellist, a guitarist, and a percussionist. They're a bit heavier on the jazz influence than the Clogs, I think mainly because of the style of the percussionist. These guys and the Clogs are really must-listens.
Thinking Plague, "Rapture of the Deep (For Leslie)". Today seems to be a day for deeply strange music. Thinking Plague is a really wierd group. Their guitarist is a member of Robert Fripp's League of Crafty Guitarists, and plays very much in the guitarcraft style; the vocalist is very unusual in that instead of singing as the lead-line of the music, she treats her voice as just another instrument in the band. They tend towards dissonant, sometimes even atonal music, with bits of 12-tone.
The Clogs, "Witch Stick". And the Clogs come up again!

Overall, I think this is my favorite FRT list so far.

Why oh why Y?

2006-05-18T20:32:00.000-04:00

So in the last few posts, I've been building up the bits and pieces that turn lambda calculus into a useful system. We've got numbers, booleans, and choice operators. The only thing we're lacking is some kind of repetition.

This is, alas, going to be a bit difficult. Lambda calculus does repetition using recursion (an explanation of recursion can be found here). But since functions in lambda calculus don't have names, that means that we resort to something tricky. It's called the Y combinator, aka the lambda fixed point operator.

Let's start by looking at a simple recursive function outside of the lambda calculus. The factorial function, n!, is the standard example:


 factorial(n) = 1 if n = 0
 factorial(n) = n*factorial(n-1) if n > 0

If we want to start trying to write that in lambda calculus, we'd need a couple of tools... We need a test for equality to zero, and we need a way of multiplying numbers; and we need a way of subtracting one.

For testing equality to zero, we'll use a function named IsZero, which takes three parameters: a number, and two values. If the number is 0, it returns the first value; if it's not 0, then it returns the second value.

For multiplication - we can't write multiplication until we work out recursion. But we'll just handwave that for now, and have a function Mult x y.

And finally, for subtracting one, we'll use Pred x for the predecessor of x - that is, x - 1.

So - a first stab at factorial, written with the recursive call left with a blank in it, would be:


  lambda n . IsZero n 1 (Mult n (something (Pred n)))

Now, the question is, how do we get the "something" in there in a way that causes it to recurse?

The answer is something called a combinator. A combinator is a special kind of higher order function which can be defined without reference to anything but function applications. (A higher order function is a function which takes functions as parameters and returns functions as results). The Y combinator is the special, almost magical function that makes recursion possible. Here's what it looks like:


let Y = lambda y . (lambda x . y (x x)) (lambda x . y (x x))

If you look at it, the reason for calling it Y is because it's "shaped" like a Y. To show you that more clearly, sometimes we write lambda calculus using trees. Here's the tree for the Y combinator:

What makes the Y combinator special is that applying Y to itself creates itself - that it, (Y Y) = Y (Y Y). Let's take (Y Y) and work it through:

Y Y
Expand the first Y:
(lambda y . (lambda x . y (x x)) (lambda x . y (x x))) Y
Now, beta:
(lambda x . Y (x x)) (lambda x. Y (x x))
Alpha[x/z] the second lambda:
(lambda x . Y (x x)) (lambda z. Y (z z))
Beta:
Y ((lambda z. Y (z z)) (lambda z. Y (z z)))
Expand that Y in front and alpha[y/a][x/b]:
(lambda a . (lambda b . a (b b)) (lambda b . a (b b))) ((lambda z. Y (z z)) (lambda z. Y (z z)))
Beta:
(lambda b . ((lambda z. Y (z z)) (lambda z. Y (z z))) (b b)) (lambda b . ((lambda z. Y (z z)) (lambda z. Y (z z))) (b b))

Now, look carefully at that expression. That's (Y (Y Y)). [Remember from the above that (Y Y) = (lambda x . Y (x x)) (lambda x . Y (x x))] So Y Y = Y (Y Y) That's the magic of Y: it reproduces itself. (Y Y) = Y (Y Y) = Y (Y (Y Y)), forever.

So how do we use this crazy thing?

Well, let's take our first attempt up there, and try to play with it a bit. Let's give it a name, and try writing it with that name:


let fact = lambda n . IsZero n 1 (Mult n (fact (Pred n)))

Now - the trick is, "fact" is not an identifier defined inside of "fact". How do we let "fact" reference "fact"? Well, we can do a lambda abstraction to let us pass the "fact" function as a parameter; then if we can find a way to write "fact" so that we can pass it to itself as a parameter, we'll be ready to go. Let's call that metafact.


let metafact = lambda fact . (lambda n . IsZero n  1 (Mult n (fact (Pred n))))

Now, if we could apply metafact to itself, we'd have our factorial function. That is, fact n = (metafact metafact) n.

That's where Y comes in. It lets us create a bizzare structure where that function, above, will be copied every time we need to recurse. metafact (Y metafact) will do what we want. Expanded out, that's:


(lambda fact . (lambda n . IsZero n  1 (Mult n (fact (Pred n))))) (Y (lambda fact . (lambda n . IsZero n  1 (Mult n (fact (Pred n))))))

(Y metafact) is the parameter value of fact in the lambda; when we do beta on the function, if n is zero, then it just returns 1. If it's not zero, then we get the call to fact (Pred n). Fact betas to Y metafact. Which does that insane magic copying thing, giving us metafact (Y metafact) (Pred n).

Voila, recursion. Deeply twisted recursion.

I learned about the Y combinator back in my undergrad days, which would place it around 1989 - and I still find it rather mystifying. I do understand it now, but I can't imagine how on earth anyone ever figured it out!

If you're interested in this, then I highly recommend getting a copy of the book The Little Schemer. It's a wonderful little book - set up like a childrens book, where the front of each page is a question; and the back of each page is the answer. It's written in a delightfully playful style, it's very fun and engaging, and it will not only teach you to program in Scheme.

As an important side-note there are actually a couple of different versions of the Y combinator. There are different ways of evaluating lambda calculus: given an expression like:
(lambda x y . x * y) 3 ((lambda z. z * z) 4)
we can do it in two different orders: we can first do the beta on "(lambda x y . x * y),which would give us:


3 * ((lambda z . z * z) 4)

Or, we could beta ((lambda z . z * z) 4) first:


(lambda x y . x * y) 3 (4 * 4)

In this case, the two orders end up with the same result; but that's not always the case.
The first order is what we call lazy evaluation: we don't evaluate the parameters to a function until we need to use them. The second is called eager evaluation : we always evaluate parameters before the functions that they're passed to. (In real programming languages, Lisp, Scheme, and ML are lambda-calculus based languages that use eager evaluation; Haskell and Miranda are lambda calculus based languages that use lazy evaluation.) The Y combinator I described above is the Y for lazy evaluation. If we used eager evaluation, then Y combinator above wouldn't work - in fact, it would copy Ys forever.

Political Bloviators and Bad Economics

2006-05-17T14:18:00.000-04:00

As the republicans' political fortunes gradually decline, they are naturally going on the warpath to try to discredit any voices speaking against their policies. In particular, there's been a lot of hysteria from some conservative gasbags terrified that the tax cuts handed to the wealthiest Americans might not be made permanent.

Any honest analysis of economic data during Bushes time in office is extremely clear: the republicans have dramatically decreased revenues (by 297 billion in 2004, the most recent year for which I could find complete figures), while dramatically increasing spending (31.5% increase between 2001 and 2004).

Of course, the incredibly simple arithmetic of a balanced budget is apparently beyond political bloviators.

Here's how a balanced budget is supposed to work:
Revenue - Spending = 0

Now, what happens if we increase spending and decrease revenue?
Revenue - Spending < 0

But that doesn't stop our conservative geniuses, like John McIntyre of "Real Clear Politics":

The Washington Post's Sebastian Mallaby is on a crusade to discredit pro-growth or supply-side economic policies. Today's column titled "The Return of Voodoo Economics" makes one wonder about what he doesn't like about 4% growth, under 5% unemployment, housing and the stock market higher, wealth being created and tax revenues at all time highs. I guess he pines for the pre-Voodoo Economics days of the 1970's when the highest marginal tax rate was 70% and the country had anemic growth, high unemployment and a Dow languishing below 1,000.

What gives Mallaby the right to think that he is a "serious" person when it comes to economic policy, but President Bush, Vice President Cheney, Majority Leader Frist and Finance Chairmen Grassley are not? Is Mallaby really that arrogant? Did it ever occur to Sebastian that maybe he is letting his ideological views get in the way of an honest appraisal of the facts?

Why is it so hard to explain the concept to many "intellectuals" that the idea is to grow the pie as big as possible, and that taking a smaller percentage of a bigger pie can yield more than a higher percentage of a smaller pie? Mallaby can quote all the economists and studies he wants to justify his attack on the economic wisdom of lower tax rates.

I'll just look at what happens in the real world.

Yeah, you see, you can quote all the studies and economic analyses you want - the fact that "Revenue - Spending < 0" isn't a problem in McIntyre's world. In McIntyre's world, cutting revenue increases revenue.

Sorry Johnny-boy, that's not how things work. Spending more money than you have is going to be a problem, sooner or later. You can't borrow money forever. And borrowing money so that you can hand it over to the wealthiest people in your society, well, that's not particularly what I calla brilliant idea. (And in the interests of full disclosure, my wife and I are quite definitely in the range where we are benefiting from those tax cuts. If they expire, it will cost us rather a lot of money.)

Growth produces wealth, which leads to higher tax revenues and a more prosperous nation. Less growth produces less wealth and in turn lowers tax revenues. High tax rates retard economic growth; low tax rates encourage more growth. It really isn't that complicated.

You see, dogma overcomes math. The simple and undeniable fact that the Bush tax cuts have decreased revenue - a fact that not even the Bush administration denies - that's just the babblins of a bunch of egg-head intellectuals. "Reality" is that lowering taxes increases revenues.

Booleans and Choice in Lambda Calculus

2006-05-16T17:00:00.000-04:00

Now that we have numbers in our Lambda calculus, there are only two things missing before we can express arbitrary computations: a way of expressing choice, and a way of expressing repetition. In this post, I'll talk about booleans and choice; and then next post I'll explain repetition and recursion.

We'd like to be able to write choices as if/then/else expressions, like we have in most programming languages. Following the basic pattern of the church numerals, where a number is expressed as a function that adds itself to another number, we'll express true and false values as functions that perform an if-then-else operation on their parameters:


let TRUE = lambda x y . x
let FALSE = lambda x y . y

So, now we can write an "if" function, whose first parameter is a condition expression, second parameter is the expression to evaluate if the condition was true, and third parameter is the expression to evaluate if the condition is false.


let IfThenElse = lambda cond true_expr false_expr . cond true_expr false_expr

For the boolean values to be useful, we also need to be able to do the usual logical operations:


let BoolAnd = lambda x y .x y FALSE
let BoolOr = lambda x y. x TRUE y
let BoolNot = lambda x . x FALSE TRUE

Now, let's just walk through those a bit. Let's first takea look at BoolAnd:

BoolAnd TRUE FALSE
Expand the TRUE and FALSE definitions: BoolAnd (lambda x y . x) (lambda x y . y)
Alpha the true and false: BoolAnd (lambda xt yt . xt) (lambda xf yf . yf)
Now, expand BoolAnd: (lambda x y. x y FALSE) (lambda xt yt . xt) (lambda xf yf . yf)
And beta: (lambda xt yt.xt) (lambda xf yf. yf) FALSE
Beta again: (lambda xf yf . yf)

And we have the result: BoolAnd TRUE FALSE = FALSE. Now let's look at "BoolAnd FALSE TRUE":
BoolAnd (lambda x y . y) (lambda x y .x)
Alpha: BoolAnd (lambda xf yf . yf) (lambda xt yt . xt)
Expand BoolAnd: (lambda x y .x y FALSE) (lambda xf yf . yf) (lambda xt yt . xt)
Beta: (lambda xf yf . yf) (lambda xt yt . xt) FALSE
Beta again: FALSE
So BoolAnd FALSE TRUE = FALSE

Finally, BoolAnd TRUE TRUE:
Expand the two trues: BoolAnd (lambda x y . x) (lambda x y . x)
Alpha: BoolAnd (lambda xa ya . xa) (lambda xb yb . xb)
Expand BoolAnd: (lambda x y . x y FALSE) (lambda xa ya . xa) (lambda xb yb . xb)
Beta: (lambda xa ya . xa) (lambda xb yb . xb) FALSE
Beta: (lambda xb yb .xb)
So BoolAnd TRUE TRUE = TRUE

Phony Statistics and Nauseating Metaphors

2006-05-15T20:31:00.000-04:00

Not exactly on topic, but not entirely off; my old buddy Vox Day is spouting again.

As usual, he spouts some a lot of foul nonsense, but this is particularly over the top. Two quotes from the miserable walking shitbag:

Dear Jorge plans to address the nation tonight, a speech wherein he will almost surely attempt to deceive citizens into believing that he does not wish the mass migration from Mexico to continue unabated. He will likely offer some negligible resources for law enforcement and border security – resources which will never materialize – in return for an amnesty program that will grant American citizenship to the Mexican nationals who have helped lower America's wage rates by 16 percent over the last 32 years.

Nice statistic there, totally unsupported (and unsupportable) by facts. But hey, what's a fake number better for than setting up a good old fashioned bit of vicious scapegoating:

And he will be lying, again, just as he lied when he said: "Massive deportation of the people here is unrealistic – it's just not going to work."

Not only will it work, but one can easily estimate how long it would take. If it took the Germans less than four years to rid themselves of 6 million Jews, many of whom spoke German and were fully integrated into German society, it couldn't possibly take more than eight years to deport 12 million illegal aliens, many of whom don't speak English and are not integrated into American society.

There just aren't words for this... It makes me so angry I can barely type. My relatives were part of that six million that the Germans "got rid of". I know the names of members of my family who were killed. And this shithead is using them as part of a gag-line about what to do about illegal immigrants, as if mass murder of innocent people was/is no big deal.

The Genius of Alonzo Church: Numbers in Lambda Calculus

2006-05-15T19:37:00.000-04:00

So, now, time to move on to doing interesting stuff with lambda calculus. To start with, for convenience, I'll introduce a bit of syntactic sugar to let us name functions. This will make things easier to read as we get to complicated stuff.

To introduce a "global" function (that is a function that we'll use throughout our lambda calculus introduction without including its declaration in every expression), we'll use a "let" expression:


let square  = lambda x . x^2

This declares a function named "square", whose definition is lambda x . x^2. If we had an expression "square 4", the "let" above means that it would effectively be treated as if the expression were:

(lambda square . square 4)(lambda x . x^2)

In some of the examples, I used numbers and arithmetic operations. But numbers don't really exist in lambda calculus; all we really have are functions! So we need to invent some way of creating numbers using functions. Fortunately, Alonzo Church, the genius who invented the lambda calculus worked out how to do that. His version of numbers-as-functions are called Church Numerals.

In Church numerals, all numbers are functions with two parameters:

Zero is "lambda s z . z".
One is "lambda s z . s z".
Two is "lambda s z . s (s z)".
For any number "n", it's Church numeral is a function which applies its first parameter to its second parameter "n" times.

A good way of understanding this is to think of "z" as being a a name for a zero-value, and "s"as a name for a successor function. So zero is a function which just returns the "0" value; one is a function which applies the successor function once to zero; two is a function which applies successor to the successor of zero, etc.

Now - watch this; if we want to do addition, x + y, we need to write a function with four parameters; the two numbers to add; and the "s" and "z" values we want in the resulting number:

let add = lambda s z x y .  x s (y s z)

Let's curry that, to separate the two things that are going on. First, it's taking two parameters which are the two values we need to add; second, it needs to normalize things so that the two values being added end up sharing the same binding of the zero and successor values.


let add = lambda x y. (lambda s z . (x s (y s z)))

Look at that for a moment; what that says is, to add x and y: create the church numeral "y" using the parameters "s" and "z". Then apply x to the church numeral y, using the new church numeral "y" defined in "s" and "z". That is: a number is a function which adds itself to another number.

Let's look a tad closer, and run through the evaluation of 2 + 3:

add (lambda s z . s (s z)) (lambda s z . s (s (s z))) news newz

To make things easier, let's alpha 2 and 3, so that "2" uses "s2" and "z2", and 3 uses "s3" and "z3";

add (lambda s2 z2 . s2 (s2 z2)) (lambda s3 z3 . s3 (s3 (s3 z3)))

Now, let's do replace "add" with its definition:


(lambda x y .(lambda s z. (x s y s z))) (lambda s2 z2 . s2 (s2 z2)) (lambda s3 z3 . s3 (s3 (s3 z3)))

Now, let's do a beta on add:


lambda s z . (lambda s2 z2 . s2 (s2 z2)) s (lambda s3 z3 . s3 (s3 (s3 z3)) s z)

And now let's beta the church numberal for three. This basically just "normalizes" three: it replaces the successor and zero function in the definition of three with the successor and zero functions from the parameters to add.


lambda s z . (lambda s2 z2 . s2 (s2 z2)) s  (s (s (s z)))

Now.. Here comes the really neat part. Beta again, this time on the lambda for two. Look at what we're going to be doing here: two is a function which takes two parameters: a successor function, and zero function. To add two and three, we're using the successor function from add function; and we're using the result of evaluating three as the value of the zero!:


lambda s z . s (s (s (s (s z))))

And we have our result: the church numeral for five!

My Favorite Calculus: Lambda (part 1)

2006-05-14T19:36:00.000-04:00

(In the original version of this post, I tried using a javascript tool for generating MathML. It appears to not work very well; several browsers failed to render it correctly, and it doesn't work in an RSS feed. I've gone back and re-written everything in simple text format.)

In computer science, especially in the field of programming languages, we tend to use one particular calculus a lot: the Lambda calculus. Lambda calculus is also extensively used by logicians studying the nature of computation and the structure of discrete mathematics. Lambda calculus is great for a lot of reasons, among them:

It's very simple.
It's Turing complete.
It's easy to read and write.
It's semantics are strong enough that we can do reasoning from it.
It's got a good solid model.
It's easy to create variants to explore the properties of various alternative ways of structuring computations or semantics.

The ease of reading and writing lambda calculus is a big deal. It's led to the development of a lot of extremely good programming languages based, to one degree or another, on the lambda calculus: Lisp, ML, and Haskell are very strongly lambda calculus based.

The lambda calculus is based on the concept of functions. In the pure lambda calculus, everything is a function; there are no values at all except for functions. But we can build up anything we need using functions. Remember back in the early days of this blog, I talked a bit about how to build mathematics? We can build the entire structure of mathematics from nothing but lambda calculus.

So, enough lead-in. Let's dive in a look at LC. Remember that for a calculus, you need to define two things: the syntax, which describes how valid expressions can be written in the calculus; and a set of rules that allow you to symbolically manipulate the expressions.

Lambda Calculus Syntax

The lambda calculus has exactly three kinds of expressions:

(1) Function definition: a function in lambda calculus is an expression, written:
lambda x . body
which means "a function with one parameter named X, which returns the result of evaluating the body". We say that the lambda expression binds the parameter.
(2) Identifier reference: an identifier reference is a name which matches the name of a parameter defined in a function expression enclosing the reference.
(3) Function application: applying a function is written by putting the function value in front of its parameter, as in "(lambda x . plus x x) y".

Currying

There's a trick that we play in lambda calculus: if you look at the definition above, you'll notice that a function (lambda expression) only takes one parameter. That seems like a very big constraint - how can you even implement addition with only one parameter?

It turns out to be no problem, because of the fact that functions are values. So instead of writing a two parameter function, you can write a one parameter function that returns a one parameter function - in the end, it's effectively the same thing. It's called currying, after the great logician Haskell Curry.

For example, suppose we wanted to write a function to add x and y. We'd like to write something like: lambda x y . plus x y. The way we do that with one-parameter functions is: we write one function with one parameter, which returns another function in one parameter. Adding x plus y becomes writing a one-parameter function with parameter x, which returns another one parameter function which adds x to its parameter:

lambda x.(lambda y. plus x y)

Now that we know that adding multiple parameter functions doesn't really add anything but a bit of simplified syntax, we'll go ahead and use them when it's convenient.

Free vs Bound Identifiers

One important syntactic issue that I haven't mentioned yet is closure or complete binding. For a lambda calculus expression to be evaluated, it cannot reference any identifiers that are not bound. An identifier is bound if it a parameter in an enclosing lambda expression; if an identifier is not bound in any enclosing context, then it is called a free variable.

lambda x . plus x y: in this expression, "y" and "plus" are free, because they're not the parameter of any enclosing lambda expression; x is bound because it's a parameter of the function definition enclosing the expression "plus x y" where it's referenced.
lambda x y.y x: in this expression both x and y are bound, because they are parameters of the function definition.
lambda y . (lambda x . plus x y): In the inner lambda, "lambda x . plus x y", y and plus are free and x is bound. In the full expression, both x and y are bound: x is bound by the inner lambda, and y is bound by the other lambda. "plus" is still free.

We'll often use "free(x)" to mean the set of identifiers that are free in the expression "x".

A lambda calculus expression is completely valid only when all of its variables are bound. But when we look at smaller subexpressions of a complex expression, taken out of context, they can have free variables - and making sure that the variables that are free in subexpressions are treated right is very important.

Lambda Calculus Evaluation Rules

There are only two real rules in lambda calculus; they're called alpha and beta. Alpha is also called "conversion", and beta is also called "reduction".

Alpha Conversion

alpha is a renaming operation; basically it says that the names of variables are unimportant: given any expression in lambda calculus, we can change the name of the parameter to a function as long as we change all free references to it inside the body.

So - for instance, if we had an expression like:
lambda x . if (= x 0) then 1 else x^2

We can do alpha changing X to Y (written "alpha[x/y]" and get):

lambda y . if (= y 0) then 1 else y^2

Doing alpha does not change the meaning of the expression in any way. But as we'll see later, it's important because it gives us a way of doing things like recursion.

Beta Reduction

Beta reduction is where things get interesting: this single rule is all that's needed to make the lambda calculus capable of performing any computation that can be done by a machine.

Beta basically says that if you have a function application, you can replace it with a copy of the body of the function with references to the parameter identifiers replaced by references to the parameter value in the application. That sounds confusing, but it's actually pretty easy when you see it in action.

Suppose we have the application expression: "(lambda x . x + 1) 3". What beta says is that we can replace the application by taking the body of the function (which is "x + 1"); and replacing references to the parameter "x" by the value "3"; so the result of the beta reduction is "3 + 1".

A slightly more complicated example is the expression:
lambda y . (lambda x . x + y)) q
It's an interesting expression, because it's a lambda expression that when applied, results in another lambda expression: that is, it's a function that creates functions. When we do beta reduction in this, we're replacing all references to the parameter "y" with the identifier "q"; so, the result is "lambda x. x+q".

One more example, just for the sake of being annoying:
"(lambda x y. x y) (lambda z . z * z) 3". That's a function that takes two parameters, and applies the first one to the second one. When we evaluate that, we replace the parameter "x" in the body of the first function with "lambda z . z * z"; and we replace the parameter "y" with "3", getting: "(lambda z . z * z) 3". And we can perform beta on that, getting "3 * 3".

Written formally, beta says:


lambda x . B e = B[x := e] if free(e) subset free(B[x := e]

That condition on the end, "if free(e) subset free(B[x := e]" is why we need alpha: we can only do beta reduction if doing it doesn't create any collisions between bound identifiers and free identifiers: if the identifier "z" is free in "e", then we need to be sure that the beta-reduction doesn't make "z" become bound. If there is a name collision between a variable that is bound in "B" and a variable that is free in "e", then we need to use alpha to change the identifier names so that they're different.

As usual, an example will make that clearer: Suppose we have a expression defining a function, "lambda z . lambda x . x+z)". Now, suppose we want to apply it:

(lambda z . (lambda x . x + z)) (x + 2)

In the parameter "(x + 2)", x is free. Now, suppose we break the rule and go ahead and do beta. We'd get: lambda x . x + x + 2

The variable that was free in "x + 2" is now bound. Now suppose we apply that function:
lambda x . x + x + 2) 3

By beta, we'd get "3 + 3 + 2".

What if we did alpha the way we were supposed to?

by alpha[x/y]: lambda z . (lambda y . y+z)) (x + 2)
by beta: lambda y . y + x + 2) 3
by beta again: 3 + x + 2.

"3+x+2" and "3+3+2" are very different results!

And that's pretty much it. There's another rule you can optionally add called Eta-reduction, but we'll skip that for now. What I've described here is Turing complete - a full effective computation system. To make it useful, and see how this can be used to do real stuff, we need to define a bunch of basic functions that allow us to do math, condition tests, recursion, etc. I'll talk about those in my next post.

We also haven't defined a model for lambda-calculus yet. (I discussed models here and here.) That's actually quite an important thing! LC was played with by logicians for several years before they were able to come up with a complete model for it, and it was a matter of great concern that although LC looked correct, the early attempts to define a model for it were failures. After all, remember that if there isn't a valid model, that means that the results of the system are meaningless!

A minsky machine to play with

2006-05-14T17:23:00.000-04:00

Just for fun, I whipped together a really simple implementation of Minsky machines in Scheme. You can grab it at my .Mac site. It's written in generic scheme, so it should work on any interpreter you want.

I'm a huge fan of two scheme interpreters, and I've tested this code on both, so I'm sure it'll work with them. But it should work on any Scheme interpreter. The two I recommend are:

DrScheme: very powerful scheme system with wonderful tool support.
Gauche: a scheme system for script-type programming. Really a thoroughly fantastic, thorough implementation.

(No insult intended towards other scheme implementations; these just happen to be the two that I like using. )

Test post

2006-05-13T20:20:00.000-04:00

Please ignore this; I'm doing some experiments with the blog template, and I need a post that I can edit to see if it's working.

`\lambda x . x + 1`

`(\lambda x . plus\ x\ x)\ y`

`\lambda x . B e \equiv B[x := e] if text{free}(e) \subset text{free}(B[x := e])`

Truly, truly horrible math pun

2006-05-12T19:39:00.000-04:00

What's purple and makes honey and commutes?

More Gematria Gibberish

2006-05-12T17:39:00.000-04:00

After talking about the gematria gibberish that was sent to me in email earlier this week, I came accross the following link while looking at an article about Autism rates on Kevin Leitch's blog. In the course of discussing the top referrers to a new autism=mercury site, he mentioned David Icke. Now, Icke is a total loony, and a fun one at that. He believes that the rulers of every country are actually lizards in disguise. Well, from Icke's site, I found a link to some of the goofiest gematria crap I've seen in a long time. I don't think this needs any commentary at all, so just follow the link and enjoy!

The Minsky Machine

2006-05-12T11:48:00.000-04:00

I've said before that all computing systems are ultimately equivalent. This is something known as the Church-Turing thesis. It's interesting to look at one or two machines other than the Turing machine, just to get some idea of why we believe that, and what other computers might look like.

There's a really fun computing machine designed by Marvin Minsky, an incredibly smart and prolific computer scientist. He just called them "program machines" when he first proposed them; most of us call them "Minsky Machines". I really like Minsky machines; I find their programs much easier to read and write than Turing machine programs, and their behavior is closer to real computers.

The minsky machine is astoundingly simple: even simpler than the turing machine. A minsky machine consists of:

A finite set of registers, A, B, C, ..., each of which contains a natural number.
A list of numbered instructions.

There are only three instructions in a minsky machine:

Increment: increment takes two parameters: a register, and an instruction number. It increments the value stored in the specified register, and then jumps to the instruction at the number.
Decrement: decrement takes three parameters: a register, and two instruction numbers. If the value in the register is 0, it jumps to the instruction at the first number; if the value in the register is greater than zero, it decrements it, and jumps to the instruction at the second number.
Halt.

You start with the instruction at position 0, and keep going until you hit a Halt.

Here's a subtraction program for a minsky machine with two registers. It takes two numbers in registers A and B, and leaves the result in A. If it halts with anything but 0 in B, then it's an error.


1: Decrement(B, 4, 2)
2: Decrement(A, 3, 1)
3: Incr(B,4)
4: Halt

First, it decrements the value in register B; if B is zero, then the subtraction is done, so it jumps to halt. If B is greater than 0, then it subtracts one from B, and then tries to subtract one from A. If A is already zero, then it adds one to B (to be sure that B != 0) and halts. If A isn't zero, then it decrements it, and goes back to the beginning.

Now, here's a question: is this really equivalent to a turing machine? Intuitively, you can problably get a sense that this is a complete effective computing system. But how do we prove it?

Well, we know that a two-stack push-down automaton is completely equivalent to a turing machine: the two stacks can simulate the parts of the tape on either side of the head. And we know that if something can be done with a turing machine, it can be done with a binary (two symbol) turing machine. So - we need to show that we can simulate a two-stack binary push-down automaton using a minsky machine. A pushdown automaton is really just a FSM with two stacks.

Since we already showed we can implement fully general natural number subtraction with a Minsky machine, we know that we can implement an FSM: subtraction is strictly harder than anything an FSM can do - so if our machine can implement a general subtraction, it can implement an FSM. So what we need to do is show that we can implement the stacks.

And that's easy. Here's how you implement a stack with two registers: one register holds a binary number. That binary number is the stack. To push a value on the stack, you multiply by two, and add the value. To pop the value on top of the stack, you take divide by two; the result of the division is the popped stack, and the remainder is the value that was on top. So you've got the stack data in one register. You need a second register to use to implement the multiplications and divisions.

So, if you've got four registers, then you've got two stacks. Poof. You've got a turing machine.

Going the other direction, it should be pretty easy to see how to implement a Minsky machine with a turing machine. To make things easy, we can use a multi-tape turing machine (since we know that that's no more powerful than a one-tape). Each register is one tape, containing its value in unary; and one tape contains the program.

On Applying Sampled Statistics

2006-05-12T10:38:00.000-04:00

After my post last week about probabilities and the Duke rape case, there's been a fairly heated discussion in the comments about whether/how it's appropriate to apply statistics to compute probabilities relating to a particular selected instance. I decided it was worth taking the time to post a little bit about what statistics mean, and what that implies about how they can be applied.

Statistical analysis is primarily about measurements of groups. Broadly speaking, there are two kinds of statistics: full-population statistics, and sampled statistics.

Full population statistics are less common. In full population statistics, you have data about every member of the group being analyzed, and you're trying to analyze the properties of that group. An example of this is many types of manufacturing: for example, if you're intel, and you're manufacturing chips, after each manufacturing run, you test every chip you produced. And you gather a lot of information about how many have no detectable defects; and of the defective units, how many had each kind of defect.

Sampled statistics are the more common ones. They're what you use when you do not have data about every member of the group. What you have is a selected subgroup, called your sample, which is (ideally) representative of the group as a whole. By performing measurements on the sample, if the sample is truly representative, then probabilistic descriptions of the measurements of the sample should be very close to what you would find by doing a total measurement of all members of the group. To continue with the manufacturing example: if you were building processors for use in satellites, you would want to know how much radiation exposure the processors could survive before they failed. So you might take a sample of the units, and expose them to increasing levels of radiation, seeing the spectrum of failure points, in order to allow you to make a reasonable guess at how much shielding you would need to achieve a specified level of reliability.

The purpose of sampled statistics is that if the sample is representative, then measuring the sample will allow you to make probabilistic statements about the population the sample was drawn from. That's a critical, key point: statistics are about groups, and sampled statistics are carefully done in a way that allows you to reason from samples to populations. (Put more formally, wikipedia defines it as "Sampling is that part of statistical practice concerned with the selection of individual observations intended to yield some knowledge about a population of concern, especially for the purposes of statistical inference. In particular, results from probability theory and statistical theory are employed to guide practice.")

Because of the fact that a representative sample should show roughly the same characteristics as the population as a whole, then if you take a second, independent representative sample of the population, then the statistics drawn from the first sample should, with high probability, apply to the second sample. So - again with the manufacturing example: Supposed I've produced 20,000 processors for satellites. From those, I've taken a testing sample of 1000 units, and exposed them to various level of radiation until they failed, and generated the mean failure level, and the standard deviation of the amount of radiation that caused them to fail. Now, I want to deliver 1000 units to a customer. If my testing sample was representative, and the set of 1000 units that I deliver to my customer are equally representative, then the data I generated from my radiation exposure tests should describe the failure properties of the set of units I delivered.

But the key there is the idea of the representative sample. A representative sample should have the roughly the same distribution of properties as the population. If the sample is not representative, then we cannot reason from or about it.

Now, the issue that came up in comments is: can we use statistics to reason about a specific member of a population? The answer is always no. Because a specific, individual member of a population can never be a representative sample. And you can only reason to and from representative samples of the population.

Friday Random Ten, May 12th

2006-05-12T08:15:00.000-04:00

Solas, "The Hanover Reel/John James Reel/The Copperplate". Great traditional Irish band.
New Grange, "Under the Hood". New Grange is a sort of bluegrass superstar band made up of performers from Compass Records: Allison Brown, Tim O'Brien, Mike Marshall, Darol Anger.
Shirim, "Moldavian Tantz". Amazing Klezmer.
The Ligeti Project, "Hamburg Concerto for Solo Horn". Modern classical music that I bought based on a recommendation from the FRT two weeks ago. I haven't listened to it enough to have a firm opinion yet.
Mussorgsky, "Promenade" from "Pictures at an Exhibition". The original piano version. Very sparse compared to the orchestral one we usually here. Very nice.
Happy Rhodes, "Out Like a Lamb". Happy Rhodes is a relatively obscure singer in roughly the same vein as Kate Bush. Excellent songwriter, beautiful voice.
Steve Hackett, "Rise Again". Wonderful stuff from the guitarist from the glory days of Genesis.
Moxy Fruvous, "Michigan Militia". Hysterical.
Yes, "Changes"
Hugh Blumenfeld, "Saxton's River".

Busy Beavers

2006-05-11T14:41:00.000-04:00

After spending all this time talking about the different kinds of computing machines and what they can do, I thought it would be fun to talk a little bit about what they can't do.

Back in the early days of this blog, I talked about two things that no computing machine can do:

the halting problem: determining whether running a given program on a particular input will eventually halt;
minimal complexity: determining whether or not a particular program is the smallest one that can generate a particular result.

There's one really fun non-computable, which various nutty people like me still play with to see who can find the best one. It's called the busy beaver problem. There are actually real competitions to see who can build the best busy beaver program.

Here's the question that the simplest version of the busy beaver problem wants to answer: Given a binary turing machine (that is a machine whose tape can have only the characters 0 and 1) with N states, what is the longest string of 1s that can be generated by a halting program?

Based on experimentation, our best guess is for a five-state machine, the answer is: 4098 ones, taking 47,176,870 steps. For a six state machine, it's something on the order of 10^1000 1s.

From wikipedia, here's the state transition function for a six-state busy beaver that will write 1x10^865 ones:

State,Input	Write-Symbol	Next-State	Direction
0,0	1	1	+
0,1	0	5	-
1,0	0	2	+
1,1	0	3	+
2,0	1	3	-
2,1	1	4	+
3,0	0	4	-
3,1	0	3	-
4,0	0	0	+
4,1	1	2	+
5,0	1	0	-
5,1	1	HALT	HALT

(In the original version of this posting, the turing program above had several errors due to an error translating from the wikipedia format to my format.)

I'm not going to go through the proof; this is basically just a fairly typical Godel-esque problem: to compute this, you need to "meta-compute" - that is, to use computation to reason about computation; and any time you reach meta-problems like that, you hit the Godel barrier, and things become uncomputable. This is what we call a Turing complete problem: if it were possible to solve the halting problem, we could solve this; if it were possible to solve this, we could solve the halting problem.

(This is actually a secondary use of the term "Turing complete", and it's definitely awkward, but I'm not aware of a better term. Turing complete is also used to describe programming languages or computing machines to mean that the language/machine can both implement a turing machine, and be implemented by a Turing machine.)

There are numerous variations on the busy beaver problem: versions for turing machines with more symbols on the input tape; versions where the goal is to run for the most execution steps before halting; versions for other computing systems; etc.

(One of the questions that people often come up seeing the busy beaver is: if all computing devices are equivalent, then why would the answer be different for a computing device other than a turing machine? The answer is that the busy beaver problem includes the basic properties of the Turing machine in it - so even if you used a different computing machine to compute the result of a given busy beaver program, the program for that other machine would need to encode the properties of the Turing machine that the BB program was written for.)

The Crystallized Skeptics Circle

2006-05-11T08:03:00.000-04:00

A very clever Skeptics Circle is up at The Second Sight. Go see what the magic of crystals can do for skeptical thinking.

Physics in an Electric Universe

2006-05-10T17:54:00.000-04:00

As I mentioned in my post earlier, some of the best examples of bad math are really examples of no math. One of my favorite examples of this kind of bogosity is the Electric Universe. The Electric Universe is fun, both because of the utter bizzareness of its ideas, and the fact that it's not just a single crackpot spewing it, but rather a whole active community of crackpots working together. So there are multiple different threads of it - a veritable cornucipia of of lunacy!

There are two main threads to the EU gibberish: the mythology, and the physics. Let's take a look at the physics. Here's one version of the fundamental physics of the electric universe:

The Electric Universe takes a simplifying leap by unifying the nuclear forces, magnetism and gravity as manifestations of a near instantaneous electrostatic force. Instead of being "spooked" by the concept of action-at-a-distance, like most physicists this century, the Electric Universe accepts it as an observational fact. Anyone who has tried to force two like poles of magnets together has demonstrated action-at-a-distance. "Electromagnetic" radiation is then simply the result of an oscillating electrostatic force.

At the level of the atom, the Electric Universe model takes a lead from the work of Ralph Sansbury, an independent New York researcher. Foremost is the simple recognition of the basic electrical nature of matter and the primacy of the electrostatic force** in matter interactions. It also rests upon the simple assumption that the proton, neutron and electron are composed of smaller charged particles, orbiting each other in a classical sense in stable, resonant orbits. That is, the energy exchanged between those sub-particles in elastic deformation during each orbit sums to zero. Being charged, the sub-particles interact via the electrostatic force. A simple calculation shows that the sub-particles that form an electron must travel at a speed far in excess of the speed of light - some 2.5 million light-years per second, or from here to the far side of the Andromeda galaxy in one second! So the electrostatic force must act at a speed which is almost infinite on our scale for the electron to be stable. It is the stable orbital resonances of these sub-particles, both within and between particles that give rise to the phenomena of protons, neutrons, electrons and atoms. Other denizens of the particle "zoo" are merely transient resonant states of the same charged sub-particles. The so-called "creation" of matter from energetic photons is an illusion in which pre-existing matter is reorganized into new resonant states that give the impression that a particle has suddenly materialized. Antimatter is a misnomer since it too is formed from the same sub-particles as "normal" matter except that the total charge is mirrored. Matter cannot be created or annihilated.

Now, how's that for a wacky idea?

The thing to note is that it alludes to some math, but nowhere can you actually find a full, detailed presentation of it. In fact, you can go through all of the books, conferences, papers, websites, and pamphlets from the EU folks, and you'll never see so much as one equation, or one actual mathematically defined relationship. They make arguments like "the simple assumption that the proton, neutron, and electron are composed of smaller charged particles, orbiting each other in a classical sense in stable, resonant orbits", completely ignoring the fact that such a claim is (a) meaningless, and (b) unsupportable.

Then they try to build on the first meaningless claim, again alluding to math which is never, ever shown: "A simple calculation shows that the sub-particules... must travel at a speed far in excess of the speed of light...". It's a simple calculation, but we will never show it to you, no matter how many times you ask!

I also really, really love the bit about how "spooky action at a distance" is obviously real, because you can see it when you play with magnets! It's obvious that that's an instantaneously transmitted force! All of modern physics is wrong, because I can feel it with my hands!

Quantum Theory

For the first time the highly successful quantum theory gains a physical explanation in terms of resonant motion of charged particles, mediated by a near-instantaneous electrostatic force. A quantum electron orbit is one in which the exchange of energy between all of the sub-particles in the nucleus of an atom and those in an orbiting electron, sum to zero over the orbit. Exchange of energy takes the form of distortion of a particle to form an electrostatic dipole or a move to a new resonant orbit.

Yep, the electric universe guys can explain quantum physics in a way that's intuitively easy to understand! Of course, the fact that quantum physics has a spectacular amount of complex mathematics supporting it, which make precise predictions, none of which are explained by the EU handwaving is unimportant. Because it just makes sense! (Now would be a good time to quote Feinman: "anyone who claims to understand quantum theory is either lying or crazy")

Relativity Theory Einstein's Special Theory was designed to define simultaneity in a universe where the fastest force or signal was restricted to the measured speed of detection of light from a distant source. With an electrostatic force of near-infinite speed acting between the sub-particles of all matter, relativity theory reduces to classical physics. This leaves open the question of what we are measuring when we determine the speed of light. The speed of light in galactic terms is exceedingly slow, requiring about 150,000 years to cross our galaxy. However, the astronomer Halton Arp has shown that the redshifts of entire galaxies are quantized which requires some form of near instantaneous, galaxy-wide communication at the sub-atomic level. There are now several reported experiments that demonstrate faster than light effects. With the Special Theory gone, and the universe in communication with its parts effectively in real-time, there can be no time travel and space and time are independent. Common sense has always suggested that this was so. Einstein's General Theory was devised to explain gravity. It attempts to discard the observed action-at-a-distance of gravity by proposing a counter-intuitive warping of space in the presence of massive objects. This unnecessary complication of space is then added to the current metaphysical concepts of what constitutes the mass of an object. But space must also "warp" at near infinite speed to produce the observed planetary orbits. Common sense, observation, and parsimony of hypotheses all suggest that the electrostatic model of gravity (see below) is superior. There is now experimental evidence from gravity measurements at the time of a total solar eclipse that supports the Electric Universe model and discounts the General Relativity model.

Yeah, Einstein had it all wrong. Quantized redshifts of galaxies means that all of the particles in the galaxy are communicating instantaneously! Relatavistic explanations of gravity are just garbage!

Einstein's famous mathematical expression E=mc2, equating energy and mass is known by almost everyone. However, most textbooks go on to use the word "matter" in place of "mass." But nowhere has it been shown that mass and matter are interchangeable. In fact, we are entirely ignorant of what constitutes the mass of an object. So it is inadmissible to imply that energy and matter are interchangeable. The ultimate expression of this idea led to the nonsense of the big bang. It seems simpler and more sensible to suggest that both nuclear and chemical energy is released or absorbed by the rearrangement of the resonant orbits of charged particles. It is then common sense to suggest that mass is the measured response of a system of charged particles to an external electrostatic force. The more massive an object, the more the electrostatic force contributes to the elastic deformation of its protons, neutrons and electrons, rather than their acceleration.

This paragraph is one of my favorite bits of crackpottery ever. It's all just "common sense" and "simple". Because the EU guys can't understand relativity and how it defines mass and energy, it must be junk. It's not clear and obvious, like the idea that mass is actually the "elastic deformation" of the orbital systems of sub-nuclear particles that make up matter.

Of course, we can't describe how that works mathematically. And we can't predict how things will behave. But that's no problem, because it's just common sense that it's right. Who needs all that equation nonsense when common sense will do?

This is the phenomenon seen in particle accelerators and conventionally attributed to relativistic effects. But relativity reduces to classical physics in a universe where the electrostatic force has near-infinite speed. The first question to be asked is - if it is that simple, why hasn't it been thought of long ago? The answer seems to lie in the propensity for mathematical theory to supersede common sense and observation. There is also a problem of language when mathematicians attempt to provide real meaning for their symbols.

And finally, the coup de grace of this essay: of course we don't waste our time on math. The reason that this obvious stuff was never noticed before was because all of those supposedly brilliant scientists were wasting their times on "the propensity for mathematical theory to supersede common sense"!

Now that my friends, is truly bad math.

No math is the worst math

2006-05-10T10:01:00.000-04:00

As I've said many times before, one of the easiest and most consistent ways to spot a crackpot is through math. I've talked about a lot of folks who've used bad math to support invalid theories. But bad math like what's used by people like Berlinski and Dembski is really the best case for crackpot theories. What you'll often find is something worse: no math.

The explanatory power of science isn't just the ability to put together explanations that appear to fit observed phenomena. It's the ability to very precisely predict or explain real phenomena. It's very easy to make a prediction when you don't need to be precise. I can very easily say "the theory of gravity is nonsense. Everything has a natural place where it belongs, and things always try to move towards the place they belong. So things fall to earth not because the earth is pulling on them with some invisible magical gravitational force, but because they belong on the earth." And I can make endless arguments for just why my "natural place" argument works better than gravity:

Flies wings don't produce any lift. But they don't fall to the ground when they're alive. Why doesn't "gravity" make them fall? Gravitationalists argue that they're so small that "brownian motion" in the air makes the aerodynamic principles of flight invalid for their size, but that's just handwaving to get around the fact that if gravity were true, they wouldn't be able to fly. Flies can fly because living flies belong in the air, it's their natural place.
If you fill a balloon with helium, it will rise. But if gravity were true, it couldn't rise, because the same amount of gravity would still be pulling it towards the ground. Gravitationalists argue that there's some magical "buoyant" force created by the air around it that pushes it up. But look around you - if the entire earth was pulling down on something, does air really seem substantial enough to overcome the pull of the entire earth? Of course not! The helium in the baloon belongs above the ground, and so it pulls the balloon up to where it belongs.
Why does water "find its own level"? Look at this picture:

Why does the water stop at the same level in both containers? If this gravity nonsense was true, then the bigger quantity of water in the cone-shaped container would push out the water in the smaller rectangular one - after all, there's more of it, so according to gravity, it's heavier. But it doesn't! Gravity doesn't explain that! It works because water's it's just the natural way that water works: it's natural state makes it flow so that it forms a smooth level.

You find things like this all over the place; some of the very best crackpots use arguments very much like this. The problem with this kind of explanation is that it's just handwaving. You can take any bit of evidence, and say that it fits the theory. You can't precisely tell what's going to happen in new, novel situations. You can't even precisely explain what's happening in known situations.

Explanatory power comes with mathematics. Gravity has been described to quite a high precision by Newton's law, and refined by Einstein. We can predict with astounding accuracy exactly what will happen in a gravitational interaction. We can explain with near-perfect accuracy why our solar system behaves the way it does, why things fall the way that do, etc - because the theory includes precisely detailed mathematics that allow us to not just handwave, but to speak and predict with precision.

Level 0, recursive and recursively enumerable languages

2006-05-08T20:11:00.000-04:00

Finally, time for level 0. This is going to be a short one, because I've already talked about a lot of it in other posts:

Level 0 grammars are absolutely unlimited. Anything can be on the left or the right hand side the grammar. Rules can expand and contract the string; terminals can be replaced, etc. The only real distinction between non-terminals and terminals in a level 0 grammar is that you haven't generated a sentence in the language until there are no non-terminals left.

Machines for level 0 are turing machines (or any equivalent).

The main interesting thing that happens at level 0 is that you can describe two very important families of languages (and thus of functions) in terms of level 0 machines:

The recursive languages
The recursively enumerable languages

The recursive languages are the set of languages where given a string, a computing machine will eventually stop and answer "Yes" or "No" to indicated whether or not the string is in the language. The functions corresponding to the languages are known as recursive or computable functions.

The recursively enumerable languages are the set of languages where given a string, a computing machine will eventually stop and say "Yes" if the string is in the language. But it might never stop and say no. And at any point in time, if it hasn't stopped yet, you don't know whether it's eventually going to stop and say "Yes". So you can't be certain that a given string isn't in a language.

In function-oriented terms, a recursive function is one computable by a machine that always halts. A recursively enumerable function is a possibly partial function where a machine that computes it will never halt for some values; until the machine halts, you can never be sure that it won't; so you can't ever be certain that the value of the function for a given input is undefined.

So why do we call them recursively enumerable? Because there's a recursive function that generates the strings in a RE language. It doesn't test to see if they're in the language; it just generates strings, and given enough time, any string that's in the language will eventually be emitted.

There are two different ways of thinking about the process of recursively enumerating things; the grammar oriented approach, and the function oriented approach. The grammar one is harder to formalize completely, but it's easier to understand in principle.

The grammar approach is: given a grammar G, which consists of productions g_1, g_2, ..., g_n:

For every length L from 1 to infinity:
1. Generate every possible permutation of rules g_i in G of length L.
2. Apply the sequence of rules one at a time, if possible. (If not, then give up on that sequence.)
3. If after applying the sequence of rules, the result is a string of terminals, print it out.

What makes it harder to really formalize this properly is that just generating the sequence of productions isn't enough - a given production can often be applied at more than one point in a string, and you need to make sure that you are exploring every possible application of each of the rule sequences.

The functional approach comes from recursive function theory. It's easier to write if I introduce a bit of formalism for it.

If we have a universal computing machine, we can treat it as a two parameter function: the first parameter is a program; and the second parameter is the input to the program. For some strange reason, it's traditional to call the function for the computing machine by the greek letter Phi written in script. I'll just write Phi. If the machine Phi is a turing machine of its equivalent, we call Phi an effective computing system.

For any effective computing system Phi, it's possible to list all of the possible programs for it - just take every possible program, and arrange them so that the shortest ones come first; and within programs of a given length, order them alphabetically. Once you've done this, you can assign a unique natural number to each program. This is called an effective numbering of the programs for Phi.

Once we've done this, we can define our function Phi for a computing device so that it's first parameter is an integer identifying a program according to the effective numbering.

So now, for instance, we can write Phi(3,7) to mean run program number 3 on Phi using 7 as the input.

Now, if Phi is a machine, we can define another function, PhiPrime, which takes three parameters, and returns either an integer, or a special value called bottom. The first two are, as in Phi, the effective program number and the input. The third is an integer. PhiPrime(x,y,z) runs program x on input y for z steps of Phi; if the program halts in "z" steps or less, then PhiPrime(x,y,z)=Phi(x,y); otherwise, PhiPrime(x,y,z)=bottom.

So - now, with all of that defined, we can finally describe how to enumerate the values for which a given program p will terminate.

For each natural number i > 0:
1. for each natural number j less than i:
  1. if PhiPrime(p,i-j,j) != bottom, print (i-j)

So - first we run p(0) for one step.
Then we run p(0) for two steps, and p(1) for one step.
Then we run p(0) for three steps, and p(1) for two steps, and p(2) for one step.
And so on.

Eventually, for any combination of x and y, PhiPrime(p,x,y) will get run - so if Phi(p,x) halts, eventually, we'll emit x. If Phi(p,x) doesn't halt, it will never get emitted. But since there's no particular ordering to how the values get emitted, we don't ever know for sure if Phi(p,x) doesn't halt. We can say for any y we select that PhiPrime(p,x,y) doesn't halt - but it's always possible that PhiPrime(p,x,y+1) might.

Context Sensitive Languages

2006-05-08T11:19:00.000-04:00

Last week, I started talking about computation and languages. I've already talked about level 3, the regular languages, and level 2, the context free languages. So, here we are at Chomsky level 1, the context sensitive languages.

Context sensitive languages are interesting because they are the closest formal approximation to what we can do with real, practical computers. They're also just fun, because they're capable enough to do all sorts of fascinating things, but simple enough the be reasonably easy to play with.

Representing Context Sensitive Languages

Context free languages can be represented using phrase-structure grammars, just like the other grammars we've discussed. The new expressive abilities of context sensitivity can be described in two very nearly equivalent ways. I prefer one of them for explaining why we call these things context sensitive; and I actually prefer the other for writing interesting grammars.

The first one is the classic context sensitive formulation: in productions, the left-hand side of the production can be any sequence of symbols, both terminals and non-terminals; on the right-hand side of the production, only one non-terminal can be replaced a sequence of symbols. So one non-terminal is being replaced in the production; the other symbols on the left-hand-side establish a fixed, unchangeable context in which the expansion is permitted to occur.

So, for example, if lowercase letters are non-terminals, and uppercase symbols are terminals, in a CSG I can write rules like:


x ::= ABxC
ABxC ::= ABCyC
AxYbC ::= ABYbC

But, I can't have rules like:


AxYbC ::= ABYQC  (replaced two-nonterminals)
AxYbC ::= BxYbC  (replaced a terminal)
AxYbC ::= AxYxx  (changed the context by altering the terminal after "b")

Context sensitive rules are also sometimes written in a slightly different format, which can be much clearer. This format leaves the basic production part looking the same as in the CFGs, but adds an "in" clause to specify the context in which the production can be used. So in this format, the productions above would be written:


x ::= ABxC     (Don't need to show any context)
x ::= Cy in ABxC
x ::= B in AxYbC

One of the advantages of this alternate way of writing context sensitive rules is that it prevents you from accidentally writing invalid rules: try to write one of the invalid examples above in this format - it doesn't work.

The other formulation of context sensitive grammars is simpler, but I find that it makes the "context sensitivity" aspect a little more difficult to see. The second formulation is nearly equivalent to the first; the only difference is that the CSG formulation above can be used to specify languages that include the empty string; this one can't. Aside from that, anything that can be written in CSG form above can be written in this form, and vice versa.

The second formulation is called non-contracting grammars (NCG). In a non-contracting grammar, the only restriction is that the left-hand-side of every grammar rule cannot be longer than the right hand side. So the side of the string being generated by production rules is monotonically increasing.

Here's a nice example of a NCG doing something that a CFG can't, and which illustrates why NCGs are easier to write than CSGs.


a ::= XYZ   (1)
a ::= XabZ   (2)
Zb ::= bZ    (3)
Yb ::= YY     (4)

Rules 1 and 2 basically set up the pattern to generate the matching numbers of Xs, Ys, and Zs; but it uses the non-terminal "b" instead of "Y" for all but the first "Y". Rule 3 does the re-ordering to move all the "Z"s to the end (note that we could not have this rule in a CSG). And finally, rule 4 converts the non-terminal "b"s to "Y"s. To see how it works, it helps to follow it through a few steps. So let's generate "XXXXYYYYZZZZ". We start with "a".

Rule 2(replace "a" by "XabZ") : a -> XabZ
Rule 2 again: XabZ -> XXabZbZ
Rule 3 (replace "Zb by bZ"): XXabZbZ -> XXabbZZ
Rule 2 again: XXabbZZ -> XXXabZbbZZ
Rule 3: XXXabZbbZZ -> XXXabbZbZZ
Rule 3: XXXabbZbZZ -> XXXabbbZZZ
Rule 1(replace "a" by "XYZ"): XXXabbbZZZ -> XXXXYZbbbZZZ
Rule 3: XXXXYZbbbZZZ -> XXXXYbZbbZZZ
Rule 3: XXXXYbZbbZZZ -> XXXXYbbZbZZZ
Rule 3: XXXXYbbZbZZZ -> XXXXYbbbZZZZ
Rule 4 (replace "Yb" by YY): XXXXYbbbZZZZ -> XXXXYYbbZZZZ
Rule 4 again: XXXXYYbbZZZZ -> XXXXYYYbZZZZ
Rule 4 one last time: XXXXYYYbZZZZ -> XXXXYYYbZZZZ

Doing this in a CSG rather than a NCG is possible, but not so simple. (For example, I found on variant on the net which has 13 rules, and is using a less restrictive definition of CSGs than the one above!) This little 4 rule NCG is a lot easier to understand, and a lot easier to write.

Level One Computing Devices

For level 1, the computing device is a bounded tape turing machine. As a reminder, I described turing machines earlier. A normal turing machine has as much tape as it wants to work with; the tape is however long it has to be, even if that means infinite. A bounded tape turing machine has a finite amount of tape; if it exceeds the amount of tape it's given and tries to move the head past the end, it halts and rejects the input string. The machine doesn't have to have a fixed input tape length for all inputs: for a language to be computable on a bounded-tape turing machine, you need to be able to select the length of tape that you will need to perform an acceptance calculation given only the length of the input.

If the machine is non-deterministic, then the amount of tape needed for a given input is a simple fixed multiple of the size of the input (the multiplier varies by machine/program). We call that machine a linear-bounded automaton (LBA). (IN my experience, LBA always means non-deterministic; to specify a linear bounded deterministic machine, it's LBDA.) If you're working with a deterministic machine, then the amount of tape needed for a given input can be calculated using some polynomial in the length of the input; the specific polynomial is dependent on the details of the machine/program.

Just for the heck of it, here's a very common example of a function that you cannot compute using a bounded automaton of any kind. It's called Ackermann's function, and it's an interestingly evil little bugger. It takes two integers as input. We'll call it A(m,n):

A(m,n) = n + 1 if m = 0
A(m,n) = A(m-1,1) if m > 0 and n = 0
A(m,n) = A(m-1,A(m,n-1)) if m > 0 and n > 0

Looks trivial, doesn't it?

But if you actually try to work it out, A(4,2)= 2^(2^(2^2)) - 3, which is 2^65536 - 3, which equals rough 2x10^19729. A(4,3) = 2^(2^(2^(2^2))) - 3, which is a number with more digits than there are atoms in the universe.

You can't bound it. You can't hope to bound it. Just computing the size of it isn't boundable. It's just evil.

The Joys of Crank-Mail and Bad Gematria

2006-05-07T18:10:00.000-04:00

I got my first real crank-mail in response to my blog, and while it's too long to post in its entirety, I thought I'd pull some excerpts from it, and post them for a laugh. As I've mentioned once or twice, I'm Jewish, and this is sort of a poor mans version of something from the Jewish spiritualist tradition, called gematria. Now, in my oh-so-humble opinion, gematria is a fun and interesting game to play, as long as you always remember that it's a game.

In hebrew, the same characters are used for letters and numbers. So you can treat a word as a number. Gematria is supposedly a way of finding hidden meanings in the words of the Torah; by converting between words and numbers, summing words and sentences, and other such tricks, you can find new words and new meanings.

It's not a complete waste of time. Often when I'm working and I hit a brick wall, I might try playing with something like gematria. Not because I think that there's any "hidden knowlege" that's going to be revealed to me, but because I often get caught in a bit of an intellectual rut - that is, I apprach things in a particular way, and that way isn't working. So throwing a bit of randomness and free association into the process can help me to find a different way of looking at my problem. It lets me exploit the way that the human brain naturally searches for patterns and associations, by giving it something different to stare at.

But that's sort of the point: it doesn't reveal anything special or magical. There are no deep truths revealed by playing word and number games, any more than there are deep truths in a crossword puzzle or a sudoku.

And to make matters worse for the moron who sent me mail, he's playing all sorts of stupid games with allegedly biblical texts - but he's doing it in english. Even if you're the sort of person who believes in magic codes embedded in the bible, the idea that they wouldn't be revealed in the original text, but in some third generation translation - well, it's just pathetic.
So here he is - the bozo, in his own words, with a bit'o'mockery mixed in for fun.

Signs and symmetry in reality:
Do signs create symmetry in reality?
Mar 8:12 And he sighed deeply in his spirit, and saith, Why doth this generation seek after a sign? verily I say unto you, There shall no sign be given unto this generation.
Mat 12:39 But he answered and said unto them, An evil and adulterous generation seeketh after a sign; and there shall no sign be given to it, but the sign of the prophet Jonas:

Mat 12:40 For as Jonas was three days and three nights in the whale's belly; so shall the Son of man be three days and three nights in the heart (middle, center, my words) of the earth.
O = no sign
O = one sign
O has no beginning and no end.
O is in the middle of GOD. (nothing in me)
Jhn 14:30 Hereafter I will not talk much with you: for the prince of this world cometh, and hath
nothing in me.

I believe in an IDOL. (Intelligent designer of life)
I believe he (or she) created time, size, and direction. (reality) Because each is infinite, each has a reference point in the middle. (zero)

Yes folks, everything infinite has a middle.

Mankind has six (6) senses, contacts with reality.(The 6th is balance)
Each has a reference point in the middle (zero)
The word “level” is symmetrical with v in the middle of eve.

Overlaps between english words derived from vulgar latin and poorly transliterated from hebrew are clearly profoundly meaningful occurences. And the sense of taste has "a reference point in the middle".

A builder’s level is level when the bubble is in the middle.
If one is not sure it’s accurate, turn the level 180 degrees.
It should read the same.
If I open a bank account with $100 dollars and then write
a check for $100 dollars, my balance is real, zero.
Mankind has 3 faces. The middle one is zero.(indifference)
The two ends are infinite. (plus & minus) (love & hate)
Rev 3:15 I know thy works, that thou art neither
cold nor hot: I would thou wert cold or hot.
Rev 3:16 So then because thou art lukewarm, and
neither cold nor hot, I will spue thee out of my mouth.
In other words, “Love me or hate me. Just don’t sit on the fence”.

This part I can't even make enough sense out of to mock.

Every living thing is symmetrical. Even a "flounder"
when it's born, has two (2) sides and a "fold",
a reference point in the middle.

Every living thing is symmetrical. Except of course, for the things that aren't, like the
cnidiarians and poriferans.

Every living thing is symmetrical because the center
of heaven is symmetrical just like the name of the
"mother of all living", Eve.

Actually, Eve is a lousy transliteration from hebrew by way of Greek and Latin; the original name is "Chava", which isn't symmetrical in any way.

The tree of life, who bares her fruit every month, is unique partly because her leaves are symmetrical. She also has deep roots.

Because most trees don't have symmetrical leaves. (I don't know of any trees that don't have symmetrical leaves, but hey, what do I know?)

Rev 22:2 In the midst of the street of it, and on either side of the river,(symmetry, my words) [was there] the tree of life, which bare twelve [manner of] fruits, [and] yielded her fruit every month: and the leaves of the tree [were] for the healing of the nations.
Life 101...Noah brought his family and every living animal into the ark by pairs.
(plus one) plus (minus one) = zero

Again, not enough coherence to even mock really.

If a = 1, b = 2, c =3, etc., then the following values are true:
Jesus (74)( gd) (beginning & end) divided by 2 (folded once) = fold, cg (37) See also Zec. 9:9

Yeah, if you take a name which is a lousy transliteration of "Yeshua"; and you play gematria games with it, you can get a mispelling of the word of "god"... And something else, which makes no sense.

Psa 37:37 Mark the perfect [man], and behold the upright: for the end of [that] man [is] peace.

Well, I can't really complain about the idea that Mark is the perfect man. Oh wait, that's not what he meant...

God’s name, “I Am that I Am” is symmetrical. Just by coincidence, “that” has the same numerical value as “sign”(49), which equals God (26) plus I Am (23).

No, it isn't. In fact, it's four characters in hebrew - Y H V H. Not symmetrical. Sorry. Bzzt.

I Am equals “end” and also “IN”, the first, second, and last letters in the bible.

I have no idea of what bible he's using, so I can't tell what the last word is, but the first word? It's not "in", it's "B'reshit". So the first letter is the hebrew B.

“Noah” equals “gold” (God + 12)
I Am + I Am + I Am = I Am IN I Am (Jehovah) or (In Vain).(69)
1+2+3+4+5+6+7+8+9+10+11+12 =78 (3 X God ) (I have chosen you 12) Check out the breast
plate of the high priest, or the first 12 numbers on a roulette table. The middle 12 numbers = 3
x Jesus. The total of all 3 twelves = 666.
666 + 12 = 678 ( 3 x God + 3 x Jesus + 3 x Az, first and last or 126)
1 through 36 plus Zero plus double zero = 38 numbers.
God + 12 (o8) = gold (38) (What the mercy seat is made of)
38 = Noah (last, first, and o)
3 X God (704) = 2112 ( U 12 ) (11 hid in 3 measures)
Jesus + fold = 111 (11 hid in 3 measures)
Mat 13:33 Another parable spake he unto them; The kingdom of heaven is like unto leaven, which a woman took, and hid in three measures of meal, till the whole was leavened.
Eve + 22 = God (54), (love), (leaven hid in 3 measures)
Eve x 22 = God (704) (leaven hid in 3 measures) also (11 hid in 3 measures)
Christ (77) hidden in Eve:
E V E
5 22 5
52 + 25

Yes, it's more lousy pseudo-gematria based on lousy translations/transliterations from and through other languages. And he *keeps going*. This crap I've posted is only the first third of the pile of steaming gibberish he sent me.

Can you imagine how much time this bozo spent doing this? It's a fine demonstration that the doctors in the asylum are giving the patients far too much free time with the computers.

Creationists and Extra-solar planets

2006-05-05T20:23:00.000-04:00

I had so much fun with the AiG pseudo-relativity argument, I decided to prowl around their site looking for other fun things to shred. Todays article is Extrasolar planets suggest our solar system is unique and young. This has the advantage of being incredibly stupid, and of also demonstrating some of the statistical errors that I just talked about the other day.

Here's the basic idea of their argument:

Much excitement concerns the star 55 Cancri. Apparently, it has a Jupiter-like planet orbiting further out—at about 5.9 AU with a mass about 4.05 M_Jupiter. (AU, stands for astronomical unit, the unit of length for solar-system-scale measurement, and equals the average distance of the Earth from the sun. The mass unit, M_Jupiter, is based on the mass of the planet Jupiter, about 318 times the mass of the Earth.) Because this exoplanet with 55 Cancri exists, so the thinking goes, other exoplanets must exist much farther out from their host stars. If so, our solar system would not be unique.

Evolutionists hope that many stars will be discovered with habitable Earth-like planets and gas-giant planets orbiting far from their host stars—similar to our solar system configuration. It’s interesting that this latest speculation has arisen from extrapolating a single observation with both mass and measured orbital eccentricity (e = 0.16) much greater than Jupiter’s (e = 0.05). The reports also reveal that 55 Cancri apparently has two other Jovian-mass planets orbiting much closer (< 0.3 AU). Obviously the planetary system for 55 Cancri is not particularly similar to our solar system.

Basically, they want to argue that our solar system is special. The way that they're going to do that is to look at what we know about other solar systems, and argue that because those solar systems aren't much like ours, that therefore our solar systems is special and unique.

Before I hit them for anything else, I have to point out one piece of general linguistic bogosity. Throughout this article, they refer to the astronomers and other scientists looking for extra-solar planets as "evolutionists". Of course, none of this has anything to do with evolution. It's just a knee-jerk thing with them: anything which seems to suggest that their biblical doctrine doesn't match physical reality is automatically put under the banner of evolution.

Once they're done with the introduction, they present a bunch of statistics about the extrasolar planets that we've discovered so far:

A simple statistical analysis of some of the data for the exoplanets listed to date3 yields the following averages:
Mean semimajor axis, a = 1.24 AU
Mean eccentricity, e = 0.274 (larger than Pluto’s e = 0.244, the most eccentric of our solar system)
Mean mass = 3.295 M_Jupiter
If this average gas-giant planet were orbiting in our solar system it would have a perihelion, (q) of 0.90 AU and aphelion, (Q) of 1.58 AU and continually cut across Earth’s orbit. We need to keep in mind that the masses reported are a minimum estimate, not a maximum.

In our solar system, the average values of the nine planets for the same three properties are:
Mean semimajor axis, a = 11.902 AU
Mean eccentricity, e = 0.081
Mean mass = 0.156 M_Jupiter
The ‘average’ perihelion, q is 10.938 AU and the aphelion, Q is 12.866 AU, which is well removed from the Earth’s orbit.
...
The extrasolar-planet data suggests our solar system is special, which is difficult to explain from a naturalistic evolutionary perspective. For some reason, when our solar system formed, the sun managed to avoid the more common ‘fate’ of other star systems. Specifically, we do not have gas-giant planets orbiting from 0.1 to 3.0 AU from the sun, like 75% of the stars with planets so far listed.3 The other planets in our solar system are well clear of the Earth’s orbit.

Here's where we start seeing the problem. Superficially, this all looks fine. So what's the catch?

How is the sample that was used to compute the averages for extra-solar planets selected? Well, it's the (very small) set of planets that had been discovered three years ago (when this article was written). And what properties does that sampling method have? Well, all of the planets were discovered using astronomical techniques based on how the mass of the planet perturbed the motion of its star. We do not know much about the solar systems with these large planets, except that they have large planets. Do they have smaller planets in closer or farther orbits? We can't tell. Are there other stars with smaller planets? We don't know.

There's the key. The way that we find extrasolar planets orbiting distant stars only works for extremely massive planets; and it works better for massive planets in close orbits; and it works better for planets with eccentric orbits (because eccentric orbits have a more pronounced effect on the star).

So if we can only find planetary systems with extremely large planets; and the only planets we can detect are the large ones (so even in a system with large planets, we can't tell if there are also small ones); and our method for finding these systems is better and finding systems with eccentric orbits... Then, by putting together statistics about what we know about these systems, we can conclude that other solar systems we know about tend to have larger planets in more eccentric orbits than our solar system.

Wow. Deep, huh?

And now it gets really funny.

The data is easy to understand from a young-earth creation model. Since Creation Week ended (Genesis 2:1–3) some 6,000 years ago as measured on earth, the sun and nearby spectral class G stars have completed much less than one galactic rotation. Certainly, since Creation Week, these nearby star systems have experienced little stellar evolution. The creation interpretation affects our understanding of the origin of our solar system and of extrasolar planets.

I wonder if evolutionists thank their lucky stars and random particle collisions for the unique configuration of our solar system and our habitable earth. Modern secularists cannot consider that the Creator had anything to do with it. Such thinking would violate a central tenet of modern science—methodological naturalism.8

From a creation perspective, God, during the Creation week, predetermined the initial conditions of our solar system to provide a habitable earth. We know from Genesis 1:31, that at the end of Creation Week God’s creation was ‘very good’. It is hard to imagine that gas-giant planets orbiting near the Earth and gravitationally interacting with it would fit the description of ‘very good’. Such interaction would cause the Earth to become as volcanically active as Jupiter’s moon Io, even if the orbits were stable.

Y'see, we know that earth is special because it's different from those other systems. The reason that it's different is because God said that his creation of earth was "very good", and if our solar system looked like the ones that they're comparing to, it wouldn't be very good. Therefore, God must have created the solar system this way, because it is very good.

Oh, and we know that the solar system is young, because, well, umm... Because if it were older, then it would have completed several galatic rotations which would have.. umm.., well, it would have messed stuff up. They can't really say how, or why.. just that it means that our solar system has experienced "little stellar evolution".

Context Free Languages

2006-05-05T16:07:00.000-04:00

Moving on to the next tier of the Chomsky heirarchy, we hit the context free languages. CFLs are amazingly useful buggers: virtually every compiler, and in fact virtually every large piece of application software uses CFLs somewhere, and the way that we use them is actually very close to the formalism I'm going to talk about; and the programs that we use for manipulating CFLs in real software is pretty much the formal machine that I'll talk about here.

Representing Context Free Languages

A context free language is represented by a context free grammar (CFG). The production rules have a single NTS on the left, and any sequence of terminals and non-terminals on the right (including the empty sequence).

To show you a CFG for something real: this is the grammar for lambda calculus, which is something really cool that I'll write about later. To make things easier, if there are multiple productions with the same symbol on the left hand side, I'll sometimes join the right hand sides with "|" symbols; for example, if I had productions "a ::= x" and "a ::= y", I'll sometimes combine those as "a ::= x | y".

The terminals are "LAMBDA", "DOT", "(", ")", "A", "B", "C", ..., "Z". And the production rules are:


ident ::= "A" | "B" | "C" | ... | "Z"
expr ::= LAMBDA ident DOT expr
expr ::= ident
expr ::= expr expr
expr ::= ( expr )

Here are a few typical strings from this grammar: "LAMBDA X DOT X Y", "LAMBDA X DOT ( LAMBDA Y DOT X Y) X", "X Y Z", "(X (Y (Z)))", "((X) ((Y X) Z) ((X) (X Y)))".

Capabilities and Limits of CFLs

From this example, you can see one of the things that you can do in a context free language that you can't do in a regular language: count. A string is only a member of the language if parens are matched. If you were processing the string character by character, the number of open parens is always greater than or equal to one; and at the end of the string, it's always zero.

CFLs are still pretty limited in many ways. You can't write a grammar for a spoken language using CFGs - natural languages aren't context free. We use CFLs and CFGs all the time for compilers and such in real programs, but there's always an extra step involved, because there are aspects of real computer languages that can't be captured in context-free form.

So what can't you do in a CFL? I'm not going to try to formally characterize the limits of CFLs, but here are two examples:

Non-trivial counting: if you want a language of strings with the same number of Xs and Ys, that language is a CFL. If you want a string with the same number of Xs, Ys, and Zs - that isn't.
Constrained references: you can't specify that a particular symbol can only occur in one place in the string if it already occured in a prior part of the string. For example, in the lamba calculus example, it really should say that you can only use the "expr ::= ident" rule if the ident occured in an enclosing LAMBA ident". CFLs can't do that.

Computing CFLs: the Pushdown Automaton

CFLs are computable using a kind of machine called a pushdown automaton (PDA). Pushdown automata are relatively simple: take a finite state machine, and add a stack.

For the non-CS folks out there, a stack is a last in first out (LIFO) storage system. What that means is that you can store something on the top of the stack whenever you want to (called pushing), look at what's on top of the stack (peeking), and removing the element on top (popping).

For a PDA, the transitions look like:


((state,top-of-stack,input) -> (state,stack-action))

The top-of-stack in the transition can be either a symbol from the machine's alphabet, or it can be "*".
- If it's a symbol, then the transition can only be taken if both the machine state and the top-of-stack mach.
- If it's "*", then the transition can be taken regardless of the value on top of the stack.
The stack-action can be "push(symbol)"; "pop", or "none".

The machine accepts the input if it reaches a final state with the stack empty. (There are alternate formulations that don't require an empty stack, or that only require an empty stack but don't use final states. They're exactly equivalent to empty stack + final state.)

As usual, it's easiest to understand this with an example. So let'l look at a simple language consisting of parens and identifiers, where the parens have to match. So, for example, "((I)(((I)I)(II)))" would be accepted, but "(I)(((I)I)(II)))" (the same string, but with the first open removed) would be rejected.

Our machine has an alphabet of "(", ")", and "I". It has two states: 0, and 1. 0 is both the inital state, and a final state.

Stacktop	Input	Post-State	Stack-Action
*	"("	0	push("(")
"("	")"	0	pop
I	*	0	none
empty	")"	1	none

Or graphically:

So - if it sees a "(", it pushes a "(" on the stack. If it sees an identifier, it just keeps going past it. If it sees a ")", and there's an "(" on top of the stack, it pops the stack; if it sees a ")" and there's no "(" on the stack, then it switches into state 1. Since state 1 is not a final state, and there is no transitions that can be taken from state 1, the machine rejects the string if it sees an extra ")". If there's a "(" without a matching close, then when the machine finishes, it will have a non-empty stack, and so it will reject the string.

Finally, one nifty little note. What happens if we add a second stack to the PDA? Well, that's equivalent to a turing machine: think of one stack as the tape up to the current head position; and the second stack as the tape after the current head position.

Friday Random Ten, May 5th

2006-05-05T10:46:00.000-04:00

Trey Gunn Band, "Sozzle". Instrumental stuff from an amazing touch-guitar player and current member of King Crimson. Trey's solo stuff is, unfortunately, rather dull.
Psychograss, "Mind's Meat". Deeply warped bluegrass.
Steve Reich, "Ehmore M'aht, V'ahsay Harbay". A movement from Steve Reich's recent piece, the "You Are" variations. Brilliant.
Jethro Tull, "Cold Wind to Valhalla". Classic Tull.
Solas, "Lowground". Very strange - a traditional Irish band playing bluegrass. And yet, it works.
Dave Matthews Band, "The Dreaming Tree". I know I should be ashamed, but I really like jam bands. This is one of my favorite songs from the DMB.
Flook, "Eb Reels". Flute heavy Irish trad.
Hugh Blumenfeld, "Why am I awake". Hugh is a folksinger from Connecticut, who's performed a few times at venues set up by the New Jersey Folk Project. He's a great songwriter.
Genesis, "Silent Sorrow in Empty Boats". Track off the Gabriel-Genesis masterpiece, "The Lamb Lays Down on Broadway". Even 30 years or so after it was recorded, it still manages to not sound terribly dated.
Martin Hayes, "Kitty Come Down to Limerick". Martin Hayes is a classically trained violinist who plays traditional Irish music in a traditional way. That means not so bloody fast. Irish music is mostly dance music - you can't dance to a reel played at 180 beats per minute!

Nondeterminism in Finite State Machines

2006-05-03T21:24:00.000-04:00

Yesterday, I started to explain the difference between a non-deterministic FSM, and a deterministic one. Today I'm going to expand on that theme a bit.

From any given state, a deterministic automaton has no more than one possible transition for each input symbol. A non-deterministic machine doesn't have that restriction: it can have as many transitions as it wants for any pair of (state,symbol). In NFAs, we often even add a convenient shorthand called an empty transition - that is, a free transition from one state to another which the NFA can take if it wants to, without consuming an input symbol. We typically label empty transitions with a greek letter epsilon or a lower-case e.

That's actually the general difference between deterministic machines, and non-deterministic ones. Deterministic machines have exactly one thing they can do in any situation; non-deterministic ones have multiple choices.

But - what does that actually mean in terms of computation?

Well, for both deterministic and non-deterministic FSMs, they accepts a string as a member of their language if, after processing all of their input, they can end in a final state. For a deterministic machine, that's a straightforward notion: there is only one possible path through the FSM for any given input, and so there is exactly one possible state that the machine is in after processing the input.

For a non-deterministic machine, it's a bit more subtle. There can be many possible paths through the machine for a given input. We say that the machine traverses allof those simultaneously. So the DFAs computational path is a simple chain - a linear sequence of states that it passes through as it processes the input. The NFAs computation path is a tree - at any point where the NFA can take more than one transition for a given input symbol, the execution path branches, and it follows both.

Now, the obvious question is: what does this gain us? Can we do anything with an NFA that we can't do with a DFA?

Nope. Not a darn thing. For any NFA, there's a DFA that can compute exactly the same language. In fact, it's even a easy process to translate an NFA to a DFA. And there's no time-complexity difference: both NFAs and DFAs always take one step per input symbol. The only difference is space: translating an NFA to a DFA can result in a DFA with an exponetially larger set of states.

In fact the translation is specifically based on an exponential: given an NFA N, you can translated it into a DFA D, where the set of states in the DFA are isomorphic to the powerset of the states of N. (The powerset of a set S is the set of all subsets of S.) Basically, you take the set of all subsets of states of the NFA; and starting at the initial state, for each symbol, you figure out the set of states that you could transition to for that symbol, and in the DFA, you put a transition to the state corresponding to that set of states. Then you repeat that for each of the new states you added; and keep going until you stop adding states. In the worst case, for an N state NFA, you'll wind up with a 2^N state DFA.

Here's a fairly trivial example. Let's look at the language: (a+)|(ab*(a|b)) - that is, a language consisting of either a non-empty sequence of "a"s; or a single a followed by a (possibly empty) sequence of bs, followed by either a single a or b.

We can translate it into a DFA like the following:

The NFA is a lot easier to read; and this is a really trivial language. For anything more complicated, it gets a heck of a lot messier.

As a final note, non-determinism isn't always useless: for FSMs, you don't get additional power by using non-determinism. But for more advanced automatons, non-determinism might make a difference. It definitely can make a space difference for algorithms on turing machines. Does it make a time difference? We don't know.

Regular Languages

2006-05-02T20:58:00.000-04:00

As I said yesterday, the Chomsky heirarchy specifies four basic types of languages. The simplest one, level 3, is the family of regular languages.

Regular languages are very simple little beasts. No counting, no deep patterns, and very little computational power. A machine that processes members of a regular language can always accept or reject a string in a number of steps equal to the number of symbols in the string.

Specifying Regular Languages

There are two commonly used ways of specifying regular languages: regular grammars, and regular expressions.

Regular grammars come in two flavors: left regular and right regular. A right-regular grammar is a phrase structure grammar where the left-hand side of every replacement rule (also called a production) is one non-terminal; and the right hand side is a sequence of terminals, optionally followed by a single non-terminal.

For example, the following are all valid right regular grammar productions (I'm writing non-terminals as lower-case italic latters, and terminals as upper-case):


a ::= XYb
b ::= WX
c ::= WXZYc
d ::= Xa
d ::= X

And the following are not right-regular productions:


a ::= XbY    (NTS not at end)
b ::= aWX    (NTS not at end)
c ::= WXZYcd (more than one NTS)

Alternatively, we can specify regular languages using regular expressions. A regular expression is:

(simple matching): a regular expression consisting of a single symbol matches a string consisting of that character.
(concatenation): two regular expressions placed side by side: RS matches a string if the string can be partitioned into two substrings so that R matches the first substring, S matches the second substring.
(alternation): two regular expressions separated by "|": R|S matches a string if R matches the string or S matches the string.
a regular expression inside of parenthesis (grouping): (R) matches a string if R matches the string.
(Kleene closure/repetition): a regular expression followed by a "*". R* is the same as (empty|R|RR|RRR|RRRR|RRRRR|...) - that is, zero or one repetitions of substrings matching R.

In addition, we also often use "R+" to mean the same thing as RR* (that is, a sequence of strings matching at least one repetition of R.

Regular expressions are amazingly common - we use them every day in normal programs. Pretty much all scripting languages include some form of regular expressions as primitives, and nearly all programming languages at least include libraries for using regular expressions.

A few examples of regular expressions:

(a|b|c|d)*: any string of any length made from the characters "a", "b", "c", and "d".
(a|b)*(c|d)*: a string of any length made of "a"s and "b"s, followed by a string of any length of "c"s and "d"s.
(a|b)+(c|d)+: a string of one or more "a"s and "b"s; followed by a string of any length of "c"s and "d"s.
aa*b*(cd)*(e|f): strings consisting of at least one A; followed any number of "b"s (including zero); followed by any number of repetitions of "cd"; followed by either a single "e" or a single "f".

Machines for Regular Languages

Regular languages can be accepted by a very simple kind of machine called a finite state automaton (FSA) or a finite state machine (FSM). A FSM consists of:

A set of states, S.
A single special distinguished state in S called the initial state, s_0.
A subset of the states in S called the final states, S_f.
A set of transition rules, each of which is a triple: (state,symbol,state).

The way that a FSM works is that it starts in its initial state, s_0. Then it looks at the first character c in the string, and tries to find a transition (s_0,c,s_x). If it finds a transition like that, then it switches to state s_x, and goes on to the next character. If at any point there is no rule for the current character in the string, then the machine rejects the input string as not in the language. If, after processing the last character, the machine is in a state in S_f, then the string is accepted as a member of the language; if it is in any state not in S_f, then the string is rejected.

So, for example: if we wanted to process the language of strings consisting of a string of at least one A, and any number of Bs, we would have three states: init, S_a, and S_b. init would, obviously, be the initial state; S_b would be the only final state.

The transition rules would be: { (init,a,S_a), (S_a, a, S_a), (S_a, b, S_b), (S_b, b, S_b) }.

FSMs can be drawn very easily; each state is drawn as a circle labelled with the state name. Each transition rule is an arrow from state to state labelled by a symbol. The start state is indicated by an arrow; and the final states use a double-line for their outline. So the machine I described up above would look like this: (Note: the diagram below is corrected from the original posting; I forgot to finish the diagram before posting it! The original version did not include the double-ring on state S_a, or the "b" arc on S_b. Thanks to commenter "Big C" for pointing this out.)

The description so far leaves one question open: can we have more than one transition rule from a given state for the same character? The answer to that is not trivial; it actually introduces something very interesting.

If you can have one rule per symbol from a state, you have a deterministic machine. If you have multiple rules per symbol from a state, you have a non-deterministic machine. In the non-deterministic machine (an NFSM), the machine accepts a string as a member of its language if any possible sequence of transitions leads to a final state.

I'll have more to say about determinism versus non-determinism in computations in another post.

Slandering with Statistics

2006-05-02T16:09:00.000-04:00

One thing that I keep getting mail about is various folks misusing statistics. There are a lot of examples of this, from young earth creationists, to the intelligent design bozos that I've spent too much time on, to various racist assholes, to HIV/AIDS denialists.

A link to a comment from another blog posted by a racist asshole trying to argue that the accuser in the Duke Rape case is probably lying is an example of a kind of misuse of statistics that I haven't talked about yet, so I thought it was worth taking a moment to look at it.

So here's what the asshole had to say:

Unfortunately, statistically a black women is significantly more likely to make a false accusation of rape than to have been raped by a white man. According to the National Crime Victimization Survey ( http://www.ojp.usdoj.gov/bjs/pub/pdf/cvus/current/cv0342.pdf ), less than .0004% of black rape victims were raped by whites. (The NCVS reports the percentage as 0% because there were less than 10 reported cases. I assumed 9 cases, to come up with an actual percentage) Even with the most conservative figure of 2% of rape allegations being false, this means in the case of the Duke Rape Case, the victim is 5000 times more likely to have made a false accucation than to have actually been raped.

Before I hit the real point, I'll point out that there's a really dumb math error in there: it's not "0.0004%"; it's "0.04%". Yeah, sure, we're still talking about small numbers, but two orders of magnitude is nothing to sneeze at, and it shows either how little concern the writer has for the facts; or it's a deliberate attempt to dishonestly skew the numbers by adding a percent sign.

But what's really important are the errors in how he uses statistics. He's making two major errors. One is a sampling error in producing a meaningful statistic; and one is an error in how you can apply a statistical result.

Statistics are a way of analyzing large quantities of data to understand patterns and trends, and they're very useful for that. But you have to understand what a statistic means and how it was gathered in order to know when it can be applied. In general, statistics are useful when they are generated from a large enough pool of correctly sampled data; statistics can be meaningfully applied to data in the aggregate (applying broad statistical trends to individual cases is rarely enlightening).

Now, in the above quoted gunk, the writer admits that the size of the sample from which he is extrapolating is vanishingly small in the data. You cannot generate anything meaningful from such a small sample: that "0.04%" number is basically just made up - it has no validity, no statistical meaning.

That's not the only sampling error that he makes. Even if there were enough data in the survey that he cited to draw some conclusion, you have to recognize the properties of the data that you're working with - the nature of the sample, and what, if any, data skew you would expect to see.

Whites raping blacks is something with a long history in America. We know that historically, it was extremely common. We also know that there is a significant social factor to this kind of crime: the usual dynamic of it is a poor black woman raped by a comparatively wealthy white man. In this dynamic, the victim is, at best, going to be socially stigmatized by coming forward. (For example, do you think that the black woman who had Jesse Helms' illegitimate daughter could have come forward and said he raped her? Do you think that the poor black "servant" in Helms childhood home actually wanted to have sex with him?) What this means is that because of the social environment, crimes like white-on-black rape are very likely to be under-reported.

This is a property of the sampling of the data. It's based on reported crimes; and we know that rape is a chronically under-reported crime, and that there are good reasons to suspect that the under-reporting is especially pronounced in the cases of black victims with white perps. So when we use that data, we need to recognize the sampling bias in it - and consider that when we use the data to draw conclusions.

You cannot use crime report statistics without recognizing the biases that are a natural part of the reporting process that generates those statistics. We know that the data are very likely to be flawed when it comes to this subject; to then use a microscopic subset of the flawed data and try to apply it to an individual case to purportedly say something meaningful - that's just nonsense.

But that's exactly what our little racist buddy does: he creates a meaningless number from a meaninglessly small sample of data with a known bias, and tries to combine it with other statistics to come up with a number that he can use in an argument.

Then he tries to apply the statistic that he generated. One of the very important properties of statistics is that they talk about populations, not individuals. The average american family has often been cited as having something around 2.7 children. You can't use that statistic to say that a particular family probably has two and two-thirds children.

But again - that's exactly what he does: he creates a nonsense statistic, and then applies it to a specific individual to argue that we should believe that she is lying.

Relativity and Young Earth Bogosity

2006-05-01T20:00:00.000-04:00

I was forwarded a really great link to the latest "theory" being put forward by those jokers at Answers in Genesis to explain the age of the earth. Folks, this one is a real winner! It's one of the funniest things I've read in years.

The problem that these guys have is that they need to reconcile their young-earth religion with the fact that when we look into space, we see a universe that overwhelmingly appears to be incredibly old.

For years, their claim was that the speed of light used to be faster. This has gradually started to fall out of favor, mostly because it's blindingly stupid. You still see it a lot among the various low-level goons of the creationist movement, but the leaders have moved on. The problem with this "argument" is that you can't change the speed of light without changing a whole lot of other things: many of the basic constants are interrelated in various ways to make our universe behave the way it does. Put ultra-simply, alter the speed of light, and suddenly chemistry stops working. Or as the geniuses over at "Answers in Genesis" put it:

The biggest difficulty, however, is with certain physical consequences of the theory. If c has declined the way Setterfield proposed, these consequences should still be discernible in the light from distant galaxies but they are apparently not. In short, none of the theory’s defenders have been able to answer all the questions raised.

The new claim is trickier, and wiggles it's way around the fine-tuning thing. The new argument is that the earth is at the center of the universe, and that this creates a relativistic time-dilation effect around the earth which means that time on earth is dramatically slower than time in the rest of the universe - so the rest of the universe may be billions of years old, but the earth itself is only 6000 years old.

Here's how they introduce it:

Let us briefly give a hint as to how the new cosmology seems to solve the starlight problem before explaining some preliminary items in a little more detail. Consider that the time taken for something to travel a given distance is the distance divided by the speed it is traveling. That is:

Time = Distance / Speed

When this is applied to light from distant stars, the time calculates out to be millions of years. Some have sought to challenge the distances, but this is a very unlikely answer.7

Astronomers use many different methods to measure the distances, and no informed creationist astronomer would claim that any errors would be so vast that billions of light-years could be reduced to thousands, for example. There is good evidence that our own Milky Way galaxy is 100,000 light years across!

If the speed of light (c) has not changed, the only thing left untouched in the equation is time itself. In fact, Einstein’s relativity theories have been telling the world for decades that time is not a constant.

It's a really great start. First, we jumble the dependent and independent variables, to define time as linearly dependent on speed. Then we babble a bit about Einstein to argue that time isn't constant, and so we can jiggle about this little equation. But wait - that's nothing. Really. If that was as far as they went, I wouldn't have wasted my time writing this. It gets much better.

Here's the real prize, the coup de grace. This is just magnificant stupidity:

Dr Humphreys’ new creationist cosmology literally ‘falls out’ of the equations of GR, so long as one assumes that the universe has a boundary. In other words, that it has a center and an edge—that if you were to travel off into space, you would eventually come to a place beyond which there was no more matter. In this cosmology, the earth is near the center, as it appears to be as we look out into space.

This might sound like common sense, as indeed it is, but all modern secular (big bang) cosmologies deny this. That is, they make arbitrary assumption (without any scientific necessity) that the universe has no boundaries—no edge and no center. In this assumed universe, every galaxy would be surrounded by galaxies spread evenly in all directions (on a large enough scale), and so, therefore, all the net gravitational forces cancel out.

However, if the universe has boundaries, then there is a net gravitational effect toward the center. Clocks at the edge would be running at different rates to clocks on the earth. In other words, it is no longer enough to say God made the universe in six days. He certainly did, but six days by which clock? (If we say ‘God’s time’ we miss the point that He is outside of time, seeing the end from the beginning.)10

Yes folks - if we assume that earth is at the center of the universe: the literal center of the universe; and we take the combined mass of the entire universe and treat it as a point mass at the center of the earth; and then we use that mass as the mass of the earth and plug it into the relativity equations, we get a truly amazing time-dilation effect around the earth.

That's it. That's the prize of creationist thinking. So what's wrong with it? Well, before I start, I want to say that I'm pretty sure that most of the folks reading this don't need this explained to them. I don't think you're anywhere near that stupid. But I've got to act as if I did think you were that stupid, because I couldn't write about it otherwise.

First: you can compute a pretty good approximation of instantaneous gravitational forces between bodies by treating them as point-masses at their center of gravity. But they are not point masses. And if you do anything but an instantaneous calculation, treating them as point masses will give you the wrong result. They've made a fundamental math mistake here: a simplifying assumption can only be applied in the specific type of calculation for which it was designed, in the specific situation where it was derived. They're applying it in a very different situation - they are not doing an instantaneous calculation of gravitational forces. But they've done far worse than that - they've elevated a computational shortcut to the status of a physical law! The fact that under some circumstance, you can calculate some value more easily by making a simplifying assumption does not make that simplifying assumption a physical fact!

Second: the very meaning of relativity is that there is no universal frame. This whole silly concept is based on the idea that there is a single universal frame, with earth at the center, and that this makes the location of earth fundamentally different from anywhere else in the universe.

(In an interesting connection with the recent discussion of symmetry: relativity describes a set of fundamental symmetries about the universe. This nonsense is creating a fundamental assymetric point in a bogus way, and then applying the equations that describe the symmetry at the assymetric point.)

And then they take it even further!:

It is fortunate that creationists did not invent such concepts such as gravitational time dilation, black and white holes, event horizons and so on, or we would likely be accused of manipulating the data to solve the problem. The interesting thing about this cosmology is that it is based upon mathematics and physics totally accepted by all cosmologists (general relativity), and it accepts (along with virtually all physicists) that there has been expansion in the past (though not from some imaginary tiny point). It requires no ‘massaging’—the results ‘fall out’ so long as one abandons the arbitrary starting point which the big bangers use (the unbounded cosmos idea, which could be called ‘what the experts don’t tell you about the “big bang”’).

Yes - it's lucky that they didn't invent time dilation and relativity and stuff, because we would have made fun of them. And this is all based on rock solid math and physics! No massaging of results! No special conditions! As long as you use relativity while discarding the fundamental mathematical and physical premises upon which relativity is predicated, it's all perfectly valid and obvious!

Computer Science, Math, and Languages

2006-05-01T18:19:00.000-04:00

Computer science is, I think, more of a branch of math than of science. The math behind computer science ultimately comes down to two things:

(1) What can we do?/What can we not do?
(2) If we can do it, how long will it take?

Those two questions define the two fundamental areas of computer science: computability and complexity. Personally, I tend to find computability more fun. That's probably partly because I like the theoretical machines; and partly because I first learned theoretical computer science from a spectacular teacher named Eric Allender, who taught from the perspective of automata theory. Learning something from a teacher like that can dramatically change your opinion of an area: they can show you the fun of something that might otherwise seem hopelessly abstract. Without Eric Allender, I might never have gone to grad school.

Anyway: One of the ways that the two kinds of fundamental CS come together is in the idea of computable language from automata theory. Computable languages are a way of specifying what a given type of computing device can do; and from the type of computing device, we can generate rough complexity bounds on how long a given task needs to take. What's particularly cool/fun about talking about computable languages is that it's both incredibly deep and fascinating; and yet, it's also very concrete. The concreteness comes about because we can "design" different kinds of machines - very concrete specific machines - which are capable of doing the computations expressed by the languages.

The idea of computable languages is that given a problem that we wish to solve, it can always ultimately be described as a language. The kind of language that I'm talking about here is purely syntactic: it is a set of strings in some alphabet selected by a predicate. It's important to understand that the predicate is external: the string itself has no meaning; some program or some machine examining the string can determine if it is a member of a language: the meaning of the string is imposed by the machine, not by the string.

For example: there's a language which consists of all strings of any number of "a"s followed by any number of "b"s. We'd usually write that "a*b*". There's language consist of strings of nested parenthesis, like "(((())()())(()))". There's a language made from strings of digits that consists of the set of all prime numbers. And so on.

We can ultimately describe any computation problem in terms of language; this reformulation of problem as language can change the complexity, but not the fundamental nature of what we can and can't do. To give an example of expressing a problem as language, we can describe addition as a language of patterns like "x+y=z", where the string is part of the language if the addition statement is true.

All formal languages can be described using grammars. A grammar is a set of rules describing how a string in the language can be produced. The kind of grammar that I'm using is called either just "formal grammar", "phrase structure grammar", or Chomsky grammar.

A formal grammar consists of:

An alphabet of characters, also called terminals or terminal symbols(TSs).
A set of symbols distinguishable from the terminals, called non-terminal symbols (NTSs)..
One symbol from the set of non-terminal symbols which is called the start symbol
A set of replacement rules which specify how to generate strings in the language by replacing one substring containing a non-terminal symbol with another substring.

The replacement rules are usually written as a sort of odd-looking equation: the left hand side specifies the substring to be replaced; the right hand side specifies what you can replace it with. In most grammars that you typically see, the left-hand side is always just a single non-terminal symbol. So, for example, a grammar with non-terminals "a" and "b", and terminals "X", "Y", and "Z" could contain a rule like:


   a ::= X Y b Z

What this statement means is when you have a string containing the NTS "a", you can replace it with the string "XYbZ" - that is, the terminals "XY", followed by the non-terminal "b", followed by the terminal "Z".

Here's an example of a complete grammar specifying the set of strings with equal numbers of Xs and Ys, with the Ys after the Xs. The terminals are "X" and "Y"; the only non-terminal is "a", so "a" is obviously the start symbol.


a ::= X a Y     (rule 1) 
a ::= X Y       (rule 2)

This says that if you see an "a", you can replace it with either "XaY", or just "XY". Let's look at how we can use this to create a string of four Xs followed by four Ys:

Start with the start symbol, "a": a
Apply rule 1, replacing "a" with "XaY": XaY
Apply rule 1 again: XXaYY
Apply rule 1 again: XXXaYYY
Apply rule 2, replacing "a" with "XY": XXXXYYYY
Since there are no non-terminals left, we're done.

There's a very natural way of describing four basic categories of languages - and those four categories correspond to four different ways of describing them; four different kinds of machines that can determine if a given string is a valid member of a particular language.

The four groups are arranged in levels, and the organization is called the Chomsky heirarchy. (And yes, it's the same Chomsky who currently spends his time on wacky politics. Back in the '50s, he did great work as a linguist. It's a damn shame he didn't stay in linguistics.)

To briefly describe them (I'll describe them in more detail later, one post each), the four levels are:

Level 3: the regular languages. These are very simple languages, which can't do anything particularly interesting: no counting, nothing beyond sequencing and repetition. Regular languages can be recognized by a simple kind of machine called a finite state automaton.
Level 2: the context free languages (CFLs). These are widely used in practical computer science. They're reasonably expressive; you can do a limited kind of counting with them, but nothing too deep. CFLs can be recognized by a machine called a push-down automaton.
Level 1: the context sensitive languages (CSLs). Context sensitive languages are the things that can be written a more advanced kind of grammar. You can express a lot of quite deep computation using CSLs. CSLs can be recognized by a very interesting machine: a linear-bounded tape non-deterministic turing machine. Level 1 includes most things that we can really compute: the linear-bounding non-deterministic machine is a pretty good match for the capability of a real computer; level 0 conceptually requires infinite memory.
Level 0: the recursively enumerable languages. Anything computable. Level 0 languages are languages which can be accepted by a regular, unbounded turing machine.

There's actually something between level 0 and level 1 in the Chomsky heirarchy. A machine can do one of two things on a given input: it can accept the input; or it can decide about the input. Note that in level 0 above, I said accept.

Accepting the input means that if the input is a member of the language, it will eventually stop and say "Yes, this is in my language". Deciding about the input means that that the machine will eventually stop and say either "Yes, this is in my language", or "No, this is not in my language". The difference is that an accepting machine does not necessarily stop if the string is not in the language. It might be able to stop and say no sometimes, but there is no guarantee.

There is a set of languages more complex than the context sensitive languages which is decidable by a turing machine. These are called the recursive languages.

Friday Random Ten 4/28

2006-04-28T17:51:00.000-04:00

Spock's Beard, "the Planet's Hum". Another one of those neo-progressive bands I love.
Flook, "On One Beautiful Day". Very cool Irish.
Dream Theater, "Honor thy Father". Neo-progressive/prog metal by a great band.
Philip Glass, "Les Enfants Terrible, Scenes 10/11". Part of an opera by Phil Glass. Magnificent.
Bela Fleck, "Katmandu". The master of the banjo.
David Sylvian and Robert Fripp, "20th Century Dreaming". Fripp and Sylvian did one album together a few years ago. If you like Sylvian's crooning vocal style and Fripps bizzare tonalities, this is great, great stuff.
Trout Fishing in America, "It's a Puzzle". The song with my favorite lyrics of all time: "Is is till it isn't, then it was; was was till it wasn't anymore; maybe might be an is in a second".
Lunasa, "Bolton St/The Millstream/Loophead Lighthouse". The best traditional Irish band that you'll ever hear.
King Crimson, "Dangerous Curves". Highly bizzare and wonderful instrumental by that great band of lunatics, KC.
Kaipa, "Sonic Pearls". Really great neo-progressive from the first band that the founder of the Flower Kings performed with.

The ABCs

2006-04-28T17:50:00.000-04:00

This seems to be circulating around the geekish blogs, so I figured why not?

Accent: New York. Not the Brooklyn NY. But I definitely say "bawl" for ball, and "cawfee" for coffee.

Booze: Grappa. I positively adore grappa. (Terrifyingly, it was one of my daughters first words. We were in Italy on vacation when she cut her first molars, and everyone says that rubby a little bit of brandy on the kids gums helps. She loved it, and tried to get more.)

Chore I hate: folding laundry.

Dog or Cat: Both; one small tuxedo cat, and one large golden retriever. I prefer dogs, but do adore both.

Essential Electronics: My powerbook. My ipod. Who could live without those?

Favorite Cologne: I despise all colognes, perfumes, and other stinky things that people put on themselves. Ech.

Gold or Silver: gold. I don't really care much, they're both pretty, but silver is so hard to take care of.

Hometown: I was born in Bound Brook, NJ; grew up mostly in Bridgewater, NJ; four-year stint in Findlay, Ohio in between.

Insomnia: when my wife snores. Also known as "most nights".

Job title: Research staff member.

Kids: Two, one girl 5yo, one boy 3yo.

Living arragements: House on a cliff in Westchester county, NY.

Most admirable traits: wait, I'm supposed to have admirable traits? No fair!

Not going to cop to:

Overnight hospital stays: As an adult, just one, for a nissen fundoplication to fix a pretty-much nonexistent sphincter at the top of my stomach. Not fun, not recommended; but people like me used to die of esophageal cancer; now I just have horrible cramps and trouble swallowing.

Phobias: Crowds.

Quote: "I'm not dumb; I just have a command of thoroughly useless information" -- Bill Watterston.

Religion: Judaism, particularly the Reconstructionist branch.

Siblings: One brother (older), one sister (younger).

Time I wake up: Around 7am.

Unusual talent or skill: Wait, doesn't this sort of connect to that "most admirable trait" thing? Oh, wait, it doesn't need to be admirable, just unusual. Ok. Let's see. I can trip over nothing, is that a skill?

Vegetable I love: Hard to pick one. Either chinese brocolli or snow pea greens.

Worst habit: procrastination. Why do you think I'm doing this?

X-rays: Too many. Mostly abdominal, related to the problem that led to the surgery mentioned above.

Yummy foods I make: Another one with a lot. At one point when I was in grad school, I seriously thought about dropping out and opening a restaurant. A few of my favorite things: rare seared duck breast with ancho-honey sauce; hong-kong style braised fish with tofu; catfish with dashi sauce and soy syrup; brandied chicken risotto w/portabello mushrooms.

Zodiac sign: Leo.

Cyclic Groups

2006-04-28T15:26:00.000-04:00

There's an interesting kind of group called a cyclic group. Cyclic groups are interesting buggers: they express the symmetry of rotation in 2 dimensions, and the symmetric properties of addition in integers. They even tie together the idea of an exponential power series with the basic structure of the integers.

So what is a cyclic group?

A cyclic group of size N (often written Z_N) is a set of N values with a "circular" relationship. The reason for the scare-quotes is that there is an infinite cyclic group, which doesn't close - it's the set of integers. If the cyclic group is finite, then you can see it as a circle of values. You can draw a cyclic group very easily: here's the cyclic group of size 5:

To really explain what a cyclic group is, we can formulate it in two ways: modulo arithmetic, and power series. They're quite different formulations at first glance, but they are entirely isomorphic, and the correspondance is quite easy to see.

Cyclic Groups as Modulo-Arithmetics

The first way is something called modulo arithmetic. Modulo arithmetic a kind of arithmetic that uses a finite number of positive integers. For each positive integer N, there is a modulo N arithmetic (sometimes called modN for short). In modN, N=0=identity; if you add two numbers in modN, and the result is greater than N-1, you wrap back around zero.

Since that sounds confusing, here are a few examples in mod5:


1+2=3
2+2=4
2+3=0 (2+3 = 5 in non-modulo; in mod5, it wraps back to 0)
3+3=1 (3+3 = 6 in non-modulo; in mod5, it's 3+2+1=0+1=1)
4+4=3 (4+4=8 in non-modulo; in mod5, it's 4+1+3=0+3=3)

Another way of thinking of modulo-N arithmetic is that after every addition, you do an integer divide by N, and take the remainder. The remainder is the result in modulo arithmetic.

And finally, the easiest way to think of modulo-N arithmetic: remember the idea of a number line from elementary school? Take the number line starting at zero. Cut it at N. Take what's left, and curl it around so that it forms a circle.

Just like you can do addition by stepping on the number line (3+4 is start on three, and take four steps forward), you can do addition by stepping around the modulo-N number circle: 3+4 is start on 3, and take four steps forward along the circle.

Cyclic Groups as Generated Power Series

The other way of viewing a cyclic groups is as a power series generated by a single value. For a number X, there is a cyclic group of size N whose values are X^0 (the identity value), X^1, X^2, X^3, ... , X^(N-1). (note: this was corrected based on comments: the last entry was originally X^N, which is a group of size N+1, not N.)

The group operator in this formulation is basically just multiplication; the identity is thus X^0. The one little catch is: if we're looking at a finite cyclic group, then the multiplication operation "rolls back" in a manner exactly like modulo arithmetic. Again, it will get clearer with some examples. For a cyclic group of size 5:


N^0 * N^4 = N^4
N^3 * N^1 = N^4
N^3 * N^3 = N^1 (N^3*N^3 = N^6, which "rolls over" to N^1.)
N^4 * N^3 = N^2 (N^3*N^4 = N^7 which rolls over to N^2.)

As you can see, if you look at the members in terms of exponents, then the multiplication operation behaves as modulo arithmetic on the exponents.

Cyclic Groups and Rotational Symmetry

If you look at my corrected explanation of group operations from the other day, you should be able to see how a cyclic group expresses rotational symmetries. For example, if you take a set of the vertices of a pentagon, and look at Z_5 as a group operation, then the values in Z5 correspond to the five possible symmetric rotations of the pentagon. For example, the member of Z_5 labeled as "1" in the diagram above is the permutation function:


{v1->v2, v2->v3, v3->v4, v4->v5, v5->v1}.

Concluding Note

Today's going to be my last post on group theory for a while. There's plenty more to say about it, but group theory isn't my specialty, and since the next couple of weeks are going to be very busy for me, both at work and at home, so I'm not going to have the time to write about something that requires so much background reading. So I'll be moving on to other things for a while after today, and I'll get back to more group theory at some point.

Britain has a very cool judge

2006-04-27T09:50:00.000-04:00

Just saw this over on slashdot and BBC news:

As you may have heard, the author of the dreadful book "The DaVinci Codes" was sued in a British court for plagiarism of an earlier non-fiction book. The judge who wrote the ruling on the case embedded an encrypted message into the decision, by italicising letters scattered through the text.

I haven't seen the solution yet; according to Slashdot, the italicized letters in the judgement are (corrected from my original post, which already contained a correction from the original slashdot posting): "smithycodeJaeiextostpsacgreamqwfkadpmqv". (Thanks to the anonymous commenter who pointed out the missing "v".)

I doubt that I'll have time to look at this before someone comes up with a solution, but I thought the people who read this blog might be interested in this little puzzler.

Groups, Subgroups, and Group Actions, Oh my! (REVISED)

2006-04-26T21:18:00.000-04:00

Sorry for the bad title. While I was working on this, it popped into my head, and it won't go away. If I'm going to go crazy hearing that in my head, you can too.

Today's a bit of a definition day. To be able to really show how some of the stuff I've talked about informally works, you need to know some terminology. Don't worry - it's not entirely dull! (I'm also rather overtired this evening, so don't be surprised if some typos slip through; please let me know if you notice any.)

(Update: as the comment above indicated, I originally wrote this in a hurry while overtired. This was a very bad idea. As a result, it has been substantially rewritten to fix it up.)

Subgroups

I've mentioned subgroups briefly once or twice; it's worth pulling it out and making it first class here.

A subgroup S of a group G is a group with the same group operator as G, and whose members are a subset of the members of G. Because the subgroup is also a group, that means that it needs to be closed under the group operation and inverse. To be precise:

A group S is a subgroup of G iff:


 members(S) subset members(G)
 all x,y in S : x*y in S
 all x in S : x^-1 in S

There is a particular kind of subgroup that is interesting, called a normal subgroup. A subgroup S of a group G is a normal subgroup of G if/f:


 all x in G : (all y in S : x * y * x^-1 in S)

Another way of writing that is:


all x in G : x * S * x^-1 is a subset of S

It happens to be provable for normal subgroups that the "is a subset of" up there can actually be replaced by "=".

A group is an Abelian Group if/f the group operator is commutative:


all x,y in G : x * y = y * x

If a group is abelian, then all of its subgroups are normal.

A trivial group is a group containing only the identity value.

A simple group is a group whose only normal subgroups are the trivial group and the group itself.

Group actions

We're getting closer to being able to talk about the fun stuff. But we need to talk about group actions.

A group action is something that you can create by treating the members of the group as mappings. The way that you can do this is related to the symmetric groups.

The other day, when I talked about the symmetric groups. I defined the symmetric group of order N as a group over the integers from 1 to N. You can also define the symmetric groups in another way: the symmetric group over a set A is the set of all permutations of the members of the set. The symmetric group over a set A is written S_{A} The two are just different ways of expressing the same basic thing: the group of all permutations over a set of values.

Now, also remember that every group is isomorphic to a subgroup of some symmetry group. What this means is that given an appropriate set A, any group is equivalent to a permutation group over the set. Each member of the group is a function mapping A to A. The group action of a group G is a homomorphism from G to the symmetric group over A, S_{A}.

If you have a group G and a set A, then a group action of G on A is a function f such that:

all g,h in G : (all a in A : f(g*h,a) = f(g,f(h,a)))
all a in A : f(1,a) = a. (where 1 is the group identity element).

That's really a hairy way of saying:

There's a mapping from elements of the group to functions over the set;
Performing the group operation on the elements of set according to the mapping applies a symmetric transformation to the set.

Remember when I talked about the symmetries of a pentagon? Rotation, mirroring, etc. Well - for each of those symmetries, there is a group whose operation defines the particular kind of symmetry; and we can define the symmetry on the pentagon figure by applying the group to the set of vertices of the pentagon. For example, there's one group which describes rotational symmetries; for a pentagon, it's a cyclic group (I'll talk about what cyclic groups are later) with 5 elements; each element corresponds to one of the five possible symmetric rotations of the pentagon.

Dembski and Displacement

2006-04-25T10:05:00.000-04:00

I've been requested to comment on a relatively recent paper by Dembski,
Searching Large Spaces : Displacement and the No Free Lunch Regress, in which he essentially attempts to use his "No Free Lunch" theorem to show that something like evolution requires an intelligent guide.

Frankly, I'm pretty tired of talking about Dembski; but I think this paper is interesting in a few ways: it's blatantly dishonest in a way that's unusual even for Dembski; it demonstrates some classic creationist misdirections; and it demonstrates what the ultimate point of NFL is for Dembski.

The Blatant Dishonesty: Uniformity

As usual, Dembski is using his No Free Lunch (NFL) theorems as a way of arguing that evolution couldn't possibly have produced life as it exists on earth. But it's got the same problem as all of this other NFL stuff; in fact, it's got the same problem in an even more extreme form. Dembski's argument models evolution as a search function; and it treats the search space as perfectly uniform.

Yeah, if you've got a perfectly uniform search space, and you want to search it with a fixed search function, then guess what: the probability of your search finding its target is damn poor. Yippee. Not exactly a profound statement.

The "novelty" of this paper is that it also considers various kinds of meta-searches: that is, searches where instead of just choosing a search function, you use a search to find a search function well-suited to the search space.

Guess what? If you've got a uniform search space, then searching for a good search function that can find the target doesn't work well: the probability of finding a search function that will find the target even lower than the probability of a random search function finding the target. Going blindly meta on the search isn't better than just doing a blind search; in fact, it's worse.

This is not a profound result.

But the real problem here, the real fundamental dishonesty, is that Dembski continues to use a deliberately ridiculous model - one whose errors have been pointed out to him numerous times, and which he continues to ignore. He models evolution as a search for a specific target in a uniform search space using a single fixed search function. His concession to the criticisms of this model is to allow the search function to be stochastic - which is really no concession at all. (A stochastic search function doesn't pick a direction for the next step of the search; it assigns probabilities to the various directions that you could progress in, where the probabilities are its guesses about how likely you are to find the target in that direction.

Evolution is not a search using a fixed search function over an arbitrary uniform space. The search space is not uniform; the "search function" is not fixed; there is no specific target. It's the same old nonsense: if you create a model of the evolutionary process which eliminates the properties that make evolution work, then you can use that model to show that evolution doesn't work.

Dembski even pulls out that favorite creationist canard: the old "probability of a protein 100 amino acids in length". Dembski knows full well that this is garbage - it's been pointed out to him numerous times. But he doesn't let that stop him - and it's a perfect demonstration of exactly what's wrong with his entire argument:

Take the search for a very modest protein, one that is, say, 100 amino acids in length (most proteins are at least 250 to 300 amino acids in length). The space of all possible protein sequences that are 100 amino acids in length has size 20^100, or approximately 1.27x10^130.

No process in evolution searches for a specific protein. Not every chain of amino acids is even possible. The "probability space" of protein chains is very non-uniform: because of geometric constraints, some chains are very likely; some are very unlikely; and some are impossible. So if you want to model a search for a protein, the search space is not a search for 1 in 20^100; it's a search for some protein which is suited to some purpose (which is likely a family of similar proteins) in a non-uniform search space in which some things are far more likely to appear than others.

This is exactly the problem with all of Dembski's NFL arguments: the insistence for uniform search spaces; the insistence on a single fixed target; and the insistence on a single fixed search function.

Misdirections

The fundamental point of this paper is to try to turn NFL into some kind of support for intelligent design: it wants to argue that blind searches can't work, and that directed searches can work, but only if they have intelligent guidance.

It's a total misdirection. He's structured things so that no search can work unless you know how to get to the target in advance, and then argues that you can't get to the target unless you know it in advance. Phrased in simple english, this is incredibly obvious. But Dembski plays the standard trick of creationists: dazzle you with so much verbose nonsense and impressive-looking math that the tautological nature of the basic argument is hidden.

Here's an example:

What the heck does this mess say? If you used a meta-search to add information to a search function, then you used a meta-search to add information to a search function.

The Point: Dembski's Agenda

This paper is by far the clearest demonstration of exactly what the point of all of Dembski's NFL stuff is about. Dembski wants to argue for intelligent design. He's trying to create a mathematical argument for why there must be an intelligent guide for evolution to work. His agenda for this is to argue that first, there's no way that simple unguided evolution can possibly work. That's the basic NFL stuff. This paper augments that: it tries to show that it can work if the process is guided - but only if the guide has the property that its guidance adds information to a search through its guidance; and finally, he wants to argue that no random process can create a "guide" for search that adds information - the guide must be an intelligent being.

It's intelligent design expressed through mathematical misdirection. By carefully structuring things, and throwing lots of math around, he builds the assumption that an intelligent designer is needed into his framework, and then uses that framework to show that an intelligent designer is needed.

Permutations and Symmetry Groups

2006-04-24T20:46:00.000-04:00

One group that's particularly interesting to CS guys like me is called the symmetric group. The symmetric group is, in one view, the first step towards something called Category Theory, which has become very trendy in theoretical CS circles lately.

There isn't one symmetric group; the symmetric groups are finite groups, and for any given size N, there is a symmetric group of that size, called the symmetric group of degree N.

Symmetric groups are the "master" groups of something called permutation groups. Permutation groups are groups whose members are mappings between elements of sets of size N.

Just as a reminder: permutations are rearrangements of a set. The permutations of a set S are every ordering of all of the members of S. The number of permutations of a set of size S is S! (the factorial of S).

There are two ways of looking at a permutation group. One is sort of what you might expect from the name: for a permutation group over the set of numbers from 1 to N, the possible members are all of the ways you can re-order the numbers. For example, if you've got the set of integers from 1 to 3, the possible members of the permutation groups are:

{ (1->1, 2->2, 3->3), (1->1, 2->3, 3->2), (1->2, 2->1, 3->3), (1->2, 2->3, 3->1), (1->3, 2->1, 3->2), and (1->3, 2->2, 3->1) }

The other way of looking at the possible values in a permutation group over 1 to N is as the set of all total, one-to-one functions from (1..N) to (1..N). If you look at that list up above, it does include every possible total one-to-one function from {1, 2, 3} to {1, 2, 3}.

The set of pemutation values become a group when we assign the group operation, and show that it has identity elements and inverses.

The group operation is straightforward: composition of the permutations. I think it's easiest to understand that if you think of the group members as functions; then the operator is just function composition: given two members f(x) and g(x), then f*g = f(g(x)).

So, for example, let's look at two members, F=(1->2,2->3,3->1) and G=(1->1,2->3,3->2).

G(1)=1; F(1)=2, so F*G(1)=2.
G(2)=3; F(3)=1, so F*G(2)=1.
G(3)=2; F(2)=3, so F*G(3)=3.

So the composition F*G=(1->2,2->1,3->3).

The identity value should be pretty obvious - it's the identity function, which for all i maps i -> i. So for a the permutation group of order 3, the identity value is {(1->1),(2->2),(3->3)}.
And finally, inverses: just reverse the direction of the arrows in the mappings: for example, the inverse of (1->3,2->1,3->2) is (3->1,1->2,2->3), which can also be written (1->2,2->3,3->1) - and which is one of the members of the group.

The symmetric group of degree N is the permutation group containing all of the possible permutations over 1..N.

The symmetric group has a lot of really interesting properties. This is getting long, so for today, I'll just mention one really amazing one: every finite group is isomorphic to a subgroup of a symmetric group. (To remind you: a subgroup of a group G is a group whose members are a subset of the members of G.) The symmetric groups are a supergroup of every finite group!

That's exactly why they're so important: every possible symmetry property of a finite group is embedded in the structure of the symmetric group!

(Note: this post was corrected to remove a terminology error pointed out by poster Ivan M. I originally erroneously used the term "symmetry group" for "symmetric group". The error was a mistake dating all the way back to my group theory notebook from school! Thanks, Ivan, for catching it and being persistent about correcting me.)

A Sunday Snack: Finishing Up the PEAR

2006-04-23T13:18:00.000-04:00

Finishing up on other incomplete stuff, I started discussing the PEAR survey paper. As a quick reminder, PEAR is a group at Princeton University that is studying "the interaction of human consciousness with sensitive physical devices, systems, and processes common to contemporary engineering practice". There's not a huge amount to say about the rest of it, but there are a few good points worth taking the time to discuss.

Overall, the problem with PEARs publications as a whole is that they've gathered a huge amount of data, which contains no statistically significant anomalies of any kind. But they keep trying to show how various properties of their data, despite being statistically insignificant, show anomalous features. This is a totally meaningless thing to do: any set of data, if you slice and dice it enough, will contain subsets that have apparently anomalous features; the whole point of statistical significance is that it's a way of measuring whether or not apparent trends in the data are strong enough to be considered as more than just random patterning or noise.

Section 3C is typical. Here's what they say in the introduction to the section:

Any structural details of the trial count distributions that compound to the observed anomalous mean shifts may hold useful implications for modeling such correlations. While no statistically significant departures of the variance, skew, kurtosis, or higher moments from the appropriate chance values appear in the overall data, regular patterns of certain finer scale features can be discerned.

This is an incredibly damning statement. Translated into simple english: there is nothing statistically significant in this data to indicate anything other than randomness. But by taking carefully selected subsets, we can discover interesting patterns.

Let me give an extreme example of what this means, in practice. If I take a set of data containing random numbers, and I slice it so that it contains only multiples of two and three, then I'll find that my data contains a subset which has an anomalously high proportion of even numbers. Is it a meaningful anomaly? Only in the sense that I selected the subset with the property that interested me - I created the anomaly by my data selection - the "anomaly" is a property of my selection process, not of the underlying data.

Section 3D is more of exactly the same thing:

Given the correlation of operator intentions with the anomalous mean shifts, it is reasonable to search the data for operator-specific features that might establish some pattern of individual operator contributions to the overall results. Unfortunately, quantitative statistical assessment of these is complicated by the unavoidably wide disparity among the operator database sizes, and by the small signal-to-noise ratio of the raw data, leaving graphical and analytical representations of the distribution of individual operator effects only marginally enlightening.

This is interesting for a couple of reasons. First - this is the most direct admission thus far in the paper of how thoroughly invalid their data is. They're combining results from signicantly different experimental protocols: some of the testers have done significantly more experiments with the apparatus than others; but the results are intermixed as if it was all consistent data.

Second, they're openly admitting that the data is invalid, and that any conclusions drawn from it are pretty much meaningless because of the problems in the data - but they're going to proceed to draw conclusions anyway, even though in their best assessment, the results can be only "marginally enlightening". (And even that is a ridiculous overstatement. "Meaningless" is the correct term.)

Section four starts with another thoroughly amusing statement:

Possible secondary correlations of effect sizes with a host of technical, psychological, and environmental factors, e.g. the type of random source; the distance of the operator from the machine; operator gender; two or more operators attempting the task together; feedback modes; the rate of bit generation; the number of bits sampled per trial; the number of trials comprising a run or series; the volitional/instructed protocol options; the degree of operator experience; and others have been explored to various extents within the course of these experiments, and in many other related studies not discussed here. Very briefly, qualitative inspection of these data, along with a comprehensive analysis of variance [40], indicates that most of these factors do not consistently alter the character or scale of the combined operator effects from those outlined above, although some may be important in certain individual operator performance patterns.

De-obfuscated, that translates to: "Pretty much every property of the experiment has been varied in all sorts of ways; the results of the experiment have been shown to be statistically insignificant; and then when we tried to piece out single factors as influencing the results, we couldn't find anything statistically significant."

One last quote, and I'll be done with PEAR once and for all. PEAR has been frequently criticized by, among others, James Randi (aka the Amazing Randi) for the bogosity of their experiments. One of the recurring criticisms is, quite appropriately, the replicability of the experiment: that is, can they reproduce these kinds of supposedly anomalous results in a controlled trial set up and observed by someone outside of PEAR?

Here's their response:

From time to time, the experiments reported here have been assessed, both formally and informally, by a number of critical observers, who have generally agreed that the equipment, protocols, and data processing are sound [49]. Frequently, however, the caveat is added that such results must be “replicated” before they can be fully accepted, with the replication criteria variously defined to require strict preservation of all technical and procedural details, or to allow more flexible similarities in equipment and protocols. It is our opinion that for experiments of this sort, involving as they clearly do substantial psychological factors and therefore both individual and collective statistical behaviors, to require that any given operator, on any given day, should produce identical results, or that any given operator group should quantitatively replicate the results of any other, is clearly unreasonable. Rather more apt would be such criteria as might be applied to controlled experiments in human creativity, perception, learning, or athletic achievement, where broad statistical ranges of individual and collective performance must be anticipated, and results therefore interpreted in statistically generic terms.

"We can't reproduce our results, because that would be unfair."

Of course, people have done carefully controlled trials of perception, learning, and athletic achievement, with reproduceable results. (I don't know of any in creativity, but that's because I don't know of any definition of "creativity" that's sufficiently quantifiable to be measured.) But hey, PEAR doesn't let that stand in their way. It's just unreasonable to ask them to be able to reproduce them.

Misc: Answering Questions and Sources

2006-04-23T10:17:00.000-04:00

There's a bunch of questions that I've been asked about the group theory stuff I've been talking about lately. Since things are always slow on the weekend, I thought it would be a good time to go through and answer.

I also just want to take a moment and say thanks to all of the people who are reading the blog, and who've sent me kind words about how much they enjoy it. I can't tell you how happy I am that people are enjoying my writing. I'm having a great time writing this, and it really means a lot to me that people are enjoying reading it. So thank you all!

Onto? What's that? When I was defining transformations of groups, I used a bunch of terms "onto", "total", "one-to-one", etc. Lots of people didn't know the terms - and they're right, I should have defined them. So here we go:

Total/Partial: a function from A to B is total if f(a) is defined for all members of A. It's partial if there are members of A for which f(a) is not defined.
Onto: a function from A to B is onto if for every member b of B, there is at least one member of A where f(a)=b. It's basically the reverse of total. An onto function is also called a surjection.
One-to-one: a function from A to B is one-to-one if every member of A maps to one member of B; and no member of B is mapped to by more than one member of A. Note that in this definition of one-to-one, the function does not need to be onto. (Some definitions of "one-to-one" require that the function be onto; that's not the way I was taught.) By this definition, a one-to-one function is also called an injection.

Symmetry means reflection around a mirror. Shouldn't you use a different term? A lot of people have asked this. The thing is, symmetry doesn't mean reflection around a mirror. That's the simplest common example of it, but the term symmetry does mean much more than just "unchanged by reflection". I know that most english dictionaries definitions are, unfortunately, the reflective definition, because that's the common usage. But the origin of the word in greek, and it's use in mathematics is broader than that. Mathematicians use the word in it's broader sense, and if I were to use a different term for it on my blog, all I'd do is end up confusing things, because every other mathematician in the world will continue to use the word symmetry.
Why aren't you using MathML? After all of the discussion about whether or not to use MathML, I've ended up not using it, at least not for now. After experimenting with some tools for it, I've found that Blogger is very unfriendly to MathML. I really appreciate the fact that Blogger is free and all, but it's very frustrating at times. The only way I've found to make MathML work would require me to change a blogger setting which, in turn, would require me to go back and reformat all of the earlier posts to blog, or they'd become illegible.
What are your sources? For the group theory stuff, I'm using my old class notes, Wolfram's Mathworld, and Wikipedia. In particular, Mathworld is a really fun source - there's a ton of great stuff up there. The writing quality varies from mediocre to fantastic; the group theory stuff tends towards the mediocre, but it's thorough, so it makes a good reference, if not a good place to go to learn the material.

I've also been reading "The Equation that Couldn't be Solved" by Livio; lots of people think it's a great book. Personally, I find it a very frustrating read; Livio tries to write like Hofstadter or Gardner, with a lot of places where it goes off on semi-related tangents. When Hofstadter does that, I tend to enjoy it; his tangents are interesting and relevant. I find that Livio's tangents are often too unrelated to the basic material. I think it's mostly a matter of personal taste, but I find Livio a very difficult read; I can't get myself to read more than a few pages at a sitting. (Whereas when I read, say, Brian Greene, I read 50 pages at a sitting.) Given how many people seem to really love the book, if you're interested in this kind of stuff, it's probably worth getting a copy and reading; but it's not like "Godel, Escher, Bach" where I think it's an absolute essential to have in your library.
When are you going to write about X? I'm amazed and flattered how many mails like this I've gotten. People have asked me to write about topography, recursive function theory, language families, rings, set theory, discrete vs continuous math, statistics, music theory, and more. My only answer is: give me a chance! Please do keep sending requests for what you'd be interested in seeing on the blog; I'll do my best to get to it all. The more requests I get for a topic, the sooner I'll get to it. But please be patient!
Can I reprint articles from your blog? As long as it's not for profit, sure, as long as you put in an attribution identifying where you got it, and don't edit it other than for formatting. If you want to edit it, or you want to include it in something where you're going to charge for copies, get in touch with me by email, and we can talk about it.

Mind-numbingly stupid math

2006-04-21T15:18:00.000-04:00

An alert reader just forwarded me a link to this mind-bogglingly stupid article. This is one of the dumbest pseudo-mathematical arguments that I've ever seen - and that's a mighty strong statement. This Oxford University Professor! argues that he can mathematically prove the resurrection of Jesus. Get a load of this:

This stunning conclusion was made based on a series of complex calculations grounded in the following logic:
(1) The probably of God's existence is one in two. That is, God either exists or doesn't.
(2) The probability that God became incarnate, that is embodied in human form, is also one in two.
(3) The evidence for God's existence is an argument for the resurrection.
(4) The chance of Christ's resurrection not being reported by the gospels has a probability of one in 10.
(5) Considering all these factors together, there is a one in 1,000 chance that the resurrection is not true.

Where to start with shredding this? Is it even worth the effort?

By a similar argument, I can say that probability of pink winged monkeys flying out of my butt is one in two: that is, either they will fly out of my butt, or they won't. The probability that those monkeys will fly to the home of this Oxford professor and pelt it with their feces is one in two. If pink winged monkeys fly out of my butt, that's an argument for the likelyhood of a fecal attack on his home by flying pink monkeys.

Do I really need to continue this? I don't think so; I'd better go stock up on monkey food in my bathroom.

Group Isomorphism: Defining Symmetry Transformations

2006-04-21T14:57:00.000-04:00

Yesterday, I explained the idea of multiple kinds of symmetry intuitively, by describing symmetry as immunity to transformation. Today I'm going to try to explain what, in group theory transformation means, and how symmetry is defined in terms of transformation.

What it comes down to is a concept called group isomorphism.

Group Homomorphisms and Isomorphisms

Before I can describe a group isomorphism, I need to explain a group homomorphism. A homomorphism between two groups A and B is a function that maps members of A to members of B in a way that preserves the group property.

So - suppose we have group A, and we call its operation "+"; and we have a group B, and we call its operation "*". A function f from A to B (written f : A -> B) is a homomorphism if and only if:

   all x,y in A : f(x+y) = f(x)*f(y)

So a homomorphism is a mapping in one direction from A to B. It guarantees that for every element of A, we can map it onto an element of B; and that that mapping is guaranteed to preserve the group property on the mapped elements.

What do I mean by the group property is preserved? Mostly that the statement up above is true: all x,y in A: f(x+y) =f(x)*f(y). But that implies a couple of important things:

(1) f maps the identity element of A onto the identity element of B: f(1_A) = 1_B.
(2) f's mapping preserves inverses: f(x^-1) = f(x)^-1.

A homomorphism does not have to be a total function onto B - meaning that non every member of B has an element of A mapped onto it. It does not have to be one-to-one, meaning that multiple elements of A could be mapped onto a single element of B, so long as the group property was preserved.

A group isomorphism is a group homomorphism f, where f is a bijection. That means that f maps each element of A onto exactly one element of B; and every element of B is mapped to by exactly one element of A. (Another way of saying that is f : A -> B is total, one-to-one, and onto.)

If f : A -> B is a group isomorphism, then it describes a symmetric transformation from group A to group B. If we take a set of values from A; and we map each of those values to B using f, we get as a result a set which is equivalent or indistinguishable from the original set.

Permutation Symmetry

One particularly interesting kind of symmetry is called permutation symmetry. Permutation symmetry is a kind of symmetry created by a group isomorphism from a group to itself. Reflection symmetry between the real numbers is a permutation symmetry: it is a total, one to one, onto map from all real values (omitting zero) to all real values (omitting zero) which preserves the group property of multiplication.

The rotational symmetry of a pentagon is also a permutation symmetry; if we label the five vertices of the pentagon as A, B, C, D, and E, then the function: { (A->B), (B->C), (C->D), (D->E), (E->A) } is an isomorphism; when you apply it, you rotate the pentagon (or the labeling of the pentagon), but you end up with a pentagon that is indistinguishable from the one you started with.

Friday Random Ten 4/21

2006-04-21T09:09:00.000-04:00

Steven Reich and Maya Beiser: Cello Counterpoint. A truly amazing modern classical composition by Steven Reich, played by Maya Beiser. Beiser is tracked 16 times on this: she's the only performer, but there are 16 different parts overlayed. This is a seriously spectacular piece of music. I love Reich as a composer, and I think this is one of his finest short works. Just wow.
The Flower Kings, Monkey Business. Neo-progressive rock, by a great band. Definitely not for people with no patience - FK songs tend to average around 15 minutes each.
Harry Bradley, The Merrymaker's Club/The Acrobat. My favorite Irish flutist.
Dave Matthew Band, Don't Drink the Water. DMB with Bela Fleck on banjo. What more could you ask?
Continental Divide, Andersonville March. Very traditional bluegrass from a great, unfortunately defunct band. Scott Vestal on banjo - Vestal is one of the true greats on the banjo; the man can play anything from Yes to Bach to Scruggs. I don't care for the singer in CD (or in fact nearly any bluegrass vocalist), but this tune is instrumental.
Broadside Electric, Babylon. A truly gruesome old folksong about a robber who accidentally murders his own sisters. Broadside is a great local band (NY/Philadelphia area) with a particular fondness for gruesome ballads.
Deanta, Ready for the Storm. Beautiful song from a great Irish band.
Miles Davis, Well You Needn't. I am not worthy to comment on Miles Davis.
Steven Hackett, Man Overboard. Latest work by the great guitarist from the old days of Genesis. Good, but not great.
King Crimson, Starless. Very old KC, from the "Red" album. Proof that a guitar solo doesn't need to have a lot of notes to be amazing.

Group Theory 3: Expanding on Symmetry

2006-04-20T19:17:00.000-04:00

Yesterday, I talked about the basic intuitive idea of what symmetry means. Today, I'm going to try to take it a bit further. I will eventually get to the point of explaining how groups express this; but this stuff really fried my brain the first time I saw it, so I'm trying to take small steps, with as much intuition as I can muster at each step.

Intuitively, when we talk about symmetry, we think about reflection - like we could pick out a line, or a plane, and switch things around the sides of it. In normal english usage, that's all that symmetry means: reflective symmetry around a line or plane. The standard real number multiplication symmetry fits that nicely: it's reflective symmetry around the line "x=y".

In math, and in group theory in particular (since group theory is what defines symmetry), symmetry means something more than that. Mathematically, symmetry means something more like "immunity to transformation" - where the exact transformation could be almost anything. Immunity to transformation means that after the transformation is applied, there is no way to distinguish between before and after the transformation.

The familiar symmetry, reflective symmetry, means that if you mirror-reflect what's on each side of the line, and switch it to the other side of the line, you'll end up with something indistinguishable from what you started with.

There are other kinds of symmetry, which mean that you can do some other kind of transformation without having any distinguishable effect.

Translational symmetry means that something can be moved in some way without having any distinguishable effect; rotational symmetry means that something can be rotated in some way without having and distinguishable effect.

For example, if you have an infinite sheet of graph paper, and you move it one square in any direction, you can't tell that you moved it: it is symmetric with respect to translation by integral unit translations.

If you have a pentagon, you can reflect it five along five different lines:

You can also rotate it; it has rotational symmetry around the angles produced by the five reflective symmetry lines:

Finally, a particularly cool example: this Escher image has six reflective symmetries; 3 rotational symmetries; translational symmetries in 8 directions,
and a 3-way reflective symmetry (meaning you can divide it into three sections and mirror-swap each section separately). Instead of marring such a beautiful image, I'll leave it alone and let you puzzle those out.

The Bad Math of Paranormal Research: PEAR

2006-04-18T21:12:00.000-04:00

Reading some stuff on Orac's site, I discovered a website run by a professor at Princeton who runs a lab called the "Princeton Engineering Anomalies Research Center", aka PEAR. They're part of the department of Engineering and Applied Science at Princeton. As a Rutgers alumni, I've always been loyally snooty about Princeton engineering; but I never would have dreamed that garbage like this would fly there.

What PEAR studies is allegedly how human beings can influence random number generators. Their experiments consist of a fairly elaborate rig that generates a random sequence; the subject have no physical access to the generator, but tries to influence the "direction" of the random numbers generated, either up or down. I'm looking at one of their papers: a review of 12 years of experiements with this experimental apparatus.

It's an interesting example of bad math, because it's quite subtle. There are, of course, warning signs even from the beginning that the authors are crackpots. One of the common warning signs that the authors know that they're doing nonsense is when they start the paper with a long list of famous people (usually dead) who allegedly support their ideas. This one starts with a list of eighteen people who they allege supported their ideas, ranging from Francis Bacon to Einstein. They even include an alleged conversation between Einstein and an unnamed "important theoretical physicist" about how paranormal powers were a legitimate area of study in physics.

After a detailed description of their experimental apparatus and testing protocol, they finally get the alleged math.

There's a couple of tricks that they pull right away as they get into the math. They have 91 different test subjects; 522 test series; and close to 2 1/2 million "trials". This is intended to give an appearance of a fair, balanced study; but later in the paper, it becomes clear that the different operators ran different numbers of tests in somewhat different settings. They do not indicate how the trials were selected, how they were distributed among the subjects, or whether these are the only subjects that every did the experiment. This is absolutely unacceptable - in statistical mathematics, ensuring fair samples is critical.

Next, we come to a table presenting a summary of their results; I had to flip back and forth between the page with the table and the previous page at least half a dozen times, making notes, in order to be able to make any sense out of this table. While I can't prove it, I strongly suspect that this obfuscatory presentation of data is quite deliberate: it's a classic bad math maneuver: dazzle the readers with lots of complicated looking numbers, equations, and tables, in order to give them the idea that there's a depth to your analysis that isn't really there. This really is a dreadful way of presenting this information: there is not particularly complex data in this table - it's basically means and standard deviations for a fairly straightforward experiment protocol - but it manages to astonishingly confusing.

On the next page - we get a wonderful statement:

The anomalous correlations also manifest in the fraction of experimental series in which the terminal results confirm the intended directions. For example, 57% of the series display HI-LO score separations in the intended direction (zs = 3.15, ps = 8 * 10^-4). In contrast, the anomaly is not statistically evident in the 52% of individual operators producing databases in the intended directions (z0 = 0.31, p0 = 0.38), a feature having possible structural implications, as discussed below.

Yes, 57% of experiments, performed by 52% of the operators: this is an admission that the sample is biased!

And better "the anomaly is not statistically evident"; another way of saying that it's a statistically insignificant result. Yes, the fact that their results are not statistically significant is a feature "having possible structural implications". Pardon me, I need to go roll on the floor and giggle for a few minutes.

.
.
.

Ok. I'm better now. One last thing, and then I'm goint to take a break from this monstrosity. Here's a copy of their graph of the "cumulative deviation over time" of their trials:

Just take a look at that graph: the distance of the lines from the parabolic curve is the cumulative deviation. "HI" accumulates some deviation early, and then stays roughly parallel to the curve; baseline wanders all the heck over the place, ending up right on the upper branch of the curve; "LO" meanders around the curve, approximating it pretty well.

What does that tell us?

Absolutely nothing of value. The deviation of the baseline is extremely close to the deviation of "LO" - i.e., their deviations aren't significant. In fact, if their "HI" didn't have an early bump, which doesn't seem to persist very well, the curves would have been pretty much staying within the 95% confidence interval. (As a side note, if you take a look at their website, they have a whole bunch of different versions of that graph. Amazing how you can get different results by using different samples of your data, isn't it?)

The information they take from this graph is that the "anomalous correlations" - you know, the anomalous correlations that they admitted weren't statistically significant? - they amount to a shift of 10^-4/bit - or 1 bit in 10,000 deviating from the expected norm.

I'll have more to say about this crud later - because it's a fine example of how to use bad math to obscure bad work - but this is enough for now; I can only plow through so much slop in one session.

Group Theory: What is symmetry? Why do I care?

2006-04-18T15:50:00.000-04:00

When I started talking about group theory on monday, I said that ultimately, groups are a way of capturing symmetry: multiplication over the real numbers (if you omit zero) has an amazing symmetry about it, and group theory abstracts away the details of multiplication to home in on that symmetry concept.

The problem that a lot of non-mathematicians have when you talk about Groups is that it's kind of hard to grasp what that symmetry is, what it means, and why they should care. The list of applications that commenters came up with is impressive, and is a pretty compelling argument to me for why this stuff is interesting; but it's important to grasp the intuition behind the symmetry of groups before you can really get group theory.

So - what does symmetry mean?

Let's start by looking at multiplication. Think about multiplication with non-zero real numbers. Forget about the fact that we can add numbers - just focus on multiplication.

If I were to have you take the real numbers, and come up with some funny way of writing them, so that I don't know which numbers are which, and then you ask me to tell you which number is which, only by using multiplication and testing equality, would I be able to do it?

Well, I could certainly tell which number was 1: it's the only number where anytime I pick some other number and multiply it by one, I get the other number.

What else could I work out? Given enough time, could I figure out which number was two? Well, two is interesting in its way, because if I could figure out which numbers were integers, then I could recognize two because every other integer is a multiple of it - so if I tested enough numbers, I could at least make a pretty good guess which number was two - that is, if I could figure out which numbers were integers. But I can't do that - there's no way for me to tell the difference between an integer and any other real number.

Now, here's where it gets a bit subtle: Suppose I were to give you the integers from 1 to 1000, and their reciprocals. So you've got a bunch of numbers which you know are 1, 2, 1/2, 3, 1/3, 4, 1/4, 5, 1/5, 6, 1/6, etc, but you don't know which is which. Now, could you tell me which of them was the number 2?

The answer is no. You could narrow it down to being one of *two* numbers, and you could tell that those numbers were each others inverses - but you couldn't tell which was which. You can't tell apart 1/2 and 2 - because the group is symmetric around 1.

Think about it: how could you tell the difference between "x*y=z" where x=1/2, y=1/3, and z=1/6, and "x*y=z" where x=2, y=3, and z=6?

Or to be visual for a moment: look at this graph of the equation y=1/x in the first quadrant (that is, the part that we normally draw on the upper right, where x and y are both positive).

Without the axes being labeled, which is X and which is Y?

It doesn't matter - you can call either one X and the other one Y, and that's still the right graph. What that means goes beyond that one graph: any statement that you can make about numbers using only multiplication is also true if you replace every value with its reciprocal.

For a more concrete and practical example of this kind of symmetry: the symmetry property works in electronics. You can analyze a circuit two different ways: you can look at any circuit, work out what it does, what current, voltage, amperage, resistance, etc., exists at what point in the circuit; and you can do that under the assumption that the positive charges are moving, or that the negative charges are moving - and the answers will come out exactly the same. In fact, for years (and maybe even still now), electrical engineers were trained to do the computations with the assumption that it was the positive charge that moved! (It's a historical error".)

Symmetry is a fascinating property, which allows you to recognize similarities, and discover ways in which properties can't change even though they've been twisted around somehow.

Remember that great quote from Newman? "The theory of groups is a branch of mathematics in which one does something to something and then compares the results with the result of doing the same thing to something else, or something else to the same thing." Group theory lets you see the similarities between different things, or the ways in which things can't be different, by expressing the fundamental symmetries.

Some Applications of Group Theory, promoted from comments

2006-04-17T20:36:00.000-04:00

A bunch of people posted some really great descriptions of applications of group theory in the comments; I thought they were good enough that they deserved to be promoted to the front page.

Groups and Relativity

Blake Stacey wrote an excellent comment explaining how group theory applies in relativity.

Take two observers, Joe and Moe, who are watching some mechanical system -- say a star system with planets and moons spinning around -- and testing if the motions they see follow Newton's laws. To describe motion mathematically, they use coordinates, which might be the Cartesian x-y-z system: locate an object at a particular time by specifying how far it is above some plane, how far in front and how far to the left (with negative numbers to describe positions in the opposite directions).

Joe and Moe do not have to use the same coordinate systems to agree upon the laws of motion. If Moe is standing 10 million kilometers to Joe's left, say, then Moe's coordinates for each planet will be offset by that amount, but Moe will still see the motion as obeying Newton's laws. Likewise if Moe is turned with respect to Joe: a point which lies on Joe's x-axis will to Moe be some mixture of x and y, but the physical laws will be the same.

In Newtonian mechanics, it is even true that Joe and Moe can be in motion relative to each other. Joe believes he is standing still and sees Moe moving past with a constant speed in a straight line; Moe believes he is standing still and sees Joe going past in a straight line. Uniform motion in a straight line is indistinguishable from a state of rest, or put another way, there is no "gold standard" absolute state of rest from which all speeds should be measured. (Think of riding in an airplane on a smooth flight: when can you tell you're not sitting on the ground without looking outside?)

Einstein's revision of Newtonian mechanics says that the same principle holds true for all physical laws. Even if Joe and Moe try to determine who is "really" moving by measuring the speed of a light beam, they will measure the same speed, 300,000 km/s. One would expect that if Joe measures light going at 300,000 km/s and sees Moe flying past at 100,000 km/s, Moe will measure the light traveling at 200,000 km/s, but such is not the case.

This all comes down to group theory because we can consider these transformations -- translation by a fixed distance, rotation by an angle, movement at a uniform velocity -- as symmetry operations on the physical laws. Just like a vase or a starfish is symmetrical if we can rotate it around and it looks the same as it did before, a physical law is symmetrical if we can change the coordinates we use and it still takes the same form.

The magic buzzword to give a search engine is "Lorentz group".

In a very similar vein, an anonymous poster (email me if you want me to put your name here!) commented on how group theory within the framework of relativity explains the basic laws of conservation:

The interesting thing about the application of group theory to space time is that the conservation laws of physics can be shown to be equivalent to the invarience of physics under space time transformations. For example
1. conservation of angular momentum can be shown to be equivalent to the statement that the laws of physics are invarient under static rotations (the rotation group in three dimensions);
2. conservation of linear momentum can be shown to be ewuivalent to the statement that the laws of physics are invarient ulnder static space translations (the translation group in three dimensions);
3. conservation of energy can be shown to be equivalent to the statement that the laws of physics are invarient under static time translations (the one dimensional translation group).

Other Applications in Physics

Another nifty example of how group theory has been used in physics; eulerfx explains:

To mention an example of how group theory is used in particle physics, Paul Dirac discovered the existence of the positron through manipulation of complex valued matricies in the general linear group, GL.

Music Theory

Steve added some detail to my comment about how group theory can be applied to music theory:

The music theory applications center around mod-12 arithmetic. There are 12 notes in the chromatic scale & rather than refer to them as C, C# etc. they can be numbered 0 through 11. The two basic operations are then:

Transposition by n semitones: x + n (mod 12)

Inversion: 12 - X (mod 12)

All possible chords with n notes can be classified by sets where the notes are placed in the form that minimizes through the operations of transposition and inversion the sum of the intervals. If two chords can be made identical by either transposition or inversion they are considered identical. By this classification, for instance, there are 12 possible 3 note chords (interestingly enough, a major and minor triad are the same entity under this system)

Big thanks to you guys, and all of the other commenters!

Finite Groups and the Greatest Math Song Ever!

2006-04-17T20:10:00.000-04:00

I'm busy tonight, and in a strange mood, so I'm not going to say too much; but I need to get to one point, so that I can link to something wonderful.

So, yesterday, I posted an introduction to group theory.

Well, it turns out (naturally), that there are many groups with finite numbers of members. And they are, quite imaginatively, called finite groups. Most finite groups can be illustrated quite beautifully with a diagram, but that's a topic for another day.

Within a finite group, the number of elements in the group is called the order of the group. So, for example, a group with 10 elements is called a finite group of order 10.

There also a notion, too complex to really get into tonight, called a simple group. A simple group is, essentially, one that has a kind of minimality about it; its only normal subgroups (basically groups formed by subsets of the values in the group) are trivial. (Note: the word "normal" was originally omitted from this sentence, because I forgot that there are plenty of non-simple subgroups; only the normal ones need to be trivial. This error was pointed out by commenter Ivan M.)

So - the point of this: here is a link to the greatest a-capella math song of all time: Finite Simple Group of Order Two, by the Klein 4 at Northwestern University.

Yes, I am a dork.

Brain Development and Learning Math

2006-04-17T08:06:00.000-04:00

Just a quick pointer to something neat: there's an interesting article about how are brains are wired for doing mathematics over at MindHacks.

Fun Stuff: Group Theory (Corrected)

2006-04-16T20:07:00.000-04:00

One of the things that you can do in math that's really interesting is to play games with abstracting things. What I mean by that is that you can look at things that are part of everyday math, and strip them down to their bare essentials, and see what happens. Some fascinating theories have come out of this, and they're not just theoretical math - they have concrete, practical applications: mathematical structure is part of the world, and playing with abstraction is one way of seeing that.

In Algebra, one of the abstraction games that people like to play is called Group Theory, and I'm going to write a bunch of posts talking about it, because there's so many fascinating things hiding inside of it. Today, I'm just going to give you a very brief introduction; later in the week, I'll build on that.

Group theory comes from looking at the idea of multiplication, and asking: what are the real essential properties of multiplication? If I get rid of numbers, so that I'm just talking about multiplication as a bare operation, what are its essential properties?

What you wind up with is something called a group. A group Gis a set of values, along with a binary "multiplication" operation, which meets a set of properties, all of which should be familiar from working with multiplication on real numbers:

Closure: Closure says that for any two values a and b are in G, then their product "a * b" must be in G. In other words, there is no way that you can multiply any two values in G, and end up with a value that isn't in G.
Associativity: If a, b, and c are in G, then (a*b)*c = a*(b*c).
Identity: There is an element, "1" in G, such that for all a in G, a * 1 = a, and 1 * a = a.
Inverse: G contains an inverse (reciprocal) for each of its members. The inverse of an element "a" in G is written "a^-1"; and for all a, a * a^-1 = 1 and a^-1 * a = 1.

What this comes down to is that a group is a structured set of values that has an interesting kind of symmetry expressed in its multiplication operation.

An interesting to note is that group theory is an abstraction of a set with a multiplication operation; but the Real numbers with the normal real multiplication operation are not a group (because 0 breaks the identity and inverse properties); on the other hand, real numbers using the addition operation are a group!

A very famous mathematician, James Newman, who was particularly famous for writing books that explained mathematics to laymen, describe group theory in a wonderful way:

The theory of groups is a branch of mathematics in which one does something to something and then compares the results with the result of doing the same thing to something else, or something else to the same thing.

What kinds of things can be expressed as groups?

Music: There's a way of looking at music theory using groups: natural "operations" that occur in music and chords, like inversion, transposition, etc., all exhibit group symmetries.
Chemistry: you can determine the polarity of a molecule by using group theory to identify the symmetries in the structure of the molecule.
Physics: group theory is apparently used in special relativity, although I don't pretend to understand how.

(Update note: in the original version of this, I forgot that Group Theory does not assume that multiplication is commutative; I've corrected it since the error was pointed out in the comments.)

Q&A roundup: No Free Lunch

2006-04-14T14:06:00.000-04:00

I've been receiving a bunch of email over the last couple of weeks with similar questions about my critique of Dembski's "no free lunch". Rather than answering the emails individually, I've been gathering them up, and I'll try to answer the questions here.

What does "averaged over all landscapes" mean?

In a NFL setting, we're talking about doing something like a search over a landscape, where we have "fitness functions" which provide the search algorithm with its directions: the search moves in the direction that the fitness function tells it to.

One of the properties of the fitness functions is that they don't get to see the real landscape: their job is to try to approximate the landscape in a good way, so the search will wind up at a good destination.

When we average over all landscapes - what that means is that instead of considering how a particular fitness function matches a particular landscape, we're saying "Let's look at every possible landscape, and run the fitness function, and see what kind of results it gets".

NFL says that if we do that, that no matter how carefully we design the fitness function, it can't possibly do better than random for all landscapes. What this means is that if we don't know which landscape we're going to be confronted with, we can't pick a fitness function that's guaranteed to do well. This is interesting, for example, when applied to things like financial derivatives markets: if we don't have information about what the markets are going to do, then on average, we can't beat the market.
NFL works for operations research tasks; why doesn't it work for evolution?

Receiving multiple emails with this question surprised the heck out of me. It's an odd question, one which is both deep and shallow at the same time. I suspect that someone somewhere put folks up to asking this one as a response to my argument, but I have no proof of that. Anyway - on to the answer:

One of the key properties of NFL is that it uses blind fitness functions. That is, the fitness function doesn't get to change itself depending on what landscape you're running it on. The fitness function in NFL is also deterministic: for any point in the landscape, looking at where it can go next, it can only choose one path as the best.

Evolution is an adaptational process: modelled as a function, it's more like the learning functions in Case's computational learning theory than like the fitness functions in NFL; an evolutionary process doesn't have a fixed path built in to it; it doesn't even have a real fitness function built in to it. In effect, an evolutionary process is modifying its fitness function as it goes. The landscape that it traverses gets built into the function, so that the longer it runs, the more adapted to the landscape it gets.

Evolution is also not deterministic: it tries multiple paths. Remember that evolution is working on a species, not on individuals. Within a species, multiple adaptations can occur in different sub-populations. That is effectively trying multiple paths. In fact, that's exactly how speciation occurs: different subpopulations adapt to the environment in different ways.
NFL is a probability argument; why do you keep babbling about landscapes?

There are a lot of different ways that you can describe NFL-type problems; landscapes is the one I think is intuitively easiest. The idea of things like NFL is to look at a state-space with transitions, and see how algorithms can perform in different state spaces. You can describe that as a probability space, a landscape, a weighted graph, a state table, or any number of other things. The "probability" piece comes from comparing the fitness function (or fitness landscape, or whatever abstraction you choose) with the landscape it's supposed to by trying to fit. By doing that comparison, you can find the probability of a given type of fitness function performing well on a given type of landscape.
NFL doesn't say evolution can't do better than randomness; it says that evolution must have some knowledge of the landscape to do better than randomness. Where does evolution get that knowledge?

As I said above, NFL relies on deterministic, fixed fitness functions for searching landscapes. Evolution is effectively non-deterministic, because it tries multiple paths; the successful paths persist and keep going; the unsuccessful ones die out.

Non-determinism is a big deal. The ability to try multiple paths and keep the ones that work is an incredibly powerful notion - and that's exactly where evolution gets its ability to adapt and perform well in any fitness landscape. Mathematically, you can't model evolution as a fixed deterministic function; it's an adaptive non-deterministic one. And an adaptive non-deterministic algorithm will not fall into the NFL trap. (See the Case citation above for some great work about what non-deterministic adaptive functions can do.)

Friday Random Ten, April 14th

2006-04-14T08:49:00.000-04:00

Yes, it's friday again.

King Crimson, "Fallen Angel"
Porcupine Tree, ".3": an instrumental track by a fantastic, hard to categorize band. PT started as a joke, and has straddled the lines between neo-progressive, alt-rock, and pop.
Marillion, "Market Square Heroes". Very old track off of Marillion's first album. They sounded a lot like Genesis in those days.
Deanta, "The Party". Traditional Irish music from a wonderful band. What could be better than traditional Irish, with one of the best wooden flautists in the world (Deirdre Havlin), Irish lap harp, bouzouki, and bohdran?
Genesis, "In the Cage". A track off Genesis' "The Lamb Lays Down on Broadway", the magnum opus from the Peter Gabriel days.
Bela Fleck, "The Legend". Newgrass from one of the gods of newgrass banjo. Bela's truly an unbelievable musician - the guy can play anything on a five-string banjo. I've seen him live performing traditional old-school bluegrass, newgrass, bop jazz, classical, rock... There's just nothing the guy can't do with a banjo.
Yes, "Yours is No Disgrace". My iPod seems to like old prog-rock today.
Moxy Fruvous, "Spiderman". Moxy is a goofy canadian band which specializes in silly songs with four-part vocal harmony. This is their take-off on the theme to the old spiderman cartoon. Imagine that trashy song with lyrics like "Spidermans master plan, build his own little spider clan. In the woods, now they're troops, fighting for special interest groups".
Nightingale, "Ma Commere, Ma Mie / Retour De Montaignac". French canadian folk music from a wonderful three-part band. The singer for Nightingale, Keith Murphy, has one of the most beautiful quiet voices I've heard.
The Clogs, "Pitasi". The Clogs are impossible to classify. The music is mostly classical sounding, but with an improvisational edge, and bits of rock-style rythym mixed in. Definitely an acquired taste, but I like 'em.

Vaccines and Geniuses

2006-04-13T09:18:00.000-04:00

As Orac points out today, Vox Day, one of the most obnoxious assholes that I've encountered on the net, is an anti-vaccine guy, who's been using the recent outbreak of mumps in Iowa (discussed by Tara here) to argue that vaccines must not work.

It's quite sad in its way: Vox is a self-proclaimed genius and member of Mensa. And yet, this is typical of his idea of argument. The "math" is so poor that it's laughable, and the rest of the reasoning is no better.

So, here's Vox:

From the Star & Sickle:

A mumps vaccine was introduced in 1967. Iowa law requires schoolchildren to be vaccinated against measles and rubella, and the mumps vaccine is included in the same shot. The state's last major outbreak was in 1987, when 476 people were infected.

Of the 245 patients this year, at least 66 percent had had the recommended two-shot vaccination, while 14 percent had received one dose, the Public Health Department said.

"The vaccine is working," Quinlisk said. "The vaccine certainly was made to cover this particular strain, because it's a fairly common strain of mumps." Quinlisk said the vaccine overall is considered about 95 percent effective.

So, the question is this: if the vaccine, not improved hygiene or some other factor, is primarily responsible for preventing transmission of the disease it is supposed to prevent, how is it possible that 80 percent of the infected in this latest outbreak are at least partially vaccinated against it?

And isn't it at least somewhat doubt-inspiring that the health authorities continue to insist that the vaccine is working in the face of direct evidence that, at least in some cases, it is not?

So, Vox wants to argue that vaccines don't really work, because there's a mumps outbreak in Iowa. And 80% of the cases are people who received at least one dose of the MMR vaccine.

Let's look at some numbers, to get an idea of what the infection rates mean. We'll be charitable, and stack all of the numbers in Vox's favor - so whatever we come up with is going to make the infection rates seem much higher than they are.

So - let's start by coming up with an estimate of the number of people in the pool of potentially infectable. Playing the numbers in Vox's favor, we'll assume that all of the mumps cases came from people born in the same year. The birth rate in Iowa is is pretty consistent, acording to the official statistics: around 38,000/year. Of those, the number vaccinated is around 81%, again according to the official statistics. So, the pool of vaccinated people born in that year is around 30,700.

Now, the cited effectiveness rate of the MMR against mumps is 95%. What that number means is that 95% of the people who receive the vaccine will develop an effective immunity to mumps. So - the expected number of vaccinated people who would not be immune would be around 1500 people (rounding down).

There are 245 infections this year, according to the article Vox cited. That would mean that 15% of the non-immune population of vaccinated people had become infected. That's a damned high number, but not completely beyond reason for something as contagious as mumps.

But then, remember that all of the numbers are stacked heavily in favor of making the vaccines look bad: in particular, these numbers are based on reducing the pool of potential infectables by several orders of magnitude (because we assume all cases were born in the same year, and all of them were born in Iowa) - we find that the number of infections with mumps is entirely possible. It makes for a pretty serious outbreak for sure - but not something that calls into question the effectiveness of vaccines.

Now, to put the nail in the coffin: back to some official statistics. How many cases of mumps were there before vaccines became mandatory in Iowa? Official statistics are here: during the decade before mumps vaccines became mandatory in Iowa, the number of infections per year ranged from 2000 to 12000 per year. Now, during a dramatic outbreak, described as an epidemic, we've got a couple of hundred cases. Does that look to you like the vaccines are not working?

Nah. Me neither.