Rubrication

I was perusing Wikipedia today at lunch since I left the book, “An Taistealaí”, which I’m currently reading, at home. I recently finished my first Irish book “Bagairt Ón Spás”. The latter is *much* easier reading than the former, since it was written for the instruction of teens between the ages of 12 and 15.

In any case I was roaming around the sections on syntax and morphology and I stumbled onto an article concerning Ubykh. This extremely strange Northerwestern Caucasian language is sometimes classified as polysynthetic due to the capacity of verbs to incorporate large parts of the sentence. The following sentence is, to me, quite facinating:

“aχʲazbatʂʾaʁawdətʷaajlafaqʾajtʾmadaχ!”

which translates to:

“If only you had not been able to make him take it all out from under me again for them!”

If you can’t read that because of the strange characters that you need to have present in your font, or because you don’t understand how to read IPA then don’t worry too much. You probably couldn’t pronounce it even if you could read it, since Ubykh has one of the largest consonant sets outside of South Africa. In order to compensate however it has an almost ridiculous paucity of vowels, totaling to only two.

I first learned about the Ubykh language while reading a facinating book Nart Sagas from the Caucasus. This book has one of the most incredible collections of folk tales that I have ever read. At the same time strange and familiar, the Narts hold many values that are incredibly modern and egalitarian (for instance the recognition of the sexual rights of women), whilst at the same time holding traditions that are incredibly alien (the ability to avoid blood feud by suckling at the nipple of your adversaries wife). I HIGHLY recommend this book. Really, these stories should be up there with the greek myths and the story of Cúchulainn.

Unfortunately as I was reading, I also learned of something else about the Ubykh language. “The Ubykh language died out on October 7, 1992, when its last fluent speaker (Tevfik Esenç) died in his sleep.” (wikipedia)

A tragedy to be sure. I remember the excitement I felt in reading the Nart Sagas and in the possiblity of reading the sagas in their native language, and I even contemplated the possibity of going to Caucasia and speaking with the Ubykh people in their native tongue. Alas, there are none to speak to.

For those of you who missed out on it, Richard Waghorne wrote an extremely amusing post on the Irish language. Apparently a few people were incensed. I myself thought it was quite funny and I sent it to my wife straight away. She, not being as familiar with Waghorne’s antics, was quite convinced that it was a parody.

I didn’t have time to prepare a response due to other constraints. Soon after the post appeared I found a post which covered nearly every argument that occured to me to put forward over at Talideon.com. Even the post title which had arisen in my mind was stolen by some clever soul working at Údarás na Gaeltachta before I could use it.

I’m quite convinced that Ireland is in the midst of a cultural revolution. The economy is booming in Ireland and the McCulture that can be offered by the global entertainment industry and the appeal of excessive drinking can only hold the attention spans of an affluent population for a limited time. The popularity of the Gaelscoileanna are growing rapidly and visits to Irish classes in the Gaeltacht are booming. TG4 offers reasonable entertainment value which is at least as good as most of the programming on the english language stations. And now, we find that even youtube.com has modern Irish music in its repertoire.

As evidenced by the juggernaught that is the Welsh language, or the meteoric rise of Finnish, It doesn’t take long for people to take back their native tongue. All it takes is the will to see it used.

I look forward to the day when dinosaurs like Richard Waghorne will have to make a choice of whether to move into the modern era or hide under the swiftly fading shadow of Englands hegemony.

I got my citizenship notice today!!! I’m an Irish citizen! Now I can vote! And I’m an EU citizen! It came two months earlier than I thought it would. Hooray!

Rather than writing the canonical blog post about how I haven’t written in a long time, I’ll start with the metacanonical blog post about how I’m not going to write about how I haven’t written in a long time.

As some of you may know, I’ve been studying Irish lately. I’m a bit obsessive about it. I really really enjoy it. In any case it has gotten me thinking a lot about how to perform automatic translation by machine.

I have very little faith in the utility of formal grammars for the purpose of computer linguistic analysis both because these have been shown to be extremely poor performers in past practice and the fact that I don’t really believe in semantics in the first place.

One common problem in translation by machine is the notorious “round trip problem”. Anyone who has played with babble-fish has seen the humourous consequences of translating an idiomatic phrase from one language into a target language and then translating it back.

I have some ideas about how to solve the “round trip problem” in translation by machine. The idea is basically this. You take two parallel corpuses (corpi? I don’t know Latin and I always choose the wrong plural, so I’ll just go with the English plural). You “pin” these corpuses at places that are “full stops”. A full stop is a boundary over which the analysis is allowed to ignore correlations. This can improve the computational efficiency of the technique. I haven’t tried it yet, but I believe that paragraph boundaries may be reasonable. The analysis consists of looking at the probability of occurance of words in the target text given words in the source text. If we pin at sentence boundaries the following parallel corpus:

I am hungry
Tá ocras orm

I am thirsty
Tá tart orm

We will find that “hungry” is correlated to “ocras” and “thirsty” is correlated to “tart”. “I am” will be correlated to “Tá… …orm”. It will also very importantly be correlated to both “tart” and “ocras”. The importance of this can be seen from some further sentences in our parallel corpus

I am tired
Tá mé tuirseach

I am contented
Tá mé sásta

It is only in context that we can determine the appropriate use of the prepositional pronoun “orm”. No amount of grammatical analysis will denote the appropriateness of a particular construction when moving from a source language to a destination language. The fact that “the hunger is upon you” is correct is only evident from the use of the language.

In any case I’ve been playing with different probabilistic models to achieve the correlations between words, and to make sure that the positioning is both important and not over-determined in the model. This is especially important for noun phrases and other syntactic units that should be treated as atomic by the structural analysis.

I’d love to hear if you have any thoughts….

I was thinking about cut elimination on my way back from work today due in large part to a post on the cut rule made by sigfpe on A Neighborhood of Infinity.

It occured to me that the fact that cut-free proofs can be so tremendously much larger than the cut-full ones and that directly constructing cut-full proofs is so difficult is a bit strange. It seems somehow unfair.

As I was thinking about this I realised that one could find cut-free proofs automatically and then reduce them with reverse cut-elimination to produce extremely cutfull proofs. These proofs should be very economical computationally. If one keeps the terms that correspond with the proofs along side, one should be able to obtain a source to source translation that might have performance benefits.

Another totally far-out idea came to me as well. Mathematicians often use lemmas repeatedly. Perhaps the process of finding cuts is generally useful. Specifically, if a lemma is useful in simplifying one proof, maybe it is more likely to be useful in simplifying other proofs. There should be statistical measures over random syntactically valid sentences that one could come up with to see if such lemmas exist.

The ideas of traditional corporatism and communism are diminisioning in importance. This results from a fundemental change in the economics of modern post industrial society.

The means of production was assumed, in communist theory, to be the instrument that the proletariate needed in order to avoid having their labor exploited by the owners of those means. Factories, farms and industrial occupations continue to exist in the west. The cost of these plants and farms is also much higher than it has every been in the past. Yet they employ fewer people and represent a shrinking segment of the economy.

The financial institution of the corporation was designed as a means of raising money in order pay for the means of production which include capital expenditures and the cost of wages. This leads to a political theory concerned with producing environments that are suitable for corporations to exist and proliferate.

Two questions need to be asked. Firstly, is this aforementioned phenomenon a real change in the economic structure or have the jobs simply been shifted elsewhere leading to the illusion of a post industrial economy in the first world. Secondly, if it is in fact a real change, what implications does it have towards political theory.

I don’t know enough about the first question to say for sure (if you could send me data/papers, that would be nice!). It seems to me that the factories in these outsourced-to countries that produce our phones, fabric and computers as well as an array of other goods must, on the whole, be fairly sophisticated. They tend to produce high quality goods with respect to the goods that were produced in former times (just decades ago). I suspect that in fact the number of laborers that they use is also much lower than it would have been in times past. For these reasons I think it is likely that the post industrial economy is not just a vestige of leveraging cheap labor in foreign economies but an actual global phenomenon which will have increasing importance as countries such as china, india and mexico fully industrialise and subsequently post-industrialise.

If in fact this is true what implications does it have to the idiologies of corporatism and communism?

Let us take for example the occupation of software engineer. In reality the only infrastructure that is needed to produce and disseminate products generated by a software engineer can be bought with a months wages. The costs of the means of production are now dominated by the cost of food and shelter.

Why then are software engineers overwelmingly employeed by corporations? The interests that are served by entering into contract for a corporation reduce to:

a) insurance against non-payment (wages)
b) social lubrication

The main reasons are social and technological. The institutions that would lubricate the formation of by-need organisations of programmers to take advantage of niches or requirements in the area of software design, do not yet exist. The old political doctrines of communism and corporatism are increasingly irrelevant to the software engineer as the software engineer (in the overwelming number of cases) already owns the capital means of production, yet the apparatus to despense with these institutions, while technically feasible, still requires mind share.

As you might know, I like logics. Notice that logic is in the plural. This might seem a bit strange to you. It certainly seems a bit strange to me. How can it be that there is more than one?

There are quite a number of logics at this point. We pretty much started out with Aristotelian logic, ie. the logic of syllogism which you were probably forced to study in school. Aristotelian logic was formalised and generalised during the early part of last century and this formalism has come to be called Classical Logic or often just CL.

This formalisation caused some to view with suspicion the outcome of various formal arguments. It gave rise to a more conservative ‘constructive’ logic which we will call Intuisionistic (or IL) whose informal interpretation is known as the Brouwer-Heyting-Kalmagorov interpretation or BHK.

Basically in Classical logic you can make proofs about things for which you can not provide examples. This also happens however in Intuisionistic logic for arguments that use the ∀ quantifier. It doesn’t seem so onerous in those cases however as you can see by playing with it a bit.

We can even make things more restrictive and get Minimal Logic (or ML). Minimal logic rejects the provability of arbitrary things from Falsum. The rule is often called ‘ex falso sequitur quodlibet,’ or ‘ex falso.’

Since then there has been a real explosion of the types of logic. There are Substructural Logics, Quantum Logic (QL), Linear Logic (LL, a pretty big fish than can even swallow CL) and a host of others.

From this the question naturally arises in my mind. Which is the right logic? As someone who writes programming languages I have a natural sympathy for IL as it leads naturally to a term calculus meaning that terms can be given back to the user that exemplify proofs. It is a natural logic to look at for the purposes of a database query language. There are however problems with it in regards to this. It is not “resource sensitive”. Things change in data stores and none of the above mentioned logics provide the appropriate tools to deal with this. Linear Logic comes closest but fails to deal with sharing or ordering. Many new resource logics have been invented to deal with this but I have yet to come across something that looks to me like a suitable answer (which doesn’t mean it isn’t already out there!).

In science the problem may be even worse. People use some form of quasi-classical reasoning to make arguments. It seems that this might not even be the appropriate tool to use when reasoning about Quantum Mechanics. Quantum Logic has been proposed as the appropriate way to deal with Quantum quandries in some (fairly fringe) circles. So far Quantum Logic looks to me to be too anemic. Something closer to a theory that has a curry howard isomorphism with quantum computation would be more satisfying.

So what is it that makes a good logic? My personal feeling is this. A logic is a constraint framework from whence you can show various programs that are the “proofs” of the constraint apparatus are acceptable. An appropriate constraint framework is one in which constraints that apply to your system can be expressed simply with minimal work. I believe that the Classical Logic for Propositions arose as a sort of logic of the natural sciences because it was in fact a type of physics. It is a calculus in which we can present common sense notions of real things in a simple way. When we extended the apparatus to classical logic we may have gotten something that strays so far from common sense it is no longer useful (this of course is debatable, and I’m not sure how much I believe it).

Now that we have a quantum world with physics that does not function in ways that our common sense would dictate, it seems perfectly reasonable to reject the notion of classical logic in this regime. In favor of what? I think the jury is still out on this one.

As for as how to quantify what a good logic is, I’ll make a couple of guesses. You want to be able to express constraint systems that apply to your realm with parsimony. You want to be able to verify and extract programs from proofs. If those two conditions are met more often for one logic than another for a particular problem, then I would deem it superior.

Of course this doesn’t even go into notions of logic in ethics…

Thanks to my brother I got a really cool book on proof theory called “Basic Proof Theory”. It has a bunch of nice features including a from the ground up presentation of proof theory that should be relatively accesible to anyone with a background in mathematics. It demonstrates some of the connections provided by the Curry-Howard correspondance (which is my favourite part of the book) . It also describe Second order logic, which is great because I’ve had very little formal exposure to this. Second order logic is really beautiful since you can define all the connectives in terms of ∀, ∀² and →. If you pun ∀ and ∀² you have a really compact notation.

The book also forced me to learn some things I hadn’t wrapped my head around. One of those was Gentzen style sequent calculus. This really turns out to be pretty easy when you have a good book describing it. I’ve even wrote a little sequent solver (in lisp) since I found the proofs so much fun. The first order intuisionistic sequent solver is really not terribly difficult to write. Basically I treat the proofs as goal directed starting with a sequent of the form:

⇒ F

And try to arive at leaves of the tree that all have the form:

A ⇒ A

I have already proven that ‘F ⇒ F’ for compound formulas F from ‘A ⇒ A’ so I didn’t figure it was neccessary to make the solver do it. The solver currently only works with propositional formula (it solves a type theory where types are not parameteric.) but I’m interested in limited extensions though I haven’t thought much about that. I imagine I quickly get something undecidable if I’m not careful.

Anyhow working with the sequent calculus got me thinking about → In the book they present the rule for R→ as such

This is a bit weird since there is nothing that goes the other direction. ie. for non of: Minimal, Intuisionistic or Classical logic do you find a rule in which you introduce a connective in the left from formulas in the right. I started looking around for something that does this and I ran into Basic Logic. I haven’t read the paper yet so I can’t really comment on it. I’ll let you know after I’m done with it.

Ok, so last time we left off with a very informal discussion about Venn diagrams and how they relate to Boolean Logic.

First let us do a little set theory and then we’ll start drawing connections with the previous post to make it a bit more rigorous. We will stick with completely finite sets, so keep that in mind.

A set is basically a collection of distinguishable objects. Sets have no notion of the number of times an object is in them. They simply contain an object or they do not. A set (if it is finite) can be writen in terms of its elements, for instance: S = {a,b,c} is the set S with elements a,b and c.

A map can be thought of as arrows that leave from one set (the domain) and arive at another (the codomain).

We will also introduce a special set 2^S which is an exponential or a “homset” called hom(S,2). S will be jus t a collection of elements as above, and 2 will be a collection of the elements {0,1}. We can think of a homset as a collection of all maps from the elements of S into the elements of 2. In this particular case the map has some special properties because of 2. A map will either map an element to 0 or it maps it to 1. This means that we can fully describe a map from S to 2 by simply naming either the set that goes to 1 or the set that goes to 0. See the illustration below.

Since S is finite 2^S will also be finite. In fact if we use the naming trick above, where we associate the set of elements that goes to 1 with the map, the set of all maps can then be described as the set of all subsets of S. Try it out on paper with S={a,b,c}, 2^S = {{},{a},{b},{c},{a,b},{b,c},{b,a},{a,b,c}}.

Ok, so there are a couple of operations on sets that we will be interested in. One is ∩ which is pronounced “intersection” and ∪ which is pronounced “union”. The intersection of two sets is simply all elements that occur in both sets. So if we let A={a,b,c,d} and B={c,d,e,f} then A∩B={c,d}. The union of two sets is just every element that is in both of the sets. so A∪B={a,b,c,d,e,f}.

Ok now as it turns out we want to talk about another structure called a topology. A topology is a set, in our case S together with a set of subsets of S. We will write it as the tuple <S ,T>.

Now let us go back to Boolean Algebras momentarily. We had a Boolean Algebra B being a tuple <B ,∧,∨,0,1>. Now let us identify B with 2^S, ∧ with ∩ and ∨ with ∪. By doing this we have recovered a Boolean algebra simply by looking at the topology of all S together with all its subsets and the intersection and union operations!

Ok, that is great, but it doesn’t stop there. Topologies are not restricted to <s ,2^S> We can look at other subsets of S. And then it might be interesting to ask whether we will get something like a Boolean algebra. It turns out of course that you don’t get Boolean algebras with just any set of subsets, but you do get some kind of algebra. The thing that you always get is called a lattice.

As it turns out Quantum Mechanics also forms a kind of logic if we start with Hilbert space and use the idea of associating the spaces with a logic. Its more than just the union and intersection of sets however, we also need the concept of an algebraic closure operator (an operator having as properties X ⊂ C(X), C(C(X)) = C(X), and X ⊂ Y → C(X) ⊂ C(Y) ) since the join of hilbert spaces is a superset of the union. This is actually the source of “entanglement” in quantum mechanics which leads to so much confusion. The algebraic closure in the case of Hilbert spaces is the space spanned by the basis vectors of both sets. From this we can then look at the lattice structure and come to find that it isn’t much like a Boolean Algebra at all, but is something called an “Orthomodular Lattice” a bounded lattice that is also an ortho lattice (has a complementation operation) and satisfies the modularity condition. We can write the algebra as the tuple <S,∧,∨,’,0,1 >

The modularity condition is very interesting but visually producing spaces that exhibit it is a bit tricky. I’ll try to draw some nice pictures of spaces that display this behavior in an intuitive way in part IV.

P.S. I lied about getting to Heyting algebras didn’t I!

Ok, I’ll say something about it. When we talk about our typical notions of spaces as we learned them in high school we run into some differences with the boolean algebraic description. The topology that we provided for our boolean space 2^S has an unusual property. If we look at the dual of 2^S in the sense that we exchange 0 for 1 in our naming of sets for hom(S,2) nothing changes. If we have a complement operation in our topology, that is an operator ¬ such that ¬A = S⁄A where ⁄ produces a set with every element of S that is not also in A. The set of all complements of sets in 2^S is 2^S. We say in topology that the tuple <S ,T> is the tuple of a set S, and its open sets T. The complement of the open sets are the closed sets. In 2^S every thing is both closed and open! In fact the silly mathematicians even say that they are “clopen”.

When we took algebra we learned that [0,1] is not the same as (0,1). That is the set that includes its boundary is not the same as the one that does not. This leads us to a different topology in which we have a clear distinction between open and closed sets. In the standard description of space in high school Algebra (that is, the topology induced by the euclidean distance measure) there are only two sets that have the property of being clopen (can you guess what they are?).

So in a Heyting algebra we don’t even bother with the notion of complementation since it leads to complications. Instead we introduce a symbol → into our algebra. We then have the algebra <S,∧,∨,→>. The symbol → is pronounced “implies”.

I promise to tell you more later

I have to say that this is the fault of everyone involved in allowing electronic voting systems that have no visible paper trail and are counted by private corporations with no provisions made for recount. Some of the most important security specialists including Bruce Schneier have vocally lobbied against such systems.

The existance of such systems and their wide spread deployment in the US is frightening. It serves no benefit to anyone save those who hope to use them to steal elections. Hopefully in the attempt to export democracy to the rest of the world the US leaves this kind at home.

GAO Report