Llull as Computer Scientist
or why LlulI Was One of Us
Universitat Politècnica de Catalunya, Barcelona
Abstract. Crucial notions on which Computer Science is based originated in Ramon Llull (a l3th-century philosopher from Majorca). Here we explore some of his original insights -and his plausible inspiration sources- and how these ideas have been available to us by way of Leibniz (and others).
Something unusual has happened to Ramon Llull (Raimundus Lullus, 1232-1316), the franciscan thinker from Majorca. He has been at the same time derided and hailed as a philosopher. He has been instrumental in creating our foundational insights as computer scientists and logicians, yet he occupies a very minor place in the histories of Philosophy, Mathematics or Logic. He was one of the first philosophers to claim a logical basis for religious belief yet he has been considered a source of alchemy, cabbalistics and mysticism. He is considered a conceited eccentric fool and -just read Martin Gardner's 1958 piece- a maze of confused thinking, but such indictment hardly squares with the undeniable fact that he had foresights which anticipated developments 700 years in the future. So, what is the truth? and what is the man?
That Llull is really a marginal sidepiece in the history of Western Philosophy 15 clear -as it was to him. And, because he resented it, he innovated, and tried to convince the Parisian intellectuals that his innovative ideas had merit -to no avail. He was not understood at his first Sorbonne appearance in 1289. His combinatorics were definitely not the method to use for logical analysis (causal chaining was). When he came back in 1309-11 with a more accessible system he was greeted with a flurry of sympathy rather than real acceptation. Some found in him a firm advocate of basing faith solely on logic, and all understanding on reason (against the revelationists and the mystically-inclined). But after his death the sympathy faded out, a victim of the Inquisition and the dominican-franciscan l4th-century struggle. In an ironic twist, Llull, who had always put logic before faith, and had done this by propounding innovative ideas, became a thinker derided by the first science pioneers (Bacon or Descartes, who had a lot to thank him for), while he became the hero of alchemists, cabbalists and general mystics (thanks to being attributed authorship of esoteric apocrypha). The usual charge today (for Gardner, as it was for Descartes), that his thinking was actually confused, is not the whole reason for the misrepresentation of Llull's thought: confusion between religious faith, ethical motives, apologetics and natural explanations was the rule rather than the exception in medieval philosophy. As for his own equivocations, it is a well-known fact that all innovators muddle through their own discoveries -the full reach of which they do not usually grasp- and even extrapolate wildly from them. Llull's peculiar innovations, strange as they seemed at the time, sound familiar to the modern ear. Here we list some of the more typically Lullian.
2 Some basic Computer Science concepts
2.1 The idea of a Calculus
That logical reasoning is, in some sense, computation -or, more properly, that it can be formalized and validated by controllable means- is now an accepted idea, clearly explained in the writings of 1920's logicians (Hilbert or Herbrand, to name two) and actually mechanized in the 1960's. But the notion was advanced in the l7th century by Hobbes, who wrote in 1655 that "reasoning is but reckoning", and by Leibniz, who thought in 1658 (and wrote in 1666) that, in the future, philosophers would settle their disputes as accountants do, just by taking pens and calculators (abaci) and proclaiming "let us compute!". Leibniz explicitly stated that this was Llull's dream made true. It really was. Llull had anticipated this in 1274 by noting that, to convert muslims (a current worry), public disputations were fruitless (the ones attempted in the 1260's ended circularly, with nobody convinced), so one had to find a mechanism to prove and generate truths in such a way that, once everyone agreed on the assumptions, the objectivity of the procedure would force all to accept the conclusions. The elaboration of such a mechanism took his lifetime's efforts. Though Leibniz explained the idea in concise and appealing terms, Llull himself could have suscribed his admirer's formulation, stated 400 years later. Moreover, Llull's "mechanism" was not a merely abstract procedure; it was supported by truly "mechanical" means, his rotating concentric rings. Now easily dismissed as banal toys, they were the first such devices on offer. From this elementary mechanism, and by simple mechanical manipulations, a whole heuristic followed and a deductive chain of truths was combinatorially generated, to be later explored and validated.
2.2 The idea of an 'Alphabet of Thought'
When George Boole tried in 1847 and 1854 to find out -and formalize- the "laws of thought", he basically conceived "thought" as a set of algebraically-expressed concept manipulations. Llull in 1274 also did, but unlike Boole he felt he not only needed a set of allowable manipulations (combinations) but also a finite set of elementary truths to begin with. These he called "dignities" (a plural to translate the greek "axioms") or "absolute principles", nine in number, plus 45 additional basic concepts (in groups of nine) he called "relative principles" (including consistency or contradiction), "rules" (including quantity or modality), "subjects", "virtues" and "vices". He added them basic manipulation rules (essentially a relational calculus) and a validation procedure (basically, expanding possible combinations and following them until either two concepts reinforced themselves -thus lending credence to the conclusion- or else a contradiction appeared -which meant that the hypothesized conclusion had to be negated). As Boole later, Llull firmly believed that human thought (logical reasoning) was amenable to symbolic treatment, unified procedures and objective follow-up and control.
2.3 The idea of a Method
Not every philosopher in Llull's time felt compelled to delineate clearly a general method, follow it strictly and pretend this was universal. This rather modern concept comprises Hilbert's "effective procedure" idea, or Turing's machine algorithm, but nothing of the sort existed before Descartes suggested the existence and applicability of a universal "method" (1637). Though he did in no way acknowledge his Lullian debt, Descartes -who knew Llull's work well- did for philosophy what the Majorcan had suggested for logical inquiry in general: establish a set of rules, if possible permanent and universal, and follow them strictly.
2.4 The idea of Logical Analysis
Llull's idea was to analyze basic concepts by associating them one to each other and see what happened. This, to him, was tantamount to penetrating the inner workings of God and nature, and so to understanding the world better (and giving an effective, objective account of it). If faith (or even mystic revelation) was reached in the process, then Llull's ultimate design purpose was accomplished, that of founding faith on reason, and of justifying beliefs through logical analysis. The originality here was that this was done in practice by mechanically executing an iterated expansion of a given set of initial beliefs (a core or "compendium" of truths) until, should the case arrive, a contradiction obtained. By postulating such a procedure Llull was in fact anticipating the modern (1955) idea of semantic tableaux. (More of this later.)
2.5 The idea of Heuristics and Deduction
Llull was interested in finding out new truths as well as proving -i.e. being able to convince anyone of- old ones. The last part is subsumed in what we ordinarily call deduction. The first one ("finding") is somewhat amazing, though. Modern science has systematically eschewed the analysis of why we discover or invent things. This has been attributed to imagination, to brilliancy or even to serendipity, but nobody has tried to explain, and in no way control, how the heuristic process develops. One reason for that is that we can only "control" it a posteriori, once the idea has arisen: we can then verify whether the predictions it makes turn out to be true or not. This simple reason was clearly stated by Popper in the 1950's during his dispute with Carnap and the idea of "inductive logic". Besides this, there is nothing we have today to find out new ideas except some magnificent insights into the creative process by Polya and others, and a very short collection of hints or rules-of-thumb for systematic exploration, be this Fred Zwicky's "morphological" method (an exhaustive combinatorial association) or its more modern computer-oriented counterparts in Artificial Intelligence (complete with more or less ad hoc techniques we AI-ers pretentiously call "heuristics"). What catches the eye most is that a thorough-modern method as Zwicky's, with its exploratory and pairing algorithms and tables, is strikingly similar, even in its outside appearance and paraphernalia, to the visual tools of Llull's. Needless to say, Heuristics as a science (if it ever was one) is nowadays in the same sorry state in which Llull found it.
2.6 The idea of Generative Systems
Perhaps the most striking of Llull's anticipations was the idea of having a finite set of rules as well as a finite set of truths -"basic concepts", axioms or whatever you call it-, so that you can then generate from them a (presumably infinite) set of derived truths. Nowadays we would describe the idea more simply, and say that Llull had just come across the idea of a generative system. In linguistics such a finitistic device is called a grammar (a set of rules to manipulate strings from an alphabet beginning with some initial axioms) and the generated strings are the language. In Computer Science the device is called a machine and what is being generated is the set of output configurations in a tape. As is well known today, the same mechanism can run backwards: the same grammar that is capable of generating a language is also capable of accepting or recognizing its strings as belonging to it. Or the same machine which computes the batch of acceptable results is also capable of recognizing a correct calculation. (That those two dual processes are slightly asymmetric in computational terms is a corollary of Gödel's first incompleteness theorem and should not bother us here.) Llull was the first to notice this reversible duality: in his terms, the same system that he proposed to derive new truths from a reduced set (an abridged "compendium" of them) and that he called "truth-finding procedure" ("art de trobar veritat" in Catalan or "ars inveniendi" in Latin) and that in Logic we now call simply inference (or "forward chaining") had a dual quality and could be executed in reverse, so that we then have a recognizing or accepting system he called "truth-proving procedure" ("art de demostrar", "ars demonstrandi") and we name simply proof (or "backward chaining" or "goal-oriented search" in AI). Thus, to Llull, if one were confronted with proving some specific statement, one would have to invent no new system: the one that allowed the user to explore new truths would suffice to certify the intended truth, the certification procedure itself being the proof.
2.7 The idea of a Graph
Llull connected his "basic concepts" with lines, and prescribed that the lines had to be followed to combine the concepts and derive the consequences. This was new. Not now, though; we have a name for the device Llull invented: we call it a graph. The two amazing things about this are, first, that Llull gave a dual isomorphic variety of it: he compiled the graph's information in the form of a two-entry table (just what we term the adjacency matrix of the graph) and, second, that Llull's graphs were not meant as mere concept-structuring or taxonomic (tree-structured concepts were available since late Roman times) but were conceived rather as a present-day's "semantic network" and intended to be "followed", i.e. dynamically executed as though it were a truly fact-finding "program" or a decision tree (as in AI) in a decision procedure.
2.8 The idea of Tableaux
The truth-deriving procedures Llull suggested were mainly two. One proceeded in the positive sense: concepts were combined (following the directing graphs) and, if mutually reinforcing, they proved the conclusion "by analogy". The negative dual was that at some point the concepts that were being currently manipulated turned out to be mutually inconsistent (contradictory); that meant that the initial postulated truth was automatically disproved, thereby proving the contrary. This is the first appearance in the literature of something not unlike Beth's 1955 semantic tableaux (or Popper's 1959 refutational ideas in Science). It is, however, a mere l3th-century anticipation of present-day developments, which -unlike all the other insights mentioned- have not been directly influenced by Llull's ideas or by Leibniz's rendition of them.
2.9 The idea of Conceptual Nets
As previously mentioned, Llull's graphs were neither static taxonomical trees nor concept-structuring illustrations but an actual net of links that allowed the user to explore in a combinatorial fashion the relations that existed among the currently manipulated concepts. Thus they were a prefiguration of modern so-called conceptual graphs and semantic networks. They were meant to be not so static or self-structuring but rather they presupposed a dynamic interpretation: to know well the concepts meant -to Llull- to follow their associations and explore their consequences. (The inherent dynamic ontology such a vision gave of things was enthusiastically received by philosophical and scientific innovators like the influential l5th-century Nicholas of Cusa.)
2.10 The idea of Diagrams
The universally known Venn diagrams (actually Euler's) also trace their historical lineage up to Llull. He was the first to represent graphically his "concepts" by circles and link them by superposing and intersecting them (though his aim was not to show whether they had an intersection but to demonstrate that they had a more or less strong affinity). (He also linked the terms of a syllogism with a triangle, in what was later called "pons asinorum".) Llull's circle drawings of concepts became a learning aid in J. L. Vives' hands in the l6th century, and were perfected in the l7th by Sturm or Leibniz -who created a whole (unpublished) logical notation out of them- and finally, yes, Euler (in the 1760's). (Now we call them, improperly, Venn's diagrams.)
3 The origins
An interesting thread for historians to follow is how and where Llull got his own pioneering notions. For some of them we have a hint. Thus, the idea of starting from a finite set of rules to develop a whole system has a remote ancestor in Euclides and the Alexandrian greeks and a more recent and innovative version in Al-Khwarizmi's "algebra" work -that Llull quotes as a source. This book, translated into Latin shortly before Llull's time, created a sensation with its novel idea of rule-directed manipulations and prescribed "algorithms" (a concept and a word derived from the muslim mathematician). On the other hand, Llull's idea of a comprehensive method to encompass such rules and develop concepts was probably a formal extension of a now-forgotten integral part of medieval education: the complex set of elaborated techniques for reminding and structucturing things in human memory in a printless age (actually, Llull's method was developed in this sense by Petrus Ramus in the l6th century and was then an inspiration for Bacon and Descartes). As for the mechanical devices (the rotating disks), we now know that similar "question-answering disks" were on sale in the 1260's or 1270's in Algeria (as tools for divination), and that Llull could well know them before his 1274 formulation. (Llull's disks met an unexpected use in cryptography, when Leopardi first used them for coding, and we can still recognize them in the rotors of the WW II German Enigma machine, a distant echo of Llull's disks.)
4 The consequences
Llull is not a forgotten anticipator, nor a mere precursor. Llull's work, which had to pay the unexpected toll of being augmented with all kinds of apocrypha that were falsely attributed to him, was well known and appreciated by many influential thinkers of the Renaissance and after. He had a strong influence on -but no explicit recognition by- such people as Montaigne, Pascal, Descartes or Newton (who had Llull in his library, a fact that put him on a par with his arch-enemy Leibniz). Giordano Bruno and Leibniz not only got the influence but were not afraid to acknowledge it. Leibniz is our most direct connection with Llull. By looking for a universal notation and a universal way of acquiring and developing knowledge more or less inspired by the methods of Mathematics (his mathesis universalis), he avidly absorbed Llull, critically adapted him and proposed an objective and mechanical way of founding Logic and rational inquiry. In this he failed, after leaving a string of unpublished notes (which included an algebra of thought and a graph formalism), and only some 150 years later could his blocked program be unleashed by Boole's insights. But other Leibniz ideas went ahead, notably his push for concept decomposition and analysis which had two unexpected derivations: (1) the analysis of minute quantities (the "infinitesimals", on whose development and rights his discussion with Newton turned dismally bitter) and (2) the actual construction in the 1670's of a calculating machine (the first practical multiplier, which prompted an unanticipated reflection by Leibniz on the idoneity of the binary system for calculating). Leibniz's thoughtful 1666 'Dissertatio de arte combinatoria' is not only good and interesting reading for today's logicians and mathematicians It is the best criticism and homage that Llull has ever received: by recognizing his merits and adapting his ideas to the modern needs of Science, Leibniz did all to include Llull in our scientific heritage, and did us a favor in the process.