Okay, I'm back to post about confluence and the Church-Rosser property, as I threatened yesterday. This is a complaint about something I found very annoying when I was in graduate school; it's related to yesterday's complaint about type-1 and type-2 errors in statistics, but slightly different in that it's not about names for two things that don't help you know which names which, but rather about two names that one is supposed to keep straight even though they both name the same thing.
In lambda-calculi, and other rewriting systems with which I am less familiar, one defines a reduction relation on terms that is supposed to capture the idea of a single step of computation or simplification, like replacing "2+3" with "5". (These are expressions of arithmetic, not lambda-calculus, but never mind. I'll use arithmetic expressions again below.) Reduction relations are almost never reflexive (that would be zero steps of computation), transitive (more than one step) or symmetric (counting a backward step as a forward step), but it does make sense to look at the notion of "equivalence" that comes from thinking of things as equivalent if one can be reduced to the other. The equivalence relation induced by reduction, called conversion or convertibility, is the reflexive, symmetric, transitive closure of reduction -- which is to say that two terms are convertible if one can be transformed into the other by a sequence of zero or more steps each of which is a reduction either forwards or backwards. So, if "2+3" reduces to "5" and "9-4" also reduces to "5", the expressions "2+3" and "9-4" are convertible and we can think of them as having the same meaning.
In general, if A reduces in zero or more steps to B, and C also reduces in zero or more steps to B, then we can say that B is a "common reduct" of A and C. Clearly, any two terms with a common reduct are by definition convertible. The question is, do any two convertible terms have a common reduct?
[Why is this question important? Among other reasons, because if so, and you have two terms that you can show do not have a common reduct, you will know they are not convertible. Otherwise, it would be hard to be sure.]
In the lambda-calculus, the answer is yes. This fact was proven by Church and Rosser in 1936 and is called the Church-Rosser Theorem. For rewrite systems other than the untyped lambda-calculus, the answer obviously depends on what the reduction relation actually is. A reduction relation for which any two convertible terms have a common reduct can be said to have the Church-Rosser property.
OK. It turns out that the key to proving the Church-Rosser property, at least for the lambda calculus, is to prove the following: If there is more than one way to reduce a term A, say to B1 or to B2, in zero or more steps, then there exists some term C such that both B1 and B2 can be reduced in zero or more steps to C. More generally, we can say: any two terms with a common "source" also have a common reduct. So if two different people are trying to reduce A and their paths ever diverge, taking one to B1 and the other to B2, then it doesn't really matter because they will eventually "flow back together" at C. This property is called confluence.
So here's where I have a problem. It turns out that the property I refer to as CR above (convertible terms have a common reduct) and the property I just called confluence (terms with a common source have a common reduct) are equivalent. (The CR->confluence direction is obvious, as any terms with a common source are convertible; the proof of other direction left as an exercise. Hint: induction on the number of steps in the conversion.) Because they're equivalent, it's always hard to know whether I have the names the right way around. I was pretty sure this is the way I learned them in grad school, and it's consistent with MathWorld's definitions of confluence and Church-Rosser, but Wikipedia has it differently, as does at least one legitimate book I looked in while writing this.
What's my point? The point is that I resent having had to devote precious brain cells to remembering which is which of two different ways to say the same goddamn thing. It seems like a pretty small thing and not worth bothering to resent, but there it is.
Thursday, November 29, 2007
Wednesday, November 28, 2007
Arbitrary Names
Language Log is a treasure trove. Every time I dive into its archives I find something old, but new to me, that is interesting.
In 2004, Geoffrey Pullum discussed his refusal to learn which business model for massage is called incall and which is called outcall, on the grounds that the names are utterly unhelpful and "if I can't see how it follows by some sort of linguistic principles, I will just forget it again." Later that same day, Christopher Potts pointed out that similar problems exist with ordering food "in" or "out", pushing an appointment "up" or "back", and (my favorite) identifying the root of a tree structure as maximal or minimal in the dominance relation. (Potts also says that "linguists draw their trees upside down, with the root at the top of the page" which of course is right-side up to computer scientists like me, as long as we're talking about trees as an abstract graph structure rather than about trees, the plants.)
I love reading this kind of LL post, because some of these are the kind of things about language, especially technical language, that drive me crazy.
Example: Statistics textbooks classify the ways a statistical test can go wrong as "type 1 errors" and "type 2 errors". (Or maybe they use Roman numerals. The point, namely that these names are stupid, is the same.) I have an old book (actually, a new copy of a Dover edition of an old text) that calls them "errors of the first kind" and "errors of the second kind". Now, one of these kinds of errors is when your test tells you two things are different when they're really the same, and the other is when the test tells you they are the same when they're really different. Like Pullum, I absolutely refuse to even try to remember which is which. And also like Pullum, I anticipate that many people reading this statement would respond to it by trying to tell me anyway: the fact that I don't know is not the point; the point is that the meanings of these technical terms are arbitrary, reflecting nothing about the events they describe but depending instead on what order some founding father of statistics happened to think of them in.
So what do I suggest? Well, in many contexts, like testing people for diseases or testing drugs for treatment effects or identifying spam or whatever, the terms "false positive" and "false negative" are transparent and work perfectly well. In other cases, where the designation of outcomes as "positive" and "negative" is not obvious, the statistics literature provides the terms "rejection error" and "acceptance error", referring to rejection or acceptance of the null hypothesis; which hypothesis is null is an unambiguous technical fact about the statistical method being used.
Interestingly, there are tons of these arbitrary namings in mathematics, and I don't object to all of them. I don't really care, for example, about the fact that one kind of function is called a homomorphism and another very different kind of function is called a homeomorphism, even though (as far as I can tell) there's no way to look at those words and determine from their structures which means what. But in this case, and many others, there's a good reason not to mind: a homomorphism is a function you study in algebra, and a homeomorphism is one you study in topology. So while if you're reading this paragraph as a nonmathematician and seeing these terms for the first time I could forgive you for being confused, the average mathematician probably learned the definitions of those two words in separate classes, probably separate semesters of undergraduate math. They're probably conceptually separate enough that no one who cares about either thing can possibly be confused.
Similarly, before I studied Euclidean geometry in ninth grade, I could never remember which kind of pair of angles was called complementary and which was called supplementary. (To be truthful, it's now been long enough that I will have to go look them up before I can finish this paragraph.) (Okay, looked it up. And guess what? I had it right.) There's an episode of the Cosby Show where Cockroach, complaining to Dr. Huxtable about having to study for a math test, says "I couldn't care less about complementary and supplementary angles." If he meant he didn't want to learn which word meant which thing, and Mrs. Westlake had organized her syllabus such that the two definitions were on the same pop quiz, then I can't say I blame him. But when I took geometry, the notion of a straight angle was introduced a whole week or two before that of a right angle. I'm not sure why that was, but it had the pleasant effect of letting us talk about supplementary angles for quite a while before we had to know about complementary angles. By the time we had to learn the second word, we were comfortable enough with the first word that they didn't interfere. (At least not for me. My classmates might not have agreed.) The difference between the classroom experience and the, well, call it the "dictionary experience" was impressive to me even then.
And don't get me started on confluence and the Church-Rosser property. Because I've spent so much time on these two examples that I'll have to save that one for later.
In 2004, Geoffrey Pullum discussed his refusal to learn which business model for massage is called incall and which is called outcall, on the grounds that the names are utterly unhelpful and "if I can't see how it follows by some sort of linguistic principles, I will just forget it again." Later that same day, Christopher Potts pointed out that similar problems exist with ordering food "in" or "out", pushing an appointment "up" or "back", and (my favorite) identifying the root of a tree structure as maximal or minimal in the dominance relation. (Potts also says that "linguists draw their trees upside down, with the root at the top of the page" which of course is right-side up to computer scientists like me, as long as we're talking about trees as an abstract graph structure rather than about trees, the plants.)
I love reading this kind of LL post, because some of these are the kind of things about language, especially technical language, that drive me crazy.
Example: Statistics textbooks classify the ways a statistical test can go wrong as "type 1 errors" and "type 2 errors". (Or maybe they use Roman numerals. The point, namely that these names are stupid, is the same.) I have an old book (actually, a new copy of a Dover edition of an old text) that calls them "errors of the first kind" and "errors of the second kind". Now, one of these kinds of errors is when your test tells you two things are different when they're really the same, and the other is when the test tells you they are the same when they're really different. Like Pullum, I absolutely refuse to even try to remember which is which. And also like Pullum, I anticipate that many people reading this statement would respond to it by trying to tell me anyway: the fact that I don't know is not the point; the point is that the meanings of these technical terms are arbitrary, reflecting nothing about the events they describe but depending instead on what order some founding father of statistics happened to think of them in.
So what do I suggest? Well, in many contexts, like testing people for diseases or testing drugs for treatment effects or identifying spam or whatever, the terms "false positive" and "false negative" are transparent and work perfectly well. In other cases, where the designation of outcomes as "positive" and "negative" is not obvious, the statistics literature provides the terms "rejection error" and "acceptance error", referring to rejection or acceptance of the null hypothesis; which hypothesis is null is an unambiguous technical fact about the statistical method being used.
Interestingly, there are tons of these arbitrary namings in mathematics, and I don't object to all of them. I don't really care, for example, about the fact that one kind of function is called a homomorphism and another very different kind of function is called a homeomorphism, even though (as far as I can tell) there's no way to look at those words and determine from their structures which means what. But in this case, and many others, there's a good reason not to mind: a homomorphism is a function you study in algebra, and a homeomorphism is one you study in topology. So while if you're reading this paragraph as a nonmathematician and seeing these terms for the first time I could forgive you for being confused, the average mathematician probably learned the definitions of those two words in separate classes, probably separate semesters of undergraduate math. They're probably conceptually separate enough that no one who cares about either thing can possibly be confused.
Similarly, before I studied Euclidean geometry in ninth grade, I could never remember which kind of pair of angles was called complementary and which was called supplementary. (To be truthful, it's now been long enough that I will have to go look them up before I can finish this paragraph.) (Okay, looked it up. And guess what? I had it right.) There's an episode of the Cosby Show where Cockroach, complaining to Dr. Huxtable about having to study for a math test, says "I couldn't care less about complementary and supplementary angles." If he meant he didn't want to learn which word meant which thing, and Mrs. Westlake had organized her syllabus such that the two definitions were on the same pop quiz, then I can't say I blame him. But when I took geometry, the notion of a straight angle was introduced a whole week or two before that of a right angle. I'm not sure why that was, but it had the pleasant effect of letting us talk about supplementary angles for quite a while before we had to know about complementary angles. By the time we had to learn the second word, we were comfortable enough with the first word that they didn't interfere. (At least not for me. My classmates might not have agreed.) The difference between the classroom experience and the, well, call it the "dictionary experience" was impressive to me even then.
And don't get me started on confluence and the Church-Rosser property. Because I've spent so much time on these two examples that I'll have to save that one for later.
Monday, November 26, 2007
Paul Davies: Taking Science on Faith
Op-ed in the New York Times.
A very nice essay on the importance of faith to science. I have had many of the thoughts expressed here myself, but this is a much more eloquent presentation than I could have created. Read it.
Over the years I have often asked my physicist colleagues why the laws of physics are what they are. The answers vary from “that’s not a scientific question” to “nobody knows.” The favorite reply is, “There is no reason they are what they are — they just are.” The idea that the laws exist reasonlessly is deeply anti-rational. After all, the very essence of a scientific explanation of some phenomenon is that the world is ordered logically and that there are reasons things are as they are. If one traces these reasons all the way down to the bedrock of reality — the laws of physics — only to find that reason then deserts us, it makes a mockery of science.
A very nice essay on the importance of faith to science. I have had many of the thoughts expressed here myself, but this is a much more eloquent presentation than I could have created. Read it.
The what percent?
From the Straight Dope Classic that ran today:
The square root of one percent? Is that ten percent, as in 0.10*0.10=0.01? Or, just as implausibly, does it mean (size of population affected) = 100 * (number of meditators)^2?
According to David Orme-Johnson, a researcher at Maharishi International University, "Thirty-one sociological studies conducted throughout the world document that the quality of life in society significantly improves when as little as the square root of one percent of a population practices TM-Sidhi Yogic Flying together in one place."
The square root of one percent? Is that ten percent, as in 0.10*0.10=0.01? Or, just as implausibly, does it mean (size of population affected) = 100 * (number of meditators)^2?
Wednesday, November 21, 2007
Impunity
Hey, I learned something today!
From Al Jazeera English (emphasis added):
This is the first time I can remember seeing the word impunity not preceded by with. It looked so strange that I thought it might be a typo for immunity, like the kind prosecutors sometimes give to witnesses who would otherwise be subject to prosecution themselves. Most of the time, when I hear or read that someone acts "with impunity", I take it to refer to the attitude of the person acting, the confidence that their crimes will go unpunished. This isn't something it makes sense to "offer" someone, even unintentionally and even only "in effect" -- you can offer someone the opportunity to act with impunity, but you can't offer the impunity itself.
But never mind all that, because I looked it up, and sure enough, impunity means precisely "exemption or freedom from punishment, harm, or loss". So not only does it refer to the fact of non-punishment rather than just to the expectation of non-punishment, but it can refer to "exemption" rather than mere "freedom" from punishment. So when a prosecutor grants a witness immunity, I suppose she is also granting him impunity. Then again, the dictionary's usage example was "laws were flouted with impunity", which lets me go on believing it's weird to use impunity without with.
In any case, it may be that Al Jazeera's command of the English language is better than mine.
I suppose I have to compare and contrast Al Jazeera's (English-language) coverage of this story with the U.S. media's. The second sentence of the Al Jazeera story is:
The headline on CNN.com (as of now) is "Clinton: Saudi rape verdict 'an outrage'", and the article says in part:
That's not so different, but I have to admit that I read the CNN piece first and sort of missed the fact that the Bush administration has not condemned something so obviously condemnable. The Al Jazeera version puts it much more bluntly. I guess Democrats, particularly those running for President, criticize the Bush administration so often that I no longer assume it means they've actually done something wrong.
From Al Jazeera English (emphasis added):
Farida Deif, researcher in the women's rights division of Human Rights Watch, said: "A courageous young woman faces lashing and prison for speaking out about her efforts to find justice.
"This verdict not only sends victims of sexual violence the message that they should not press charges, but in effect offers protection and impunity to the perpetrators."
This is the first time I can remember seeing the word impunity not preceded by with. It looked so strange that I thought it might be a typo for immunity, like the kind prosecutors sometimes give to witnesses who would otherwise be subject to prosecution themselves. Most of the time, when I hear or read that someone acts "with impunity", I take it to refer to the attitude of the person acting, the confidence that their crimes will go unpunished. This isn't something it makes sense to "offer" someone, even unintentionally and even only "in effect" -- you can offer someone the opportunity to act with impunity, but you can't offer the impunity itself.
But never mind all that, because I looked it up, and sure enough, impunity means precisely "exemption or freedom from punishment, harm, or loss". So not only does it refer to the fact of non-punishment rather than just to the expectation of non-punishment, but it can refer to "exemption" rather than mere "freedom" from punishment. So when a prosecutor grants a witness immunity, I suppose she is also granting him impunity. Then again, the dictionary's usage example was "laws were flouted with impunity", which lets me go on believing it's weird to use impunity without with.
In any case, it may be that Al Jazeera's command of the English language is better than mine.
I suppose I have to compare and contrast Al Jazeera's (English-language) coverage of this story with the U.S. media's. The second sentence of the Al Jazeera story is:
But the decision to give a woman who was gang raped a six months jail term and 200 lashes received only mild criticism from the US on Monday.
The headline on CNN.com (as of now) is "Clinton: Saudi rape verdict 'an outrage'", and the article says in part:
Labeling it "an outrage", Sen. Clinton urged the U.S. government to protest the decision.
"The Bush administration has refused to condemn the sentence and said it will not protest an internal Saudi decision," the Democratic presidential frontrunner said in a statement.
That's not so different, but I have to admit that I read the CNN piece first and sort of missed the fact that the Bush administration has not condemned something so obviously condemnable. The Al Jazeera version puts it much more bluntly. I guess Democrats, particularly those running for President, criticize the Bush administration so often that I no longer assume it means they've actually done something wrong.
Tuesday, November 13, 2007
Abbas And Peres Call For Peace
Al Jazeera English quotes Israeli President Shimon Peres, referring to an upcoming Israeli-Palestinian peace conference to be hosted by the U.S.:
Is that setting the bar low enough? At least Peres seems to think the meeting will involve some kind of progress -- later in the article, he is contradicted by "one Israeli official" who is quoted as saying:
Sigh.
Clearly I've been reading too much Language Log, because here's what I notice. When I saw the word "stage" following the word "performance", I initially assigned it the wrong meaning. The fact that "Annapolis" refers primarily to a place (kind of like "all the world"), rather than an event, is also a factor. (Obviously I'm not claiming it's not legit to use a place name to refer to an event that occurred or is scheduled to occur there. Witness "Pearl Harbor", "Kitty Hawk", or "Abu Ghraib".) Believing I am too smart to be tripped up by nothing, I submit that this is a clumsy translation. (Though I don't know what language the original statement was made in -- for all I know it was English!) And has Israel explained many times that the Annapolis meeting is not a conference, or claimed many times that it is one? I don't remember the name of the semantic phenomenon that causes me to favor the former interpretation, but it's the thing where saying someone "explained that X" (as opposed to "said that X" or "asserted that X") entails agreeing that X is true (though I suppose not as strongly as "proved that X"). The official clearly believes that the truth is "It's not a conference," so that's what Israel must have explained. Thus I am led to a picture of the Israeli government attempting many times to reassure its own citizens that their leaders are not getting ready to give anything away. Is that just me?
I found this after being persuaded to try reading some Al Jazeera news coverage.
"Annapolis will not just be a performance, it is a stage on an agreed path that could lead to a peace agreement in the right direction."
Is that setting the bar low enough? At least Peres seems to think the meeting will involve some kind of progress -- later in the article, he is contradicted by "one Israeli official" who is quoted as saying:
"It's not a conference, as Israel has explained many times, but a meeting where representatives will read declarations without entering into negotiations."
Sigh.
Clearly I've been reading too much Language Log, because here's what I notice. When I saw the word "stage" following the word "performance", I initially assigned it the wrong meaning. The fact that "Annapolis" refers primarily to a place (kind of like "all the world"), rather than an event, is also a factor. (Obviously I'm not claiming it's not legit to use a place name to refer to an event that occurred or is scheduled to occur there. Witness "Pearl Harbor", "Kitty Hawk", or "Abu Ghraib".) Believing I am too smart to be tripped up by nothing, I submit that this is a clumsy translation. (Though I don't know what language the original statement was made in -- for all I know it was English!) And has Israel explained many times that the Annapolis meeting is not a conference, or claimed many times that it is one? I don't remember the name of the semantic phenomenon that causes me to favor the former interpretation, but it's the thing where saying someone "explained that X" (as opposed to "said that X" or "asserted that X") entails agreeing that X is true (though I suppose not as strongly as "proved that X"). The official clearly believes that the truth is "It's not a conference," so that's what Israel must have explained. Thus I am led to a picture of the Israeli government attempting many times to reassure its own citizens that their leaders are not getting ready to give anything away. Is that just me?
I found this after being persuaded to try reading some Al Jazeera news coverage.
Subscribe to:
Posts (Atom)