For whatever reason, I remember quite clearly the first time I was introduced to the wonder of paradoxes. Curiously, it was during an English class in my first year of secondary school, and the rather eccentric teacher had a particular tendency to ramble on about any interesting topic (usually well outside of the syllabus). A criticism this is not, as it was many years before the seriousness of GCSEs and A-levels. I think that in looking back I took great enjoyment out of those classes, even if I did not so much realise it then. (And it wasn’t just for the fact that we didn’t spend countless hours analysing poetry or Shakespeare.) Moreover, it is plain now that he was, through a variety of ways, trying to open our young and malleable minds so that they might perhaps (idealistically) become sharp and inquisitive, and remain so through the future years of drudgery.

Before I continue too far on such a tangent myself, let me present the focus of this post, that is one of the paradoxes with which I became acquainted during one of those many unusual English classes. I have forgetten the precise details, but the following I think is a half-way accurate rendition of what was then told (though the many embellishments may differ to those of my former teacher). As you may guess from the title, I term this little problem the “Traveller’s Paradox”, though I don’t think it has any conventional name, and has undoubtedly been repeated in many varying forms.

Warning to unsuspecting readers: the following situation is presented in the fairy-tale style. I was told it this way, so that’s how it’s going to get repeated – can’t please everyone!

A wearied prince has travelled many leagues on his quest to reach the all but forgotten castle that is the target of his quest; the location of the the legendary gem that is the final chance to save his kingdom from ruin. The pale sun is gradually vanishing behind the horizon as the young man approaches a great fork in the road ahead, far beyond which he can glimpse the tall spires of the castle that is his destination. Having sought his goal by his wits and instincts alone thus far, he is now unsure of which path to take from this point. Alas, time permits him to delay no longer if he is to succeed in his quest, and he must make the choice of road before darkness falls.

Approaching the split in the wide path, he scarcely notices two giants standing motionlessly at the side of the path. In this moment the prince recalls the words of the sage whom he had oft consulted; these twin giants, identical in appearance, were the only living creatures who know the safe pafe to the fabled castle. Yet he has a dilemma, for one of them always lies while the other always tells the truth, and what is worse, no-one may ask either of them but a single question.

Making the wrong choice of path will lead inevitably to peril and the ultimate failure of his quest. Only one of the roads provides a safe route directly to his goal. Not willing to let the fate of his realms rest in the hands chance, the prince knows he must ask one of the giants the question that will tell him the safe path – but which giant, and what question?

Now, before continuing, do ponder for a while the nature of this paradox, if you are not already. I do promise  that this dilemma does in fact have a sane solution, and unlike other paradoxes, is not a fundamental contradiction of logic and reason. Read on only when you wish to see the answer, and more relevantly, the formal (mathematical) method we can use in treating such a paradox.

Mathematical (or formal) logic is arguably at the heart of mathematics itself, and is to many the foundation of all science, philosophy, and general reason. Logic is unfortunately not such an intuitive thing to we as humans (without exception) – at least, beyond the very superficial level. Certainly, what has developed into the field of formal logic (in particular modern research into higher-order logics) would make little to zero sense to anyone discovering it upon the first time. It does not take much consideration to realise that the human mind, not unalike to those of other creatures, is one tailored by the eons of evolution to the tasks of survival and continuation of the species. Indeed, we were never remotely designed to unravel the mysteries of the universe, and it is only through our higher level capacities developed through other means that we may begin to do so. (That is at least the brutal atheists approach, and I am among those who would argue the point at a higher level.)

Without assuming too much prior knowledge of fundamental mathematics, specifically formal logic, I will now introduce an approach to resolving in a (simple?) mathematical manner what initially appears to be a very counter-intuitive situation. Do not fret though, for I myself have barely touched the surface of these areas. Still, for the sake of conciseness, I am going to assume you either have an elementary knowledge of formal logic, or can look up the ideas involved, where necessary. If you haven’t yet seen it, I mentioned a great tutorial for starting out in a previous post. (The Wikipedia pages may be enough if you just want an overview though.)

Firstly, let us formulate the given problem in the language of propositional logic, which involves nothing more than the manipulation of true and false values, in essence. There is no fool-proof way of doing this translation, of course, but read on and I think you will see it all works out pretty well.

Note that I use for the truth value and for the false value here.

To begin let us define the propositional variables and functions we will be using:

By arbitrarily labelling the pair of giants, let represent the truth-telling one and the lie-telling one.

Note that $\equiv$ is not actually a symbol in propositional logic, but just syntax for defining a variable.

Now, using this notation, and carefully analysing the situation (problem) presented in the above text, we can see that the problem is to find a formula for that satisfies a proposition that represents the problem. First, observe that whichever giant you ask, the reply you get will be either or in response.

The proposition that defines the situation is then:

In words, that is: asking the particular question to either giant, you will get the same response (yes/no answer) every time, and this answer will also indicate that you should take path (if true, the “first” path; if false, the “second” path).

Unsurprisingly perhaps, there is no well-defined procedure for finding the correct formula for . (There are in fact a number of perfectly valid/equivalent solutions that are relatively simple.) Now, since is simply a function of the propositional variable , we can quite easily factor out the dependence on and still write without loss of generality as:

If one wanted to be utterly rigorous, one could then take this formula for , substitute it into the problem definition, and use the rules of inference (for whatever formal system) to manipulate it into a form that explicitly gives and . On the other hand, I’d rather not lose any readers I still have at this point, so let’s do things the slightly more intuitive way by using some simple human analysis!

The propositional operator , while defined as the bidirectional application of the logical implication operator (i.e. ), can also be seen as representing equivalence of two formulas. (This can indeed by proven formally, though again it’s not really worth the space here I feel.)

Taking the original proposition, we can see (again, with a bit of higher-level analysis) that it implies both:

and

By straightforward substitution for , and a bit of simplification, we can then deduce that:

With the understanding of as representing identity, as previously stated, we can substitute the values for and back into the previous formula to get the following.

Problem solved… right? Well no, not quite actually. If we had mechanically applied the rules of inference from the axioms and the formulaic representation of the problem, we would undoubtedly be able to stop at this point (requiring a good few more pages of derivation however). Since we have not been completely rigorous, we must now prove that this definition of is indeed a correct solution to the problem. Let us substitute the formula back into the problem definition and see.

Hence, we now know that the above solution is correct. What remains is only to translate this formula into plain English. Not so trivial, I think we would agree. The first thing to note is that the parameter is unknown to the prince who asks the question. Well, enough hints…  let’s see if anyone can figure it out first (no cheating), and I’ll update the post with an answer in a few days.

I have recently taken it upon myself to dig into the wonderful world of formal logic in mathematics. Starting off with propositional logic, and quickly moving on to predicate (first-order logic), it is already striking me as a highly interesting subject. (One that can surely get very complex, and is currently still an active area of research). Although I’ve known about the topic and vaguely what it concerns for some years now, I was only properly introduced to while reading Gödel, Escher, and Bach (an excellent read, though not perhaps as revealing or ground-breaking to someone with a bit of solid background in pure mathematics and/or AI).

Now to the point of my post:  I have recently found a marvellous resource on the subject of formal logic; this website provides a gentle yet thorough introduction to both propositional and predicate logic (among other things such as set theory and recursion), along with interactive exercises. Between spending a few hours over a couple of days reading through it and a bit of discussion with someone who knows the subject has given me a pretty firm grasp of the conepts and maths behind it – at least I’d like to think. I know (perhaps foolishly) plan to go on to learn about such crazy topics as higher-order logic, categorical logic, type theory, model theory, and so on. Finding such an elucidating resource for those might be rather more challenging, though I have a few books in hand that I may review if all turns out.

As I promised, I have finally gotten around to evaluating the effectiveness of taking lecture notes using an Eee PC (a first model version, borrowed from a friend). I say evaluate, but I am effectively referring to one thing: the annoyance of typing mathematics in LaTeX on a keyboard less wide than my handspan. Although as a physicists student, this plan has turned out not to be the most effective, I would be inclined to think that many of the problems would be eliminated if you were just taking notes for a history lecture or such (pretty much any humanity for that matter, including law, as I’ve been told). Regardless, reST is at least a pretty nice format in which to write, and using doctutils to pdf-ify the notes is still the way forward, I would say. So to summarise, the quite horrible ineffiency (and concentration required) of typing was the main reason that led me to abandon the (initially very hopeful) endeavour by two weeks into term. I can’t be sure how much one of the newer Eee PC models would have helpd me – somewhat, but not hugely, I would think.

As it is, I am fortunate enough that all my lecturers have decided to hand out printed (and generally pretty complete) notes for the subjects this term. Me, being the lazy student I am, am finding it a good excuse to not bother with any notes for the current term. Saying that, at least it’s letting me focus more on actually understanding the (painfully opaque) material of the current courses, which is surely a good thing!

Well, at the least, I hope I have give some thoughts to anyone else considering a similar plan for lecture notes. It would be actually be quite satisfying to hear if there are any humanities students out there that have adopted the reST/PDF approach. Equally so, I would  be rather surprised if any science guys have managed to make the thing work with an Eee PC.

Creating a modern computer algebra system from the ground up, as has been a plan of mine for some months now, is no trivial goal, as anyone who has even a vague conceptual understanding of computational algebra must surely know. My efforts in this area, grouped under the title of “the Syracuse Project“, have involved mostly research and large amounts of contemplation so far, but I feel that I have finally managed to formulate enough solid ideas that they are worth presenting in a short article. I was also fortunate enough to find someone on IRC (in #math-software on Freenode) with whom I could discuss and refine many of our mutual ideas. The ideas discussed in this post are the culmination of my own thoughts and much of the knowledge I gained from my conversations with Robert Smith (nickname ‘Quadrescence’) online, which has served as the basis for some of my own investigation and explanations here, in a modified form.

What I am going to focus on here falls mainly under the domain of my Euclid.NET project, which is essentially the core of Archimedes, which one might describe as the “CAS kernel”.  Think of Euclid.NET as the framework for symbolic mathematics upon which Archimedes is built. Its primary purpose is to handle such tasks as expression evaluation, simplification, differentiation, series expansion, and so on. (Bonus points if you can spot the connection between the names of Archimedes and Syracuse.)

TeX.NET, which is the primary parser (expression tree builder) for the project at this moment, has already seen a stable release, and will soon see the second with any luck. As you might guess from the name, it takes input in TeX syntax (well, actually LaTeX, with a few extensions).

To begin, I thought I would tackle one of the tougher aspects of computer algebra systems, namely, simplification. More trivial features such as expression evaluation and differentiation are essential to a CAS, yet are hardly worth an in-depth discussion, at least not for now.

So what is simplification?

Simplification, to state the banal, is concerned with making an expression more “simple”. Unlike many every terms that have been borrowed by mathematics, “simple” or “simplification” truly does not have a more rigorous definition. The problem here largely stems from the fact that the definition of what is simple is somewhat fluid – it depends to a great extent on the context. To illustrate this nature more concretely, here a few examples.

1. or ?
2. or or ?
3. or ?
4. or ?
5. or ?

A visualisation of a very simple expression tree. The equivalent infix expression is (2 + 2) + (2 + 2) + (3 + 3). Note that in general such trees are not restricted to be binary.

I think that anyone who has had sufficient experience using maths and manipulating many formulae and expressions will realise that in some scenarios, one of the given equivalent expressions in 1 to 5 is desired in a certain scenario, while another is desired in a second situation. Hence, any conceivable simplification algorithm cannot be treated as a rigid mechanical process, bur rather must adjust itself depending on the parameters it is given, which hint at the sort of result that is desired.

When humans perform simplification of mathematical expressions, they often use so-called intuition, developed from much prior experience, along with trial and error, to (in most cases) quickly and accurately simplify maths. It is inevitable that even the best mathematicians hit dead ends when trying to simplify complicated expressions. A computer, perhaps unsurprisingly, cannot do any better. Moreover, mathematical simplification is, in my view, one of the few aspects of mathematical methodology that overall better suits a holistic intelligence, rather than the traditional sequential one that is most often associated with maths (theorem proving being a notable exception). In fact, mathematics is not all so logical and all-encompassing as even mathematicians not long ago thought – thanks to the magnificent Incompleteness Theorem proposed by Kurt Godel in the 1930s – this is however a subject for another day.

How can we measure simplicity?

Fortunately, and perhaps surprisingly, the field of evolutionary computation presents a rather handy way of treating the “simplicity” of expressions, that is, a fitness function – in its most abstract sense, something that measures the absolute “fitness” of any given solution for a certain optimisation problem (most commonly genetic algorithms, which lent the term “fitness”). The “fitness” may be thought of qualitatively as the value, worth, or suitability of a particular solution. The solutions, in this case, are of course expression trees.

To begin, it is greatly helpful to reduce the problem by extracting a certain (small) number of parameters from the expression tree, rather than trying to analyse the entire thing holistically. This reduces the parameter space (the set of all possible parameters) dramatically, which is typically highly beneficial in optimisation problems. The fitness function itself is allowed to take any form in general, though we shall see shortly that one or two classes of function in particular are desirable. For now, let us just focus on the set of parameters. After some consideration, I came to the conclusion that any effective parameter space must consist of the following variables:

• Size of the expression tree (i.e. the number of nodes)
• Height of the expression tree  (i.e. the number of layers)
• Width of the expression tree (i.e. the number of nodes in the bottom layer).

These are all of course integer values, and thus the value of the function is restricted to lie within the set of integers. After building up an image that measuring simplicity is a tricky thing, this may seem like a rather straightforward framework; indeed, it is in some ways, thought it is worth noting that the apparent problems arise when we decide what function to use and when it should be applied. The reasons for the choice of these parameters should become apparent soon.

Let us first consider a basic fitness function that simply weights each parameter individually in a linear combination. In other words, the fitness function, may be defined as the following, where S, H, and W correspond to the size, height, and width of the expression tree respectively.

The constants a, b, c may be any integer (postive or negative), and should be passed to the simplifier routine rather than predefined, according to the desired output. It should be quite evident that by choosing different magnitudes as well as signs for these constants, each of the three parameters may be independently rewarded or penalised to greater or lesser extents. The question you might then ask is: why not a more complicated function depending on S, H, and W? My answer is a straightforward one: there is no need. A linear combination of terms gives enough control over the desired function that extending to the function to add higher-order or even exponential terms would be quite pointless and arbitrary. I have, however, far from closed my mind on this matter – as I design and test the system progressively, certain discoveries may be made that suggest a slightly different approach.

Indeed, my only other real consideration for a fitness function thus far is one of even more basic form. Suppose, for example, that the fitness function only depended on two things: a) which parameter should be prioritised, b) whether this parameter should be promoted or demoted. The other two parameters would simply be minimised in the case that the first shows no preference between two trees. I have not finalised the implementation of this, but hopefully this brief description should give you an idea.

I now only leave, as an exercise to the reader, the five example expressions given in the previous section, and considered how any desired result (simplified form) can be achieved through the selection of the appropiate fitness function (using either of the two I have just proposed). Of course, feel free to post a comment regarding any queries or findings you have regarding this matter.

An effective algorithm for simplification

So far, I have discussed how simplicity can be measured in absolute terms, and how in this way the most “simple” of a set of solutions (expression trees) can be chosen as the result of the algorithm. What I have not really mentioned, however, is how an algorithm might actually search out the possible solutions. Although the nature of the algorithm is mainly independent of the fitness function  and the evaluation of expression trees, it is helpful to discuss this second so as to give a clearer image to the approach as a whole.

Simplification when done by a computer, as when done by humans, involves at its heart the application of a large number of mathematical rules that transform expressions. To give some examples of a few of the more basic rules:

Given a complete set of all simplification rules, we can find a path (or derivation) between any two equivalent expressions. (In theory, this is no issue, since the set is finite, though rather large. The practicality of  all the required rules is another issue that I will not go into here.) Note that the rules are bidirectional; they allow you take a simple expression and sequentially transform it into an arbitrarily complex, yet still identical one. (For example, .)

Assuming (quite reasonably) that this assertion that a “finite number of application of simplification rules can derive any equivalent expression from the original” is valid, we must then consider how the search should proceed. Under the utterly naive brute force approach, the algorithm is clearly non-terminating, but we can do a lot better than this.

The search algorithm is all about compromisation in essence. If we search every possible derived expression (up to a certain size), then it could take an unreasonably length of time to simplify even relatively tiny expressions. On the other hand, we make too many assumptions and cut off many branches in the search tree prematurely, the algorithm may terminate quickly, though not necessarily with the simplest solution (or even anything close). Hence, the idea of using genetic algorithms, albeit initially appealing, is in my view to restrictive to a problem that requires a “perfect” answer in most cases, and should not have any stochastic nature.

My currently planned approach is one that does not differ greatly from a simple brute force evaluation of all the simplification paths. The main improvement is one that falls out rather naturally from using a fitness function. The idea is that each node of the search tree is evaluated by the fitness function upon its creation, and if the fitness is below a certain (specified) threshold, the search from that particular node terminates. For a start, this prevents originally small/simple expression trees being transformed into ones that are absurdly large, while still allowing some limited expansion of expression trees in the hope that they may later be simplified very effectively. Many nonsensical (what we might call counter-intuitive) paths of reduction of the expression would also be eliminated in a similar way. There is also one practical problem of important note here: many disparate simplification paths along the tree do converge to the same solution during a search (some quite quickly), so it would be quite foolish to branch twice from identical nodes of the search tree. Instead, we really want to cache any nodes (expression trees) already visited during the search process, and not compute their descendants (derived children) more than once. A simple hash table (set, in fact) would seem like the most effective way of accomplish this. Creating an efficient and relatively collision-free hash function for an arbitrary tree structure is however no trivial task. I was to get a number of quite sensible and useful responds when I asked the question on StackOverflow.

Apologies if this discussion of “search trees” and “expression trees” and their corresponding nodes has led to some confusion regarding what is what. It is most important to recognise that the node of a search tree is itself an expression tree (what I sometimes call a “solution” to the “simplification problem”). Due to the risk of losing reader interest at the cost of an even longer post, I shall stop my ramblings here, and leave further elaboration of the search algorithm for another post.

The future of the project

What has been discussed so far is largely theoretical, yet I have tried to present it in such a way that the method of implementation is for the most part self-evident. Work on this project will likely proceed slowly in the short-term future, though as it advances, the features will surely solidify. I am hoping that at least by summer there should be some tangible results to these efforts. Regardless, I shall try to give status updates along the way.

In case anyone is interested in reading the essay I wrote for a college assignment, entitlted “The Future of Space Exploration” (no need to explain the topic I think), I’ve made the full article available to read here. Be warned, however, it is around 3,500 words of mainly rambling – though the content isn’t too technical, I’d like to believe. As always, I would be curious to hear whatever opinions readers have on the subject and my writings.

These  famous words of the French philosopher Voltaire are probably better understood as one of the many examples of his keen wit, rather than a profound statement; yet they do contain a certain poignancy. The self-referential nature of this quotation makes it so wonderfully ironic and perhaps even paradoxical. As with so many quotes that are worth knowing, there are often several levels of meanings: some obvious, others concaled; some sincere, others facetious. I would in fact beg to disagree with the title of this post (though I, as perhaps anyone) cannot say whether Voltaire made this comment literally or not. To me, it is the very nature of most, if not all, witty quotes, to in some way express a deeper truth – in some respect I think it is part of the definition. After all, truth is beauty, they say.

Enough of this meta-discussion, though. The purpose of this post is really just to share the small selection of the more memorable quotes I’ve picked up over the years (or at least the ones I’ve managed to jot down before they slipped away). Indeed, rather than launching into a commentary here of all the quotes, I thought it would be better simply to list them as a (hopefully dynamic) collection, leaving it as an “exercise for the reader” to gather what interpretation they will from the words. It is my opinion that they are both better understood and appreciated in such a way – at best it gives the reader undesirable preconceptions, at worst it demeans the thing.

Well, here they are then: my collection of quotations, aphorisms, adages, or whatever you want to call them. I’ve written them in what I believe to be their most commonly accepted form, and attributed them to their most widely acknowledged sources. Nonetheless, I have little doubt that some of them have been distorted, and may even be apophrycal, yet this never made a difference to me and I don’t see why it ever should from any but a historical perspective. Good sayings are often improved over time, sometimes so much that they cannot be attributed to any more than folk wisdom. Whatever they are, they certainly give pause to ponder.

Note: The juxtaposition between the more profound and the more humurous quotes below may seem slightly awkward, but I feel it would be too artificial to separate them out in a clear-cut fashion, so read them as you will.

Socrates (469 – 399 BC) – Ancient Greek philospher

I cannot teach anybody anything, I can only make them think.

Education is the kindling of a flame, not the filling of a vessel.

I know that I am intelligent, because I know that I know nothing.

The unexamined life is not worth living.

Plato (428 – 348 BC) -  Ancient Greek philospher

Be kind, for everyone you meet is fighting a hard battle.

For a man to conquer himself is the first and noblest of all victories.

Courage is knowing what not to fear.

Excess of liberty, whether it lies in state or individuals, seems only to pass into excess of slavery.

Wise men talk because they have something to say; fools, because they have to say something.

Voltaire (1694 – 1778 AD) – French Enlightenment philosopher

Judge a person by their questions, rather than their answers.

He who thinks himself wise, O heavens! is a great fool.

Prejudice is opinion without judgement.

The multitude of books is making us ignorant.

I disapprove of what you say, but I will defend to the death your right to say it.

Common sense is not so common.

This agglomeration which was called and which still calls itself the Holy Roman Empire was neither holy, nor Roman, nor an empire.

Oscar Wilde (1854 – 1900 AD) – Irish poet and playright

Man can believe the impossible, but can never believe the improbable.

What is a cynic? A man who knows the price of everything and the value of nothing.

A man who does not think for himself does not think at all.

Nothing that is worth knowing can be taught.

Albert Einstein (1879 – 1955 AD) – German theoretical physicist

There are two ways to live: you can live as if nothing is a miracle; you can live as if everything is a miracle.

Science without religion is lame, religion without science is blind.

Logic will get you from A to B. Imagination will take you everywhere.

The important thing is not to stop questioning. Curiosity has its own reason for existing.

Everything should be as simple as it is, but not simpler.

Once we accept our limits, we go beyond them.

Small is the number of people who see with their eyes and think with their minds.

Try not to become a man of success but rather to become a man of value.

Imagination is more important than knowledge. For knowledge is limited to all we now know and understand, while imagination embraces the entire world, and all there ever will be to know and understand.

Common sense is the collection of prejudices acquired by age eighteen.

Mark Twain (1835 – 1910 AD) – American author

All generalizations are false, including this one.

Do not put off till tomorrow what can be put off till day-after-tomorrow just as well.

Good friends, good books and a sleepy conscience: this is the ideal life.

The man who does not read good books has no advantage over the man who cannot read them.

Never let formal education get in the way of your learning.

It is better to keep your mouth shut and appear stupid than to open it and remove all doubt.

Karl Weierstrass (1815 – 1897) – German mathematician

When I wrote this, only God and I understood what I was doing. Now, God only knows.

Oliver Heaviside (1850 – 1925) – English mathematician and physicist

Why should I refuse a good dinner simply because I do not understand the digestive processes involved?

As I said, I hope to update this list over time as I pick up more – do however please feel free to suggest any particularly worthwhile along the same themes expressed here.

Over the past few weeks my interest in conceptual information systems has very much been rekindled. This is largely thanks to reading and talking about a certain paper by a developer friend of mine, which discusses the ideas and implementation for his MrMoe framework. Although the project has only recently been announced, and the paper won’t be released publicly for a bit of time yet, many of the ideas are already quite well-formed, and along with my ongoing curiosity relating to the Semantic Web and RDF, have stimulated me to write something of my own thoughts on the topic. (A couple of overly-ambitious projects involving RDF are likely what caused me to put aside the subject for a while.)

Discussing RDF or MrMoe is not the purpose of this post (I’m sure the author, Jan, will however do so further in the near future), so I shall leave these aside for the moment. I will however (somewhat boldly) state that the system I am proposing is significantly more abstract and, I hope, more powerful than either, at least in theory. Saying that, I think all these systems had slightly different applications in mind when designed. Enough preamble though – I don’t wish to create any (more) premature hype. Let me now introduce you to my incipient system.

RAKIS – or the RAKIS Abstract Knowledge and Information System – is my name for the model and associated theory I have invented in the vision of representing information in what I foresee to be a most abstract, context-free, and yet highly structured manner. Do note the use of the word “information” here; this system is not designed simply to represent data, but moreover meaning. It is what one might term a “semantic model”, though this falls short by a long margin from giving any true impression of its potency and overall utility.

My aim in this article is to begin with a very simple model and build it up in small steps, eventually reaching the full RAKIS model. I am hoping that this incrimental approach will allow readers to gradually build up understanding of the concepts and the “flavour” of the system, and to appreciate its great flexibility and potential by the end of the article. Although many with a higher-level education in mathematics will observe that much of the model can be described in terms of graph theory, I will try to stay clear of its formalities and jargon (or at least not rely on them).

Let us first construct a set of nodes that represent our basic concepts. These starting concepts might loosely be described as the “nouns” of the model. For want of a good simple example, I will use the Bach family (as you will see later in this and coming posts, this will serve well because of its many associations). Do not let the simplicity of the example fool you – subsequent ones will give you a better understanding of the capability of RAKIS.

The nodes in this diagram represent various members of the Bach family.

Now, there’s nothing very interesting about this diagram (or graph, to use the technical term), though there is one crucial subtlety to point out at this stage. The labels attached to each of the nodes are not truly part of the model, and must only be considered as aids to the viewer. (To throw in some jargon, this graph may be termed an unlabelled graph, despite appearing to be otherwise.) Visualise the same diagram without any text, and you might ask; what would such a model without labels possibly mean? How could it even vaguely represent any form of useful information? To be frank, it does not, as it is. The graph certainly represents data, but has little (if any) inherent meaning. You will see shortly that the meaning is introduced naturally, rather than being directly imposed, as is almost ubiquitous in traditional systems that organise data/information, and even more modern ones such as RDF.

The following diagram incorporates relationships (what I term links)  between the various nodes (or concepts) of the model. The way I have chosen these relationships is both somewhat arbitrary but also quite deliberate. It should be evident from the diagram that these links simply represent parent-child and husband-wife relationships, in the direction of child to parent. (Note that J. S. Bach was married twice during his life, and had a number of musician children by each wife.)

The nodes represent members of the Bach family, and the arrows the relationships between them. The direction chosen for the arrows is arbitrary, but must be semantically consistent.

Now you might be beginning to see the inklings of meaning in this model, given of course the pre-defined knowledge that it relates to the most famous members of the Bach family. Still, it gives a strong idea as to the structure of this certain family.

Our next step is what truly starts to make this system interesting. At the moment, the model may simply be described as a graph with the edges representing the links between concepts. By treating the set of edges as the nodes for a higher-level graph, we can extend the model to represents “relationships of relationships”. Note that other nodes (or concepts) can be introduced at this second level that do not correspond to links of the first level, such as the “Family Relationship” node in the following diagram.

The nodes represent members of the Bach family, the solid arrows the relationships between them, and the dashed arrows the relationships of relationships, or "meta-relationships" (note that they are still directed).

Where the real power of this model stems is the recursive nature of links (relationships). One need not stop at meta-links, but rather one can proceed to create higher and higher levels which progressively represent more and more abstract information. Nor must (meta-)links necessarily join concepts in adjacent levels, but can rather link any concepts, provided that the arrow is in the direction of the higher-level concept. Unsurprisingly, the base level simply represents data, or in other words, the most concrete concepts within the system. Although it is not necessarily apparent here, the highest levels should theoretically be capable of describing very abstract ideas, making the system much more effective at relating seemingly disparate pieces of information, and possibly even performing some forms of logical inference and reasoning.  I hope this will be demonstrated explicitly in my next post on RAKIS.

The final point to stress is the implicit manner in which this model represents information. Given the appropiate context or “hints”, one can deduce easily enough what the graph represents (the significance of the concepts and relationships) without need for any labels on the nodes. Clearly, if you were presented with the above diagram, it would be virtually impossible to figure out that it corresponds to the Bach family (and hard enough to realise it corresponds to a family, even). However, if the graph were to be extended (it is not designed to exist in its isolated form) so that it interfaces with something outside of the system, the set of possible interpretations quickly diminishes until it is quite obvious what the model represents.

To give a fairly blatant example an interface, each concept in the graph shown above could be linked to two nodes, one from a set of forenames, the second from a set of surnames. These sets of names would exist external to the system, and would simply map to what you might call “interface nodes”. The advantage of utilising this design is that the model still retains its implicit meaning (no need of labels), when put into an appropriate context. In addition, this context-free nature of the model allows arbitrary (albeit relevant) isomorphisms, which only serves to increase the power of the model to associate different concepts on the surface at a deeper level of abstraction. This is highly important if your goal is to perform any sort of formal reasoning using the system, which is much of the aim of RAKIS.

An intriguing extension to the proposed model, on which I will just briefly touch now. So far I have treated all graphs (in all layers) as unweighted, meaning that an edge (link) either exists or does not. In a weighted graph, each edge would be assigned a real value (typically within a restricted range). By applying this feature to the RAKIS model, I would hope to open the doors to the possibilities of performing advanced types of inference, and perhaps even machine learning. (The latter would involve “growing” new concepts and increasing the strengths (weights) of links when certain criteria are satisfied. Although I do not want to suggest too much similarity, there is some analogy to artificial neural networks here. Not to worry if this paragraph little sense, however, since I will be elucidating this aspect of the system in a future text.

By now I’ve probably bombarded you as readers with enough of my theory (for the time being), so let us just summarise the key points I have already introduced:

• The fundamental features of the RAKIS model are concepts and links, which can be thought of as nodes (vertices) and relationships (edges) respectively.
• Concepts are unlabelled, in that their meaning is implicit and can only be inferred from context. Some sort of interface, bridging the system and the external world, is typically required to instill some form of meaning.
• Links represent connections between concepts, such as a parent-child relationship, as given above. They are directed arbitrarily, but must be consistent with each other.
• Both concepts and links can be extended to higher levels so that they represent “meta-concepts”, “meta-links”, “meta-meta-links”, and so on.
• Base-level concepts represent fairly concrete ideas, while higher-level ones (“meta-concepts”) represent progressively more abstract ideas.
• Due to the highly fluid and context-free nature of the model, isomorphisms (parallels of sorts) can be recognised between various subsets of concepts relatively easily. The implication of this is that meaning is not fixed, but is rather context-dependant.

Note: Italic terms present in this article are typically used to highlight elements of the terminology I have chosen for RAKIS.

That concludes the first post of what I intend will be a series on the RAKIS system. Just a teaser for my next post: it will be demonstrated how various logical and mathematical ideas, such as sets and prime numbers, can be expressed formally by RAKIS. Well, I hope that this introduction has at least given readers a decent grasp of the power as well as the design of the core model. If you feel anything needs clarification, or simply have general comments about this post, feel free to leave a comment.

Some news to report at last! I’ve just released the first the first beta version of my TeX.NET project over at Launchpad. Both the source (with unit tests) and binaries of what might be called “a parsing and writing library for mathematical expressions written in the TeX format”; programmed, of course, in C# 3.0 (with some rudimentary F# bindings).

This project hasn’t exactly been the focus of my blog posts recently (or at all, for the matter), mainly because I’ve found that working on the thing has taken almost all of my free time over the past month or so.  As I have come to learn, putting effort into promotion of ones ideas and work is not a wise thing to do before they have proper substance!

Since I’m not one to reword any text that I’ve already (quite carefully) written, I shall quote the project summary over at Launchpad:

TeX.NET is a library for the .NET Framework 3.5 that provides lexical analysis and parsing of mathematics written in the TeX format into expression trees, and conversely the writing of expression trees in the same textual format. The purpose of the library is to provide a useful framework for inputing, outputing, and manipulating complex mathematical expressions.

Now, you may of course be curious where I’m taking this project in the grand scheme of things. (Indeed, a library for parsing of mathematical expressions isn’t terribly useful on its own.) Although it’s far from an in-depth explanation of the end goals and my approach, I suggest you check out the Syracuse Project, which is the “container” or “super-project” for TeX.NET, among other related libraries and programs. I can however say that I will be shifting my efforts more towards the Euclid.NET project, now that I have a stable initial version of the requisite parser/writer library. It is bound to be the subject of one of my upcoming posts, anyway.

So, if anyone is inclined to give my TeX.NET library a whirl (or better yet, some further rigorous testing), I would urge gratefully them to do so. Any sort of feedback on this project is welcome, as with all of my endeavours. My aim the moment is mainly to garner a nucleus of interest and see this library applied to great things!

The Hungarian algorithm, also known as the Kuhn-Munkres algorithm, is well-known to be the most efficient algorithm for solving the assignment problem. In fact, it does what is considered by many to an exponential time algorithm (more specifically, factorial time), in O(n³).

The Wikipedia page describes the general form of the problem quite well.

There are a number of agents and a number of tasks. Any agent can be assigned to perform any task, incurring some cost that may vary depending on the agent-task assignment. It is required to perform all tasks by assigning exactly one agent to each task in such a way that the total cost of the assignment is minimized.

However, the implementation of this algorithm is far from trivial. In fact, for all my Googling, not a single implementation in C# turned up (though there was at least one in each of C, C++, Java, and Python). Given this opportunity, I took on the task of porting this code given on this page in the Ada language, to C# 3.0. With almost 300 lines of code, and a bit of debugging with the sample problem,

You may download the complete code for the algorithm, in C# 3.0, here. It is contained within a single static class that exposes an extension method that operates on a matrix (2D array), for ease of use. Although I believe that as an almost line-for-line port of the Ada code, there should not be any issues with my implementation, any bug reports would be appreciated.

Updated 15/10/09: Several bug fixes have been made that fix issues (most noticeably, endless looping) for non-square as well as various other sorts of matrices.

Updated 24/10/09: Fixed bug (endless looping) that affects large variety of matrices involving ConvertPath function.

The Royal College of Science Challenge is an annual competition open to all students of Imperial College London, and something I’ve decided to enter this year. At the present time, the midnight deadline has just passed and I’ve just taken a huge sigh of relief… As is my habit with most things (writings or otherwise), I ended up not even starting work on the submission until the past Friday, which has indeed turned out to be a very unwise decision. Anyway, the good news for me is that I did finally manage to get the essay completed and uploaded at a panicky 11:53 pm. (At this point I half-expected MS Word/Firefox/Vista to crash spectacularly, but my fortune in fact held out for a crucial 15 minutes!)

Now to the contest itself. I should note that everyone, irrespective of year and department, was able to pick any one of the four proposed questions and then proceed to write a 800 word essay on the subject. A disheartening thought if considered for too, but something told me it was worth a shot anyway. My choice was the following (third) question:

Will Homo Sapiens continue to evolve? If so, how?

For those who don’t know, I am currently studying for a Physics here, and haven’t taken biology for several years now – so it may initially seem rather silly for me to ignore the others and tackle the least physics-based topic of them all. (In actual fact, it figured that I had far too much to say and the awfully low word limit was the source of much exasperation for me!) An interesting short article in the January issue of this year’s Scientific American had gotten my pondering the issue lightly before I even new of the contest, which is probably half the reason. Although I’m sure I could have done a decent job of one or two of the others (certainly the one on the LHC, I would think), I guess the open-ended scope of the evolution one caught my fancy at the moment. Enough said – I do at least feel pretty satisfied with the end result. In getting there, I must also mention the kind assistance of my friend David in repeatedly proof-reading it and making some quite insightful suggestions.

Without further preamble, here is my entry.

Each year, the infamous Darwin awards are given out in order to “salute the improvement of the human genome by honoring those who accidentally remove themselves from it” (1). This “award” is of course proclaiming to recognise those people who supposedly perform supreme acts of stupidity and thus assist the process of natural selection in the human race, first described by Charles Darwin in the 19^th century. Behind this purely ironic prize is however a much deeper question: have we, as members of humanity, changed significantly over the recent past, and will we perhaps evolve into something quite different in the near or distant future?

It is commonly believed that our bodies have remained static from at least the time of the birth of civilization around 7,000 years ago. The greatest period of “recent” alteration occurred as the species branched off from those of other primates hundreds of thousands to millions of years ago. A recent study by American two universities[1], however, threatens to entirely reshape this perception of our evolution. It contends that a minimum of 7% of the human genome has changed over the past 5,000 years or so. These scientists even go as far as asserting that “humans have evolved as much as 100 times faster than any other time” (2).

One thing is agreed upon pretty much for sure: human evolution, however significant, will follow a radically path in our future than it has for most of our past. Firstly, it is generally believed that our brain size is not likely to increase anything like it has done in our early history. This is not to say that human behaviour will not be transformed – rather, it is considered one of the most probable of man’s characteristics to do so, thanks to the rapidly changing nature of society and growth of technology. Conceivably the most extraordinary course for our evolution to take is some form of symbiosis with machines. Even presently, human dependence on machines is immense. Economies, societies, and even many individuals require them merely to survive. Perhaps the merging of mind and machine is but the next step in a natural progression? Symbiosis, if chosen by most people, would likely add selection pressure towards purely functional behaviour. The thought of abandoning many of the pleasures of human life may be enough to prevent us from following this route, though it does not remove the prospect that one day our species might seriously consider it. The ultimate human stimulus for evolution may in fact be space travel: such a scattering of the species would be liable to produce great diversification and force adaptation.

Perhaps the most astounding change in the manner of our evolution will come as a result of human intelligence. We are now beginning to understand properly the process of evolution on both macroscopic and microscopic levels. The very fact that we are aware of such a process working upon ourselves is exceedingly likely to alter the “natural” course of evolution, maybe even unintentionally. Our efforts to perform artificial selection have already begun and are currently highly controversial issues (often in such guises of genetic engineering or “designer babies”). These ideas and associated fears are certainly not new; science fiction has long speculated on possible paths that we might take in our search for a “better world”. Aldous Huxley’s classic novel Brave New World, written in 1931, describes a future dystopian society where people are engineered to fulfil certain roles within society, reproduction being an entirely artificial, state-controlled operation. Somewhat differently, Frank Herbert’s Dune series explores a universe in which a powerful organization of women operates a long-term secretive breeding program that aims to produce a man with supreme mental capabilities. The common theme in these works is an important one; namely, that there must exist some relatively small group of individuals who possess the authority to direct the course of evolution and the workings of society. Indeed, we all know to where eugenics can lead. Now let us ask ourselves whether, as inherently fallible human beings, we can be trusted with this sort of power?

The future path of human evolution is an uncertain thing, to say the least. If modern research hints anything at what is to come, we should undoubtedly expect huge change. That we may soon have the opportunity, at least in part, to direct our own evolution, will make it especially unpredictable. Yet if we can make sensible decisions and learn to accept what it outside of our control, we may find ourselves transformed into something rather new and astonishing. After all, why should our species, one so devoted to expansion and improvement, suddenly remain static?

Bibliography

1. Darwin Awards. The Darwin Awards. [Online] [Cited: 28 2 2009.] http://www.darwinawards.com/darwin/.

2. What will become of Homo Sapiens? Ward, Peter. January 2009, Scientific American, Vol. 300, pp. 68-73.

3. Huxley, Aldous. Brave New World. London : Chatto and Windus, 1932. ISBN 0-06-080983-3.

4. Herbert, Frank. Dune. s.l. : Chilton Books, 1965.

---

[1] Teams headed by Henry C. Harpending at the University of Utah and John Hawks at the University of Wisconsin-Madison.

I now only await the news of the shortlist, with some little hope that few enough students of science would bothered to voluntarily enter an essay competition. (Yes, this is a purely unscientific hypothesis.) Regardless, it will soon be seen whether such expectation is in vain.