THE COMPUTATION PROJECT VERSUS BOURBAKI’S PROJECT Solomon Marcus Stoilow Institute of Mathematics Romanian Academy [email protected] OUTLINE 1 Bourbaki Mathematics and the Theory of Formal Languages Contrasts and Complementarity within Similarities 2 A. Salomaa and G. Rozenberg versus H.Cartan and A. Weil 3 Primacy of the Axiomatic-Deductive Approach 4 Primacy of Structure against Quantity 5 Past Dominated by Disorder, Low Level of Rigor, Atomistic View Concomitant with the Emergence of Important New Trends 6 Link with the Fields of Social Sciences and the Humanities 7 Contrasting Attitudes towards Foundations and Mathematical Logic 8 Lack of Balance between the Discrete and the Continuous 9 The Rise of Cognitive Metaphors 10 And Now a Magic Event: Von Neumann, Watson-Crick, Salomaa 11 The Calculation-Observation Interplay and How History Repeats Itself 1 Bourbaki Mathematics and the Theory of Formal Languages Contrasts and Complementarity within Similarities Bourbaki project starts in 1935 and aims to rewrite mathematics taking into account the major developments which occurred in the period from 1890 until 1935: ● set theory, ● non-commutative algebra, ● linear representations of groups, ● general and algebraic topology, ● Lebesgue theory of measure and integral, ● functional analysis, ● theory of integral equations, ● spectral theory, ● Hilbert spaces, ● Lie groups and their representations. Bourbaki project starts in 1935 and aims to rewrite mathematics taking into account the major developments which occurred in the period from 1890 until 1935: 1’ A Similar Change, concerning the effectiveness of the mathematical thinking, occurred between 1930 and 1973, the year of publication of the book Formal Languages by Arto Salomaa. In this period, new domains and trends emerged, such as: ● the theory of recursive functions (Kleene, Gödel), ● mathematical logic, ● theory of algorithms (Markov), ● of computability (Turing), ● Post combinatorial systems, ● symbolic dynamics (Morse and Hedlund), ● combinatorics and algebra of semigroups and monoids (a pioneer in this respect being Axel Thue), ● Shannon’s isomorphism between mathematical logic and electric circuits, ● automata theory and its interaction with biology, ● computer science (von Neumann), ● cybernetics (Norbert Wiener), ● coding theory (Hamming), ● generative grammars (Chomsky), ● information theory (Shannon). ● etc. 2 A. Salomaa and G. Rozenberg versus H.Cartan and A. Weil Obviously, it was not possible for one person, under the name of Nicolas Bourbaki, to monitor such a diversity and richness of ideas, theories and results. It was initially a group of about seven very young mathematicians, in alphabetic order: Henri Cartan Claude Jean Chevalley Delsarte Jean Szolem René de Dieudonné Mandelbrojt Possel André Weil But later, some of them left the group and new scholars were added. The project started in 1935. Now we can say that Cartan and Weil proved to be the most creative and perhaps the most active in this project. 2’ With respect to the project started by the 1969 and 1973 books of Arto Salomaa, we now can say that the series of works published by Arto and his associates, culminating with the 1997 Handbook of Formal Languages, is comparable with the series of fascicles published by Bourbaki in the decades before and after the middle of the past century. Moreover, we may claim that Arto and Grzegorz proved to play in this project the role Cartan and respectively Weil played in the Bourbaki project. Arto Salomaa Grzegorz Rozenberg I have personal reasons to believe this because I had the privilege to read and to review the correspondence between Cartan and Weil, a volume of about thousand pages. 3 Primacy of the Axiomatic-Deductive Approach Just like in the case of Bourbaki, whose project adopted the axiomatic-deductive method as its basic approach, in the line of achievements of the whole history, from the non-Euclidean geometries, until Peano’s axiomatics of arithmetics and Hilbert’s axiomatics of geometry, Salomaa and his associates adopted the axiomatic-deductive approach, in full agreement with the developments of the period 1930-1973, in the form of systems of objects, behaving according to some explicit rules. The reason for this choice is exactly the same one as it was for Bourbaki: the need for rigor, for logical accuracy, the need to check carefully the correctness of the inferences of various kinds, the coherence of the statements. In a period of emergence of new ideas, changing radically the existing habits of our brain, the danger of penetration of wrong or misleading statements is increasing. For Bourbaki, the domination exerted in France, in the teaching of mathematical analysis, by the treatise of Edouard Goursat, was scandalous. One of Bourbaki’s main aims was therefore to promote the rigor introduced by Cauchy, Riemann and Weierstrass, and developed further by the next generations. 3’ In the field of formal languages, the literature published before 1973 counts more than thousand items, but it is full of obscurities, while mistakes are frequent. I will mention the case of the most important article and book, Three Models for the Description of Language (1956) (2190 citations) and Syntactic Structures (1957), (15.452 citations) both by Noam Chomsky. In the presentation of the 1957 book, included on the web page of Google Scholar, it is considered to be “… the snowball which began the avalanche of the modern «cognitive revolution». The cognitive perspective originated in the 17th century and now characterizes modern linguistics as part of psychology and human biology”. These pioneering Chomskian items are obviously cited already in the first chapter of Salomaa’s book, as source of the generative grammars. However, with respect to logical correctness, the proofs proposed by Chomsky are wrong, as I have shown in two publications in French (C.R. Acad. Sci. Paris 256, 1963, 17, 357-3574 and Cahiers de Ling. Th. et Appl. 2, 1965, 146-164). This fact seems to be symptomatic for many pioneering works. Directing the attention towards something new is paid by failures in other respects. 4 Primacy of Structure against Quantity However, axiomatic-deductive approach, very necessary, was not sufficient. In order to prove that mathematics is not a conglomerate of various disparate fields, each of them on its own, but, on the contrary, these apparently heterogeneous fields have a deep common denominator, they are parts of a unique organism, there are some patterns going across the whole mathematics, working as a unification principle. It was necessary to identify some basic types of structures, the same for all mathematical fields. Three types of structures were identified: ● Order Structures, ● Algebraic Structures (the main in this respect being the Transformation Group, introduced by Evariste Galois and playing a basic role in Felix Klein’s Erlangen Programme) and ● Topological Structures. However, some mathematical fields proved to be unable to be approached in this way and this was the price Bourbaki had to pay in order to realize its structural unification. These three types of structures, both general enough and specific enough, provided the unification language developed by the Bourbaki programme. 4’ A similar need appeared in the project developed by Arto and his associates. Obviously, they took advantage from the types of structures promoted by Bourbaki project. But the structural protagonists in their approach, as in most fields under their examination, were different: ● the Semigroup (with special attention to the Free Semigroup), ● the Monoid and ● the Rewriting System including, as particular cases, the Generative Formal Grammar, the Analytic Grammar, the various types of Automaton, the Formal System of various types, the Combinatorial System, etc. 5 and 5’ Past Dominated by Disorder, Low Level of Rigor, Atomistic View Concomitant with the Emergence of Important New Trends The similarity between the disorder of the period before 1935 and the disorder of the period before 1973 was already pointed out. This topic can be further investigated, with many examples of ● lack of rigor, ● mistakes, inaccuracies, ● inconsequence in definitions and in terminology and notation ● etc. 6 Link with the Fields of Social Sciences and the Humanities Bourbaki’s project has been historically linked with the proliferation of interest for structures, coming from exact and from natural sciences (Galois’s group, chemical isomerism, the nature of heredity), but mainly from social sciences (linguistics, economics, anthropology) and from humanities (psychology – see Jean Piaget’s book Le Structuralisme Presses Universitaires de France, where the group structure is considered to have universal relevance) and from visual arts (see the collaboration between Escher and Coxeter), which are mostly interested in this notion. Many literary and social events such as the French literary group Oulipo, including the writer Italo Calvino, were developed in solidarity with Bourbaki’s project. See, for more, Amir D. Aczel - The Artist and the Mathematician – The Story of Nicolas Bourbaki, the Genius Mathematician Who Never Existed, London, High Stakes Publishing, 2007. 6’ Formal languages have as one of their fundamental source the field of linguistics. The motivation guiding Noam Chomsky in the introduction of generative grammars came from his interest in natural languages. Only later, at the beginning of the 7th decade of the past century, scholars interested in computer programming languages realized that the generative grammars proposed by Chomsky for natural languages are the right tool to investigate the syntax and the semantics of programming languages. So it happened that formal generative grammars revealed their new face: their theory became just the theory of computer programming languages. But let us quote in this respect a stronger statement, from the preface by Grzegorz Rozenberg and Arto Salomaa to the first volume of the Handbook of Formal Languages: “The theory of formal languages constitutes the stem or backbone of the field of science now generally known as theoretical computer science. In a very true sense, its role has been the same as that of philosophy with respect to science in general”. So, it is acknowledged the fact that computer programming languages are structured according to natural languages and that the whole field of computer science is build taking as a term of reference the architecture of natural languages. Obviously, these statements should not be interpreted in a trivial way; it is well-known that the relevance of context free grammars for natural languages (particularly for English) is still under debate, after a long period when this question seemed to be clarified. Many other faces of the interaction between formal languages and the social field and the humanities could be considered and we send the reader to Solomon Marcus: “Formal Languages: Foundations, Prehistory, Sources and Applications” in Formal Languages and Applications (Eds: Carlos Martin Vide, Victor Mitrana, Gheorghe Paun), Number 148 in the series “Studies in Fuzziness and Softcomputing”, Berlin, Springer, 2004, 11-53. 7 and 7’ Contrasting Attitudes towards Foundations and Mathematical Logic It is interesting to observe that the structure of a semigroup was investigated by algebraists before coming to be investigated by computer scientists, but their books are very different because their interests were completely different. Here we have an aspect of the strong contrast between Bourbaki’s project and Salomaa’s project. Bourbaki ignored fields such as foundations, probability, mathematical logic and combinatorics, just the fields of highest relevance for Salomaa’s project and for the whole project related to computability. Here we realize again the complementarity of their projects. 8 and 8’ Lack of Balance between the Discrete and the Continuous It is clear that Bourbaki favoured the continuous, according to the whole tradition of the 19th century, while Arto’s project involved mainly the discrete aspects. In this respect their complementarity is almost total. We need both of them, because we need the achievements of both hemispheres of the brain, keeping a right balance between them. Bourbaki and Salomaa are brothers. 9 and 9’ The Rise of Cognitive Metaphors We close our Bourbaki - Salomaa comparative analysis by referring to their affinity for expressive, metaphorical terms. Most mathematicians ignore that the today standard notation and terminology in mathematics was introduced by Bourbaki: ► The notation for ● The empty set ● The natural numbers N ● The integers Z ● The rationals Q ● The reals R ● The complex numbers C ● The relations of inclusion ● The strict inclusion between sets ● The operations with sets: union ; intersection ; difference \ (or –); Cartesian product All of them are using the basic metonymic or metaphorical procedures (see the similarity with signs used to express relations between numbers), ► The expressive way to denote the basic terms in modern algebra with reference to the authors of the respective notions ► Terms such as ● Injective, ● Bijective and ● Surjective All of them belong to Bourbaki. A happy cognitive-creative metaphor, emerging from authors such as Noam Chomsky – Marcel Paul Schutzenberger, Jean Berstel and I. Boisson, is to call regular languages rational languages and contextfree languages algebraic languages The link with the respective classes of real numbers proved to be very strong and it is still open to interesting unanswered questions. 10 And Now a Magic Event, involving Von Neumann, Watson-Crick, Salomaa Let us refer now to Salomaa’s Watson-Crick automata. This creative metaphor acquires a new meaning if we take in consideration what the Nobel laureate biologist Sydney Brenner wrote in his book My Life in Science, London, Biomed Central Limited, 2001. Brenner was a close collaborator of Francis Crick, who, together with James Watson, became Nobel laureates for their 1953 discovery of the double helix structure of DNA. On the other hand, John von Neumann described a similar mechanism in a paper published in 1951, in the Proceedings of the Hixton Symposium on Cerebral Mechanism in Behaviour, held in 1948, in Pasadena, California. Reading this paper, Brenner comments: “You would say that Watson and Crick depended on von Neumann, because von Neumann essentially tells you how it’s done. But of course, no one knew anything about the other”. On the other hand, Freeman Dyson noted that what today’s high school students learn about DNA is what von Neumann discovered purely by mathematics. So Salomaa’s cognitive metaphor Watson-Crick Automata acquires a deep meaning, as it is fully motivated by the historical circumstances. But, taking into account that what von Neumann described was just a kind of automaton, we realize that the right name of Watson-Crick Automata should be von Neumann- Watson-Crick Automata and it is more than a metaphor, it is a historical restoration. 11 The Calculation-Observation Interplay and How History Repeats Itself The whole story reminds another event, regarding the discovery of the planet Neptune by pure mathematical calculations, made by Urbain Le Verrier, who tried, in 1845, to explain the irregular orbit of Uranus. From these calculations, he deduced the existence of an unknown planet, which was confirmed by observation, in 1846, by the astronomer Johann G. Galle. In our case, Von Neumann is Urbain Le Verrier, Johann G. Galle is Watson-Crick while Arto Salomaa is the a posteriori Le Verrier. THANK YOU!