(*********************************************************************** Mathematica-Compatible Notebook This notebook can be used on any computer system with Mathematica 3.0, MathReader 3.0, or any compatible application. The data for the notebook starts with the line of stars above. To get the notebook into a Mathematica-compatible application, do one of the following: * Save the data starting with the line of stars above into a file with a name ending in .nb, then open the file inside the application; * Copy the data starting with the line of stars above to the clipboard, then use the Paste menu command inside the application. Data for notebooks contains only printable 7-bit ASCII and can be sent directly in email or through ftp in text mode. Newlines can be CR, LF or CRLF (Unix, Macintosh or MS-DOS style). NOTE: If you modify the data for this notebook not in a Mathematica- compatible application, you must delete the line below containing the word CacheID, otherwise Mathematica-compatible applications may try to use invalid cache data. For more information on notebooks and Mathematica-compatible applications, contact Wolfram Research: web: http://www.wolfram.com email: info@wolfram.com phone: +1-217-398-0700 (U.S.) Notebook reader applications are available free of charge from Wolfram Research. ***********************************************************************) (*CacheID: 232*) (*NotebookFileLineBreakTest NotebookFileLineBreakTest*) (*NotebookOptionsPosition[ 49392, 1216]*) (*NotebookOutlinePosition[ 52571, 1326]*) (* CellTagsIndexPosition[ 51994, 1302]*) (*WindowFrame->Normal*) Notebook[{ Cell[CellGroupData[{ Cell["\<\ The Structuring Power of Mathematica in Mathematics and \ Mathematical Education\ \>", "Subtitle"], Cell["\<\ R. Barrere, University of Franche-Comte, ENSMM 26 chemin de l'Epitaphe, F-25000 Besancon, France E-mail: rbarrere@ens2m.fr, Fax: 33(0)381 809 870\ \>", "Subsubtitle"], Cell[CellGroupData[{ Cell["Abstract", "Section"], Cell["\<\ So far, Mathematica has been used mainly either in teaching as a \ support for classical courses, or in research as a computing environment. \ However, it could be assigned a wider and more profound role in mathematics \ and mathematical education. In particular, it could support, facilitate and \ accelerate the integration of algorithmic aspects into the corpus of \ mathematics.\ \>", "Text"] }, Open ]], Cell[CellGroupData[{ Cell["1 Introduction", "Section"], Cell[TextData[{ "The necessity of integrating computing aspects in scientific", StyleBox[" ", "SmallText"], "education has already been expressed ([", CounterBox["Text", "Hayes"], "] for instance) and some authors describe innovative experiments based on \ the use of Mathematica ([", CounterBox["Text", "Johnson"], "] for instance). However, other authors stress the necessary caution in \ the renovation of courses or curriculums [", CounterBox["Text", "Gregor"], "]. The following discussion was stimulated by the observation of a general \ trend \"to bend Mathematica to old-fashioned pedagogic strategies that leave \ much of its potential unexplored\" [", CounterBox["Text", "Ramsden"], "]. To a wide extent, this remark also applies to research where the \ high-level symbolic potential of Mathematica is often underused. One of the \ reasons might be a common belief that mathematical knowledge is unchanging, \ with unending concepts. Actually, concepts evolve, even the most fundamental \ ones." }], "Text"], Cell["\<\ Nevertheless, as a result of the availability of processing power, \ a renewed way of doing and teaching mathematics is emerging, which stresses \ its algorithmic aspects besides logic. Mathematica could play a central role \ in this respect. At an elementary level, the package has already been used as \ a platform to initiate students into computer algebra, numerical methods and \ elements of programming. At a more advanced level and in research, it could \ constitute a common language to tackle such intermingled questions as \ algorithmic mathematics, theories of computation, program description and \ design, modelling and simulation methods.\ \>", "Text"], Cell["\<\ The paper is partly based on an experiment with students in \ engineering. It began with the use of Mathematica as an integrated tool for \ training them in computer algebra, numerical methods and symbolic programming \ plus a little mathematical modelling; it was based on computer labs with \ personal reports. The success of this first experiment incited the training \ personnel to bet on the federative power of Mathematica and to extend this \ approach to lectures and tutorial workshops. Now, a presentation of language \ theory, a discussion about programming paradigms, an overview of the main \ programming constructs and an initiation into program proving are part of a \ few introductory lectures beside logic. This novel experiment is in progress \ and plans already exist for broadening it to an introduction to complexity \ analysis, logical programming and mathematics for computer algebra.\ \>", "Text"], Cell[TextData[{ "Some of these topics are already taught in computer science courses ([", CounterBox["Text", "Gersting"], ", ", CounterBox["Text", "Knuth"], "] for instance); others are still scattered about the literature on \ theoretical computer science. However, the computer has become such a \ universal tool that elements of computer science must now be part of every \ scientific education. One of the purposes of the following informal \ presentation is to convince the reader that these topics deserve to be \ treated from a mathematical point of view in the same way as set theory or \ logic." }], "Text"] }, Open ]], Cell[CellGroupData[{ Cell["2 Computing vs reasoning", "Section"], Cell["\<\ The sequence defined by v[0]=1; v[n_]:=n-v[v[n-1]] gives a simple \ illustration of the difference between the classical mathematical reasoning, \ which yields v[1]=1/2 by solving the equation v[1]==1-v[1], and the \ computational approach which leads to an infinite recursion. Quite \ surprisingly, colleagues like students, whom the answer \"infinite \ recursion\" leaves skeptic, answer v[1]=1/2. This common reaction shows \ that, as a result of their classical education, many scientists are still \ unaware of algorithmic questions. \ \>", "Text"], Cell["\<\ Despite this surface discrepancy, further thought shows that the \ two approaches are not incompatible for the question can be restated from the \ enlarged point of view: which rule must be applied and when (i.e., in which \ order rules must be applied)? Several examples can be given about the role of \ rule precedence during evaluation, both in Mathematica and in classical \ mathematics. For instance, with Mathematica, upvalues are tried before \ downvalues, which allows overriding other rules; similarly, the attributes of \ the family \"hold\" enable non-standard evaluation, in particular the \ localization of variables; in mathematics, a variational formulation consists \ of an integration by parts before any other evaluation.\ \>", "Text"], Cell["\<\ The example also brings out the difference between the \ transformational interpretation of the sign = (= or := in Mathematica) and \ the equational one which is relational. The transformational formulation is \ single-valued (\"deterministic\"), whereas the relational one is multivalued; \ it is inopportunely said \"non-deterministic\" although it doesn't violate \ classical determinism. Basically, a computation is a transformational process \ while a reasoning uses relational formulations.\ \>", "Text"], Cell["\<\ The example further stresses the distinction between rules that are \ applied automatically (the recursive definition) and those that the user must \ explicitly apply (Solve[v[1]==1-v[1]]). Finally, it emphasizes the importance \ of program proving, in particular termination proofs and the role of \ structural induction.\ \>", "Text"], Cell["\<\ So this discussion points out the rule-based paradigm as a basic \ tool to tackle mathematical questions from the computational point of view \ and symmetrically computational questions from the mathematical point of \ view. In order to go deeper into the matter, two entangled questions must be \ answered first: how mathematical expressions (and computer programs) are \ written, and how they are processed. As a matter of fact, expressions are \ generated by context-free grammars and computations are implemented by (or \ amount to) a rewrite (context-sensitive) mechanism.\ \>", "Text"] }, Open ]], Cell[CellGroupData[{ Cell["3 Language theory and syntactic questions", "Section"], Cell[CellGroupData[{ Cell["3.1 Elements of language theory", "Subsection"], Cell["\<\ It might be a truism that mathematical statements must be written \ so that mathematics relies upon language theory, even prior to logic. \ However, this seems not to have been recognized until recently (actually, \ linguistic questions have often been improperly identified with logical \ ones), so that investigations about languages began under the patronage of \ linguistics and computer science rather than mathematics. Moreover, many \ authors now stress the algebraic structure (semi-group or monoid) of \ languages although their primary interest is to understand the underlying \ branching structure of mathematical formulas and computer programs.\ \>", "Text"], Cell[TextData[{ "Although they initially emerged on the occasion of Chomsky's \ investigations [", CounterBox["Text", "Chomsky"], "] about natural languages, mathematical ideas about languages were mainly \ developed in the context of programming. The central question is to \ characterize (generate or recognize) well-formed expressions among all \ possible sequences of symbols. This role is devoted to grammars (i.e., sets \ of production rules) and recognizers or parsers. In the Chomsky hierarchy, \ two major classes are of interest for language design: regular languages \ describe the sequential structure of codes, words, numbers or strings (atomic \ expressions in Mathematica); context-free languages describe the branching \ structure of mathematical expressions or programs (non-atomic expressions in \ Mathematica). Basically, mathematics as well as computer science rely upon \ context-free languages." }], "Text"], Cell[TextData[{ "In a programming context, it would be necessary to introduce automata \ theory in view of the design of recognizers or parsers. In a more general \ scientific context, in order to avoid the cumbersome manipulation of \ automata, one can analyse strings by \"exploding\" them into lists and by \ using recursive operators [", CounterBox["Text", "Leermakers"], "]. Here is for instance, a predicate that tests whether a string over the \ alphabet \[CapitalSigma]={(,)} is a well-formed bracketing (Dick's language). \ " }], "Text"], Cell[BoxData[ \(explode[s_String] := Map[FromCharacterCode, ToCharacterCode[s]]\)], "Input"], Cell[BoxData[ \(DickQ[s_String] := DickQ[explode[s]]\)], "Input"], Cell[BoxData[{ \(DickQ[{}] := True\ (*\ empty\ word\ *) \), \(DickQ[{"\<(\>", w___ /; DickQ[{w}], "\<)\>"}] := True\), \(DickQ[{u__ /; DickQ[{u}], v__ /; DickQ[{v}]}] := True\), \(DickQ[___] := False\)}], "Input"], Cell[CellGroupData[{ Cell[BoxData[ \(Map[DickQ, {"\<(()())()\>", "\<(()\>", "\<\>", "\<[]\>"}]\)], "Input"], Cell[BoxData[ \({True, False, True, False}\)], "Output"] }, Open ]], Cell[TextData[ "The recursive predicate is a direct implementation of the set of production \ rules {S\[Rule]\[CurlyEpsilon], S\[Rule](S), S\[Rule]SS} (where S is the \ start symbol and \[CurlyEpsilon] the empty word) or of the equivalent logical \ description: \[CurlyEpsilon]\[Element]L, \ w\[Element]L\[Implies](w)\[Element]L, \ u\[Element]L\[And]v\[Element]L\[Implies]uv\[Element]L (where L denotes Dick's \ language)."], "Text"] }, Open ]], Cell[CellGroupData[{ Cell["3.2 Functional syntax and abstract syntax", "Subsection"], Cell["\<\ Behind these notions, there is a central question: languages are a \ means of representing intrinsically branching structures by sequential ones. \ A small number of fundamental methods to represent trees by sequences have \ been put forward: the prefix, infix and suffix notations plus occasionally \ the matchfix one. Since these notations are different ways to represent a \ tree, which is the underlying significant structure, they are equivalent and \ it can be more attractive to reason directly with trees and their associated \ terminology; this is the role of abstract syntax.\ \>", "Text"], Cell[TextData[{ "So far, these different writings (concrete syntaxes) have mainly be used \ for convenience. In fact, for better efficiency in communication, it would be \ better to use a single notation. The designers of Mathematica used the", StyleBox[" ", "SmallText"], "ergonomic solution of a functional syntax, which is a combination of \ prefix and matchfix notations. This internal form (FullForm) of expressions \ has been supplemented with a variety of input and output formats to ensure \ compatibility with classical mathematical notations. Since version 3, these \ formats include the mathematical two-dimentional graphical notations. Below, \ a few functional translations from logical, algebraic, Lisp, HTML or \ PostScript statements bring out the unifying and often clarifying power of \ the functional syntax." }], "Text"], Cell[BoxData[GridBox[{ {\(Domain\ specific\), "Functional"}, {\(\((P \[Or] Q)\) \[And] R\), \(And[Or[P, Q], R]\)}, {\(x + 3 y + sin\ \ \[Pi]\), \(Plus[x, Times[3, y], Sin[Pi]]\)}, {\((\(+ (*\(\ x \((log\ x)\))\)\ x)\)\), \(Plus[Times[x, Log[x]], x]\)}, {\( < \(\\head\) > The\ title < \(\\Head\) > \), \(Head["\"]\ or\ Cell["\", "\"]\)}, {\(0\ 0\ moveto\ 1\ 1\ lineto\), \(Line[{{0, 0}, {1, 1}}]\)} }, ColumnAlignments->{Right, Left}]], "Input", CellMargins->{{3, Inherited}, {Inherited, Inherited}}, FontWeight->"Plain"], Cell[TextData[{ "Thus, the functional syntax can be viewed as a conventional abstract \ syntax. Indeed, there is a close relation (a morphism) between trees and \ functional constructs. This was a great idea to choose a functional notation \ at the heart of Mathematica, for it is usual and has a strong mathematical \ flavor. The figure below shows the functional and \"applicative\" \ representations of the expression ", Cell[BoxData[ \(TraditionalForm\`e\_0\)]], "[", Cell[BoxData[ \(TraditionalForm\`e\_1\)]], ",", Cell[BoxData[ \(TraditionalForm\`e\_2\)]], "\[Ellipsis]", Cell[BoxData[ \(TraditionalForm\`e\_n\)]], "]." }], "Text"], Cell[GraphicsData["PICT", "\<\ 1gkooooo03`1600A0_l<0?ooooooo`00ool0004H0000?0000000002Q0<03NBE@ Kg=dDf=bJG1d84QQHf/PHWTPCFU[IB12LVmbLb0aN00X02e0:40eP040020002P0=L0X03I00L0000000P0200S 0000X@2f00@00@010:40eP040020002Q0=P01000P000X02n0:00f@0700400@0R 02/01`?o0280:00<0ol08P0U0143o`0R02805`;o02807`0L0ol08P0L0243o`0R 01T09P?o02805P0/0_l08P0D0342oP0R0140=P?n02803P0k0oh08P0;0400002Q 0=P01000P000X02o0:00f@2P0=L01`0000008`000:40]P0400400@0700400@0R 02/0:AOP00L0000002<0002Q0;H0100100401`0100408c"], "Graphics", ImageSize->{281, 61}, ImageMargins->{{87, 0}, {0, 0}}, ImageRegion->{{0, 1}, {0, 1}}], Cell["\<\ If need be, the formatting of expressions can constitute \ application exercices. Here is an example with the format prefixListForm that \ gives the prefix Lisp-like form of an expression.\ \>", "Text"], Cell["\<\ prefixListForm[e_?AtomQ]:= e prefixListForm[h_[p___]]:= Map[prefixListForm, {h, p}]\ \>", "Input"], Cell[CellGroupData[{ Cell["prefixListForm[f[a,g[1,1.5],h[]]]", "Input"], Cell[BoxData[ RowBox[{"{", RowBox[{"f", ",", "a", ",", RowBox[{"{", RowBox[{"g", ",", "1", ",", StyleBox["1.5`", StyleBoxAutoDelete->True, PrintPrecision->2]}], "}"}], ",", \({h}\)}], "}"}]], "Output"] }, Open ]] }, Open ]], Cell[CellGroupData[{ Cell["3.3 Functional syntax and structural induction", "Subsection"], Cell["\<\ The algorithmic approach involves sets defined by structural \ induction. Structural induction is an extension of classical induction to \ partial orderings. In practice, it allows generalizing proofs from sequential \ structures to branching ones. Indeed, in the context of a functional syntax, \ objects (expressions in Mathematica) are viewed as the result of applying \ functions to other objects so the resulting functional expressions are trees. \ As a consequence, program proving involves structural induction. Here is an \ example with a recursive definition for the depth of an expression.\ \>", "Text"], Cell[BoxData[{ \(depth[e_?AtomQ] := 1\), \(depth[_[]] := 2\), \(depth[e_] := 1 + Apply[Max, Map[depth, e]]\)}], "Input"], Cell["\<\ One can verify that the relation \"is a subexpression of\" \ determines a well-founded partial ordering. Then, the property that the \ function terminates and yields the correct result is proved by structural \ induction in two steps. Firstly, the property is clearly true for atoms, \ which are the minimal elements for the well-founded ordering and the base \ cases for the recursion. Then, assuming the property is true for the \ expressions of depth (strictly) lower than n, one concludes it is also true \ for expressions of depth n since Map[depth, e] only brings into play \ expressions of depth lower than n. In more abstract terms this amounts to \ proving that the computation generates a decreasing sequence in a \ well-founded set.\ \>", "Text"], Cell[TextData[{ "Behind the principle of structural induction, there is the idea that \ membership of a set can be described in term of the form of the object. In \ Mathematica, theses forms are characterized by patterns, that can be viewed \ as expression templates or classes, including logical tests (see section 5 \ below). Classical mathematics lays stress", StyleBox[" ", "SmallText"], "upon the structure of sets, i.e. the collection of relations between \ unstructured objects; on the contrary, the algorithmic point of view stresses \ the internal structure of objects." }], "Text"] }, Open ]] }, Open ]], Cell[CellGroupData[{ Cell["4 Programming paradigms and theories of computation", "Section"], Cell[TextData[{ "An algorithm describes the decomposition of a computation into elementary \ operations. There are several ways of expressing algorithms according to \ these elementary operations, i.e., the primitives of the language. According \ to whether the language is machine oriented or problem oriented, this leads \ to several sorts of languages supporting different programming paradigms.\ \[NonBreakingSpace][", CounterBox["Text", "MaederDoobs"], ",\[NonBreakingSpace]", CounterBox["Text", "Wolfram"], "]" }], "Text"], Cell[TextData[ "Three major programming paradigms turn out to have three main theories of \ computation as mathematical counterparts: Post-Turing machines for procedural \ programming, Kleene's recursive functions and the Church \[Lambda]-calculus \ for the functional paradigm and the Post-Markov theory of algorithms for the \ transformational paradigm. So we have the equation: programming paradigm \ \[TildeTilde] model of computation. Let's examine them more precisely."], "Text"], Cell["\<\ So far, the procedural paradigm has been the most widespread one. \ Strongly influenced by the most usual computer architecture, it identifies \ the processing device with an automaton evolving through successive states. \ Post-Turing machines constitute a low-level model of the procedural paradigm \ and Fortran (Backus), Pascal (Wirth) or C (Kernighan) are well-known \ implementations of it.\ \>", "Text"], Cell[BoxData[ \(proceduralMagnitude[v_] := \n\t Module[{x, y}, \n\t\t\tx = v[\([1]\)]; \ y = v[\([2]\)]; \n\t\t\t z = Sqrt[x^2 + y^2]; \n\t\t\tPrint[z]\ \ ]\)], "Input"], Cell[TextData[ "However, other programming models were imagined, such as the functional \ paradigm based on the idea of mathematical evaluation: since a function gives \ a result (output) for any admissible value of the variable (input), it \ constitutes a model of computation. Lisp (Mc Carthy) was the first example of \ such a language, which is said functional (or applicative). It consists of \ mechanisms to define and compose functions and apply them to values. The \ theory of recursive functions and the \[Lambda]-calculus constitute \ mathematical counterparts of this programming paradigm."], "Text"], Cell[BoxData[ \(functionalMagnitude[v_] := \n\t\tSqrt[First[v]^2 + Last[v]^2]\)], "Input"], Cell["\<\ Another non-conformist approach is based on the fact that data are \ written, so an algorithm consists in analysing and transforming sequences of \ symbols according to specified rules. Such a syntax-oriented language is \ called transformational (or rule-based) and Snobol (Griswold) is an actual \ implementation. It consists of a comparison process called pattern-matching \ associated with a rewrite mechanism. Post's formal systems or Markov's theory \ of algorithms constitute mathematical counterparts of this programming \ paradigm.\ \>", "Text"], Cell[BoxData[ \(transformationalMagnitude[{x_, y_}] := \n\t\tSqrt[x^2 + y^2]\)], "Input"], Cell[TextData[{ "These questions about programming styles are far from useless. The issue \ was clearly stated by Budd [", CounterBox["Text", "Budd"], "]: \"the language in which a programmer thinks a problem will be solved \ will color and alter, in a basic fundamental way, the fashion in which that \ programmer will develop an algorithm.\" Hence the interest in a rich enough \ linguistic frame so that different programming styles (or models of \ computation) may coexist or even cooperate: \"I knew at that time that the \ real revolution would arrive when we finally understood how to bring these \ diverse points of view together in one framework\" [", CounterBox["Text", "Budd"], "]. The idea of multiparadigm programming emerged in the early eighties; \ Leda was Budd's first attempt to implement a multiparadigm language, after \ which Mathematica was the first widespread multiparadigm language, built on \ top of a rule-based core with a functional syntax. Then, computing consists \ in rewriting functional expressions, i.e., rewriting trees." }], "Text"], Cell["\<\ Plenty of exercises can be made to illustrate paradigm conversions. \ One generally admits that the functional and transformational styles are the \ most elegant ones, except in the case of compilation for numerical \ algorithms. So these exercises will generally read: \"transform this \ procedural program into a functional one\", or: \"convert this functional \ definition into a transformational one\". For instance, the procedural \ program:\ \>", "Text"], Cell[BoxData[ \(aSum[myList_] := Module[\n\t\t{theSum = 0}, \n\t\t Do[theSum = theSum + myList[\([i]\)]^2, \n \t\t\t{i, 1, Length[myList]}]; \n\t\ttheSum\n\t\t]\)], "Input"], Cell["\<\ which squares the elements of a list and adds them would give, \ thanks to the listability of Plus:\ \>", "Text"], Cell[BoxData[ \(aNicerSum[myList_] := Apply[Plus, myList^2]\)], "Input"], Cell["Similarly, the functional definition:", "Text"], Cell[BoxData[ \(thisToCartesian[v_] := First[v] {\ Cos[Last[v]], Sin[Last[v]]}\)], "Input"], Cell["\<\ which converts a polar representation to a cartesian one, would \ give:\ \>", "Text"], Cell[BoxData[ \(thatToCartesian[{r_, \[Theta]_}] := r {\ Cos[\[Theta]], Sin[\[Theta]]}\)], "Input"], Cell[TextData[{ "Finally, the relational (e.g., Prolog) and object-oriented (e.g. \ SmallTalk) paradigms could be mentioned. They are not directly implemented in \ Mathematica, but Meader [", CounterBox["Text", "MaederII"], "] described a simplified implementation of the relational paradigm in \ Mathematica and several object-oriented features of the language deserve a \ mention: expressions are objects (without internal state), patterns determine \ classes, upvalues work like methods." }], "Text"], Cell["\<\ In most scientific applications, computer science has suffered the \ lack of a common and efficient language to describe algorithms, write \ programs and reason about them. A great deal of energy has been expended \ translating problems into programs, programs into mathematical descriptions, \ defining various pseudo programming languages to describe algorithms, or \ converting programs from one language to another, while this energy would \ have been used more efficiently to discuss models, algorithms and data \ representations. Mathematica clearly avoids these drawbacks by providing with \ a single consistant framework. \ \>", "Text"] }, Open ]], Cell[CellGroupData[{ Cell["5 Math-oriented constructs vs machine-oriented constructs", "Section"], Cell[CellGroupData[{ Cell["5.1 Basic programming constructs", "Subsection"], Cell["\<\ Although the classical mathematical approach rests on set theory \ and logic, the computational one is rather based on algorithms. Two major \ programming constructs are iteration and conditionals. Elementary primitives \ are assumed to be available, such as function definition, composition and \ application. There are two kinds of iteration: the parametrized iteration \ corresponds to primitive recursive definitions and according to the \ programming paradigm can be implemented by means of Do, Fold or a recursive \ definition that terminates; the conditional iteration corresponds to general \ recursive definitions and can be implemented by means of While, FixedPoint, \ an iterative definition or possibly a stream. \ \>", "Text"], Cell["\<\ In the following example, we seek the first positive integer that \ equals the sum of its strict divisors; the three programs implement a \ conditional iteration and yield 6. At present, the implementation formerly \ said \"terminal recursive\" is rather said \"iterative\". Actually, we should \ differentiate between \"self-referent\" and \"recursive\".\ \>", "Text"], Cell[BoxData[ \(perfectQ[n_Integer] := TrueQ[n == Apply[Plus, Drop[Divisors[n], \(-1\)]]]\)], "Input"], Cell[BoxData[ \(\( (*\ procedural\ implementation\ *) \nn = 1; While[Not[perfectQ[n]], \(n++\)]; n\)\)], "Input"], Cell[BoxData[ \(\( (*\ functional\ implementation\ *) \n FixedPoint[\((#1 + 1)\)&, 1, SameTest -> \((perfectQ[#2]&)\)]\)\)], "Input"], Cell[BoxData[{ \( (*\ transformational\ implementation\ *) \n perfect[n_?perfectQ] := n\), \(perfect[n_] := perfect[n + 1]\), \(perfect[1]\)}], "Input"], Cell["\<\ These constructs apply to lists or more generally sequential data \ structures, i.e., totally ordered sets from the mathematical point of view. \ They can be extended to branching data structures, i.e., partially ordered \ sets. In that case, MapAll gives the iterative counterpart of a recursive \ definition.\ \>", "Text"], Cell[BoxData[{ \(recursiveLeafCount[e_?AtomQ] := 1\), \(recursiveLeafCount[e_] := recursiveLeafCount[Head[e]] + \n\t\t Apply[Plus, Map[recursiveLeafCount, e]]\)}], "Input"], Cell[BoxData[{ \(visitor[e_?AtomQ] := 1\), \(visitor[e_] := Head[e] + Apply[Plus, e]\), \(iterativeLeafCount[e_] := MapAll[visitor, e, Heads -> True]\)}], "Input"], Cell["\<\ Programs that implement recursive definitions may not terminate so \ a termination proof is required. It turns out to be simpler in the case of \ functional programs, since the proof (by weak, strong or structural \ induction) is modelled on the recursive definition (see section 3.3). In the \ near future, program proving, in particular termination proofs will tend to \ become part of many algorithm-oriented exercises, in the same way as series \ convergence in calculus exercises.\ \>", "Text"], Cell["\<\ Finally, conditionals are implemented with If, Which, Switch or by \ means of conditional definitions. A conditional is equivalent to a search in \ an ordered set of transformation rules. In another words, the mathematical \ counterpart of a conditional is a piecewise function.\ \>", "Text"], Cell[BoxData[ \(proceduralFactorial[n_] := If[n == 0, 1, n\ proceduralFactorial[n - 1]]\)], "Input"], Cell[BoxData[{ \(functionalFactorial[0] := 1\), \(functionalFactorial[n_] := n\ functionalFactorial[n - 1]\)}], "Input"], Cell["\<\ In all cases, the comparison of the different styles brings to \ light equivalences between programming constructs and mathematical \ formulations. Functional or transformational constructs are naturally \ math-oriented whereas procedural ones are machine-oriented. We should \ recommend students to prefer the former, except in particular circumstances \ such as compilation.\ \>", "Text"] }, Open ]], Cell[CellGroupData[{ Cell["5.2 Advanced programming constructs", "Subsection"], Cell[TextData[ "The aforementioned constructs are only basic ones, from which any algorithm \ can be implemented, at least in principle. However, the functional and \ transformational paradigms introduce specific operators for particular tasks, \ for instance Nest, Map, Dot\[NonBreakingSpace]\[Ellipsis] These high level \ versatile constructs lead to programs that mimic mathematical formulas."], "Text"], Cell["\<\ These operators are generic insofar as they apply to categories of \ problems rather than particular problems. Then, the art of programming \ consists in choosing, combining or instanciating appropriate operators. This \ leads to mathematical constructs that facilitate the reasoning about \ programs. For instance, one can recognize a generalized tensor product behind \ r-permutations.\ \>", "Text"], Cell[BoxData[ \(rPermutations[myList_List, n_Integer] := Flatten[Outer[List, Apply[Sequence, Table[myList, {n}]]], n - 1]\)], "Input"], Cell[CellGroupData[{ Cell[BoxData[ \(rPermutations[{a, b, c}, 2]\)], "Input"], Cell[BoxData[ \({{a, a}, {a, b}, {a, c}, {b, a}, {b, b}, {b, c}, {c, a}, {c, b}, {c, c}} \)], "Output"] }, Open ]], Cell[TextData[ "Once again, it is easy to elaborate lots of little exercises to compute \ tables, scalar products, differential operators\[Ellipsis] Classical \ programming exercises ask for procedural solutions; it would be more \ enriching to incite students to solve exercises using several programming \ paradigms. For those who have already learned a procedural language, there \ are nice exercises about the conversion of procedural programs to functional \ or transformational ones (see section 3). In the literature on computer \ science, one also finds exercises about the transformation of recursive \ difinitions into iterative ones; here is an exemple."], "Text"], Cell[BoxData[{ \(recursiveQuicksort[{}] := {}\), \(recursiveQuicksort[{e_}] := {e}\), \(recursiveQuicksort[{p_, r___}] := \n\t\t Flatten[{\n\t\t\t\trecursiveQuicksort[Select[{r}, OrderedQ[{#, p}]&]], \n\t\t\t\t{p}, \n\t\t\t\t recursiveQuicksort[Select[{r}, Not[OrderedQ[{#, p}]]&]]\n\t\t}, 1] \)}], "Input"], Cell[BoxData[{ \(iterator[{}] := {}\), \(iterator[{e_}] := {e}\), \(iterator[{p_, r___}] := \n\t\t Sequence[Select[{r}, OrderedQ[{#, p}]&], \n\t\t\t\t{p}, Select[{r}, Not[OrderedQ[{#, p}]]&]\t]\), \(iterativeQuicksort[aList_] := \n\t\t Flatten[FixedPoint[Map[iterator, #]&, {aList}], 1]\)}], "Input"] }, Open ]] }, Open ]], Cell[CellGroupData[{ Cell["6 Towards algorithmic mathematics", "Section"], Cell["\<\ Computer science brings out the algorithmic approach to function \ definition, in contrast to the classical set-thoretic approach. Firstly, a \ function is defined constructively as a combination of primitives or \ previously defined functions. So a function is viewed as a computing tool \ rather than a relation between elements of sets. Then, thanks to patterns, \ function domains (algorithm preconditions) can be incorporated into the \ definitions.\ \>", "Text"], Cell["\<\ Moreover, this algorithmic approach brings to light there are \ generally several ways of doing things, i.e., several possible right-hand \ members in a definition. This leads to differentiate between the \ specification of a function and its implementation. The former more or less \ corresponds to the classical set-theoretic definition; actually, at first \ stage, it is often given informally in natural language. The latter \ corresponds to the constructive definition. That's a matter of programming \ art to find an implementation that satisfies compactness or efficiency \ constraints; hence the role of complexity analysis.\ \>", "Text"], Cell[CellGroupData[{ Cell["6.1 Patterns and the modelling of data", "Subsection"], Cell["\<\ A pattern characterizes the class of expressions that match it, so \ patterns are a means of dividing up expressions into classes; that's the way \ a pattern denotes an invariant of a class. These classes are de facto \ organized in subclasses, which establishes a relation with set theory and \ with object-oriented programming. However, they need not be declared; they \ are rather used to specify the domain of functions. In practice, patterns \ constitute a convenient notation for describing subsets of expressions. Using \ patterns turns out to be convenient to refer to classes, by writing for \ instance _Real?Positive for the class of positive decimal numbers; then, _ \ denotes the more general class, i.e., the set of all well-formed expressions.\ \ \>", "Text"], Cell["\<\ Actually, one can focuss on the head of an expression, which \ amounts to a classical type, i.e., a nominal type (e.g., Rational, List, \ Graphics). Thanks to patterns, one can also consider the structure of an \ expression, in which case one can think of a structural type. Finally, one \ can associate a predicate or a test P with a pattern (_/;P or _?P) which then \ denotes a logical type. In particular, any user-defined predicate can be \ reused in a pattern, which allows defining recursive classes or enumerated \ classes.\ \>", "Text"], Cell[BoxData[{ \(binaryTreeQ[e_?AtomQ] := True\), \(binaryTreeQ[h_?AtomQ[l_?binaryTreeQ, r_?binaryTreeQ]] := True\), \(binaryTreeQ[___] := False\)}], "Input"], Cell[BoxData[ \(dayQ[x_] := MemberQ[{Sunday, Monday\ (*\ \[Ellipsis]\ *) , \ Saturday}]\)], "Input"], Cell[TextData[ "Moreover, patterns can be nested so that any combination of these type \ constructs also charaterizes a class. In particular, one can construct \ intersections and unions of classes; for instance, _head?test\[MediumSpace]|\ \[MediumSpace]pat corresponds to the set of expressions ( _head \ \[Intersection] _?test) \[Union] pat. As a consequence, patterns turn out to \ be a finer and more versatile way of differentiating data than the classical \ nominal types."], "Text"] }, Open ]], Cell[CellGroupData[{ Cell["6.2 Patterns and the modelling of algorithms", "Subsection"], Cell["\<\ One of the main uses of classes is the specification of function \ domains (algorithm preconditions). Patterns constitute an elegant way to \ integrate the domain into the function definition. Then, the precondition is \ automatically tested at the time of function application. Besides, any \ functional program amounts to function composition, hence a mathematical \ expression. So proving a program amounts to demonstrating a mathematical \ property and a correct program is no more no less than a sound formula. In \ other words, a bug has the same statute as a mathematical mistake.\ \>", "Text"], Cell[TextData[{ "In practice, proving a function amounts to examine the right hand side of \ its definition and imagine its evaluation mentally. In particular, ", Cell[BoxData[ \(TraditionalForm\`e\_0\)]], "[", Cell[BoxData[ \(TraditionalForm\`e\_1\)]], ",", Cell[BoxData[ \(TraditionalForm\`e\_2\)]], "\[Ellipsis]", Cell[BoxData[ \(TraditionalForm\`e\_n\)]], "] terminates provided that each ", Cell[BoxData[ \(TraditionalForm\`e\_i\)]], " terminates. Functional or transformational programs lead to direct proofs \ in general and inductive proofs in the case of recursive definitions. On the \ contrary, procedural programs with lots of assignments and local variables \ are unclear and lead to intricate proofs. They require not only to follow the \ program but also the numerous internal states associated with it." }], "Text"], Cell["\<\ A peculiarity of algorithms is genericity, which means algorithms \ apply to classes of data rather than particular data. Patterns are precisely \ the way to specify classes, consequently to express genericity, hence a \ mathematical abstraction. In practice, an ordinary definition renders a \ logical equivalence, whereas a conditional one conveys an implication.\ \>", "Text"], Cell[BoxData[ \(\(evenQ[n_] := evenQ[n - 2]\ \ (* \[MediumSpace]evenQ[n - 2]\[MediumSpace] \[DoubleLeftRightArrow] \[MediumSpace]evenQ[n]\[MediumSpace]*) \)\)], "Input"], Cell[BoxData[ \(\(evenQ[n_] := True /; evenQ[n - 2]\ \ (* \[MediumSpace]evenQ[n - 2]\[MediumSpace] \[Implies] \[MediumSpace]evenQ[n]\[MediumSpace]*) \)\)], "Input"] }, Open ]], Cell[CellGroupData[{ Cell["6.3 Operational types", "Subsection"], Cell[TextData[{ "Attaching transformation rules to classes gives abstract data types [", CounterBox["Text", "MaederI"], "], which more or less correspond to objects in object-oriented \ programming. Actually, these types were abstract in the procedural context, \ because they were used to develop mathematical models of data structures and \ programs. In a functional context, they are rather \"operational\" and \ typically implemented by means of upvalues in Mathematica. Then, the old \ procedural equation \"algorithms + data structures = programs\" tends to \ become:" }], "Text"], Cell[TextData[ " transformation rules + classes \[TildeEqual] abstract (operational) types \ \[TildeEqual] objects. "], "Text", TextAlignment->Center, TextJustification->0], Cell[TextData[{ "Finally, one must notice that abstract types are equational, while rules \ are transformational. So implementing an abstract type amounts to choosing an \ orientation for equations. The issue was tackled by Maeder in [", CounterBox["Text", "MaederIMS'95"], "]. This remark sets the borderline between mathematics and computer \ science. Moreover, in mathematics, we are not concerned about the attachment \ of rules to objects, while this question is central in a programming context. \ Once again, we can note that computer science enriches mathematics." }], "Text"] }, Open ]] }, Open ]], Cell[CellGroupData[{ Cell["7 Discussion", "Section"], Cell["\<\ The presentation successively focussed on syntactic questions, \ programming paradigms, program constructs and program proving methods. It \ incited to think in terms of trees or functional expressions (abstract \ syntax) rather than words or formulas (concrete syntaxes), transformation \ rules and functions rather than programs, evaluation rather than execution, \ patterns and classes rather than types. \ \>", "Text"], Cell[TextData[{ "Nevertheless, it could also include more advanced topics such as \ algorithmic information theory\[NonBreakingSpace][", CounterBox["Text", "Chaitin"], "], complexity analysis [", CounterBox["Text", "Leeuven"], "] or mathematics for computer algebra\[NonBreakingSpace][", CounterBox["Text", "Labahn"], "]. Besides, according to the context (teaching or research), these ideas \ could be more or less detailed, developed or complemented. For instance, the \ following topics could be developed: \[Lambda]-calculus, confluence \ properties, formal systems, the relational paradigm, the variety of \ variables, the problem of assignment and knowledge evolution\[Ellipsis]" }], "Text"], Cell["\<\ There is basically nothing novel, except slight modifications in \ the way of presenting notions, a different organization of concepts and \ hopefully a better integration of mathematical and algorithmic aspects. Set \ theoretic (relational) and algorithmic (transformational) aspects of \ mathematics turn out to be complementary, so they should now be examined \ together. \ \>", "Text"], Cell["\<\ We could notice the federative power of Mathematica both in \ computer science and mathematics. It contributes to broadening the zone of \ influence of mathematics and to bringing novel questions there, such as the \ dynamical aspects of programming (evaluation process, knowledge growth).\ \>", "Text"], Cell["\<\ Scientific revolutions seem abrupt at the scale of history, but \ they are progressive at the scale of human life, because they consist of \ slight successive changes. The unifying functional syntax and the unitary \ evaluation mechanism of Mathematica might constitute a revolution at the \ common borderline of mathematics and computer science; but this is not clear \ yet because we lack the experience of history.\ \>", "Text"] }, Open ]], Cell[CellGroupData[{ Cell["8 Conclusion", "Section"], Cell["\<\ So far, the algorithmic aspects of mathematics have been more or \ less regarded as marginal in science and scientific education. However, as a \ result of the common use of computers, they have become central and should be \ given a better place. Thanks to its functional syntax that mimics \ mathematical notations, Mathematica turns out to be a good candidate to \ express and investigate the mathematical aspects of computer science and the \ algorithmic aspects of mathematics; it brings together the mathematical and \ computational approaches. With Mathematica, computer science has taken a step \ towards mathematics; isn't it time mathematics made a move in the direction \ of computer science?\ \>", "Text"] }, Open ]], Cell[CellGroupData[{ Cell["References", "Section"], Cell[TextData[{ "[", CounterBox["Text"], "] T. Budd: Multiparadigm Programming in Leda, Addison-Wesley, 1995" }], "Text", CellMargins->{{Inherited, Inherited}, {2, 2}}, CounterAssignments->{{"Text", 0}}, CellTags->"Budd"], Cell[TextData[{ "[", CounterBox["Text"], "] N. Chomsky: On certain formalproperties of grammars, Information and \ Control, 2(2), 1959, 137-167" }], "Text", CellMargins->{{Inherited, Inherited}, {2, 2}}, CellTags->"Chomsky"], Cell[TextData[{ "[", CounterBox["Text"], "] G. Chaitin: Algorithmic Information Theory, Cambridge University Press, \ 1987" }], "Text", CellMargins->{{Inherited, Inherited}, {2, 2}}, CellTags->"Chaitin"], Cell[TextData[{ "[", CounterBox["Text"], "] J. Gersting: Mathematical Structures for Computer Science, Computer \ Science Press, 1993" }], "Text", CellMargins->{{Inherited, Inherited}, {2, 2}}, CellTags->"Gersting"], Cell[TextData[{ "[", CounterBox["Text"], "] J. Gregor: Computers and active learning of mathematics, in Proceedings \ of the 9th European Seminar on Mathematics in Engineering Education, Arcada \ Polytechnic, 1998, 52-57" }], "Text", CellMargins->{{Inherited, Inherited}, {2, 2}}, CellTags->"Gregor"], Cell[TextData[{ "[", CounterBox["Text"], "] A. Hayes: Mathematica and people - making the future, in [", CounterBox["Text", "1995"], "], 1-6" }], "Text", CellMargins->{{Inherited, Inherited}, {2, 2}}, CellTags->"Hayes"], Cell[TextData[{ "[", CounterBox["Text"], "] D.R. Johnson, J.A. Buege: Rethinking the way we teach undergraduate \ physics and engineering with Mathematica, in [", CounterBox["Text", "1995"], "], 233-241" }], "Text", CellMargins->{{Inherited, Inherited}, {2, 2}}, CellTags->"Johnson"], Cell[TextData[{ "[", CounterBox["Text"], "] V. Ker\[ADoubleDot]nen, P. Mitic (Ed): Mathematics with Vision, \ Proceedings of the First International Mathematica Symposium, Computational \ Mechanics Publications, 1995" }], "Text", CellMargins->{{Inherited, Inherited}, {2, 2}}, CellTags->"1995"], Cell[TextData[{ "[", CounterBox["Text"], "] V. Ker\[ADoubleDot]nen, P. Mitic, A. Hietam\[ADoubleDot]ki (Ed): \ Innovation in Mathematics, Proceedings of the Second International \ Mathematica Symposium, Computational Mechanics Publications, 1997" }], "Text", CellMargins->{{Inherited, Inherited}, {2, 2}}, CellTags->"1997"], Cell[TextData[{ "[", CounterBox["Text"], "] R. Graham, D. Knuth, O. Patashnik, Concrete Mathematics, Addison-Wesley, \ 1989" }], "Text", CellMargins->{{Inherited, Inherited}, {2, 2}}, CellTags->"Knuth"], Cell[TextData[{ "[", CounterBox["Text"], "] S. Czapor, K. Geddes, G. Labahn: Algorithms for Computer Algebra, Kluwer \ Academic Publishers, 1992" }], "Text", CellMargins->{{Inherited, Inherited}, {2, 2}}, CellTags->"Labahn"], Cell[TextData[{ "[", CounterBox["Text"], "] R. Leermakers: The Functional Treatment of Parsing, Kluwer Academic \ Publishers, 1993" }], "Text", CellMargins->{{Inherited, Inherited}, {2, 2}}, CellTags->"Leermakers"], Cell[TextData[{ "[", CounterBox["Text"], "] R. Maeder : The Mathematica Programmer, Academic Press, 1994" }], "Text", CellMargins->{{Inherited, Inherited}, {2, 2}}, CellTags->"MaederI"], Cell[TextData[{ "[", CounterBox["Text"], "] R. Maeder : The Mathematica Programmer II, Academic Press, 1996" }], "Text", CellMargins->{{Inherited, Inherited}, {2, 2}}, CellTags->"MaederII"], Cell[TextData[{ "[", CounterBox["Text"], "] R. Maeder : Term rewriting and programming paradigms, in [", CounterBox["Text", "1995"], "], 7-19" }], "Text", CellMargins->{{Inherited, Inherited}, {2, 2}}, CellTags->"MaederIMS'95"], Cell[TextData[{ "[", CounterBox["Text"], "] R. Maeder : The Design of the Mathematica Programming Language, Dr \ Doob's Journal (April 1992), 86-97" }], "Text", CellMargins->{{Inherited, Inherited}, {2, 2}}, CellTags->"MaederDoobs"], Cell[TextData[{ "[", CounterBox["Text"], "] P. Ramsden\[NonBreakingSpace]: Mathematica in Education: Old Wine in New \ Bottles or a Whole New Vineyard? in [", CounterBox["Text", "1997"], "], 419-426" }], "Text", CellMargins->{{Inherited, Inherited}, {2, 2}}, CellTags->"Ramsden"], Cell[TextData[{ "[", CounterBox["Text"], "] M. Swaine: Stephen Wolfram, Multiparadigm Man, Dr Doob's Journal, 18 \ (January 1993 109-112 and February 1993 105-108)" }], "Text", CellMargins->{{Inherited, Inherited}, {2, 2}}, CellTags->"Wolfram"], Cell[TextData[{ "[", CounterBox["Text"], "] J. Van Leeuven, Ed: Handbook of Theoretical Computer Science, vol A, \ Algorithms and Complexity, Elsevier, 1992" }], "Text", CellMargins->{{Inherited, Inherited}, {2, 2}}, CellTags->"Leeuven"] }, Open ]] }, Open ]] }, FrontEndVersion->"Macintosh 3.0", ScreenRectangle->{{0, 832}, {0, 604}}, WindowSize->{549, 573}, WindowMargins->{{7, Automatic}, {Automatic, 0}}, PrintingCopies->1, PrintingPageRange->{1, Automatic}, PrivateFontOptions->{"FontType"->"Outline"}, StyleDefinitions -> "Default.nb", MacintoshSystemPageSetup->"\<\ 00`0005X0FP000003k0;0?nTok<@30]=I085N0?N0@00005X0FP000003k0;0001 1@00I00100000@0000000BL?004000:Ccj000000000000000000000000000?nT ok<@30]=00P000000040000000000000\>" ] (*********************************************************************** Cached data follows. If you edit this Notebook file directly, not using Mathematica, you must remove the line containing CacheID at the top of the file. The cache data will then be recreated when you save this file from within Mathematica. ***********************************************************************) (*CellTagsOutline CellTagsIndex->{ "Budd"->{ Cell[44586, 1036, 233, 7, 19, "Text", CounterAssignments->{{"Text", 0}}, CellTags->"Budd"]}, "Chomsky"->{ Cell[44822, 1045, 234, 7, 34, "Text", CellTags->"Chomsky"]}, "Chaitin"->{ Cell[45059, 1054, 213, 7, 19, "Text", CellTags->"Chaitin"]}, "Gersting"->{ Cell[45275, 1063, 225, 7, 19, "Text", CellTags->"Gersting"]}, "Gregor"->{ Cell[45503, 1072, 311, 8, 34, "Text", CellTags->"Gregor"]}, "Hayes"->{ Cell[45817, 1082, 233, 8, 19, "Text", CellTags->"Hayes"]}, "Johnson"->{ Cell[46053, 1092, 297, 9, 34, "Text", CellTags->"Johnson"]}, "1995"->{ Cell[46353, 1103, 304, 8, 34, "Text", CellTags->"1995"]}, "1997"->{ Cell[46660, 1113, 333, 8, 34, "Text", CellTags->"1997"]}, "Knuth"->{ Cell[46996, 1123, 212, 7, 19, "Text", CellTags->"Knuth"]}, "Labahn"->{ Cell[47211, 1132, 234, 7, 34, "Text", CellTags->"Labahn"]}, "Leermakers"->{ Cell[47448, 1141, 224, 7, 19, "Text", CellTags->"Leermakers"]}, "MaederI"->{ Cell[47675, 1150, 195, 6, 19, "Text", CellTags->"MaederI"]}, "MaederII"->{ Cell[47873, 1158, 199, 6, 19, "Text", CellTags->"MaederII"]}, "MaederIMS'95"->{ Cell[48075, 1166, 241, 8, 19, "Text", CellTags->"MaederIMS'95"]}, "MaederDoobs"->{ Cell[48319, 1176, 242, 7, 34, "Text", CellTags->"MaederDoobs"]}, "Ramsden"->{ Cell[48564, 1185, 293, 9, 34, "Text", CellTags->"Ramsden"]}, "Wolfram"->{ Cell[48860, 1196, 254, 7, 34, "Text", CellTags->"Wolfram"]}, "Leeuven"->{ Cell[49117, 1205, 247, 7, 34, "Text", CellTags->"Leeuven"]} } *) (*CellTagsIndex CellTagsIndex->{ {"Budd", 50308, 1240}, {"Chomsky", 50432, 1244}, {"Chaitin", 50518, 1247}, {"Gersting", 50605, 1250}, {"Gregor", 50691, 1253}, {"Hayes", 50774, 1256}, {"Johnson", 50858, 1259}, {"1995", 50941, 1262}, {"1997", 51021, 1265}, {"Knuth", 51102, 1268}, {"Labahn", 51185, 1271}, {"Leermakers", 51273, 1274}, {"MaederI", 51362, 1277}, {"MaederII", 51449, 1280}, {"MaederIMS'95", 51541, 1283}, {"MaederDoobs", 51636, 1286}, {"Ramsden", 51726, 1289}, {"Wolfram", 51812, 1292}, {"Leeuven", 51898, 1295} } *) (*NotebookFileOutline Notebook[{ Cell[CellGroupData[{ Cell[1731, 51, 108, 3, 85, "Subtitle"], Cell[1842, 56, 176, 4, 80, "Subsubtitle"], Cell[CellGroupData[{ Cell[2043, 64, 27, 0, 49, "Section"], Cell[2073, 66, 406, 7, 74, "Text"] }, Open ]], Cell[CellGroupData[{ Cell[2516, 78, 33, 0, 49, "Section"], Cell[2552, 80, 1039, 20, 149, "Text"], Cell[3594, 102, 676, 10, 119, "Text"], Cell[4273, 114, 933, 14, 164, "Text"], Cell[5209, 130, 626, 12, 104, "Text"] }, Open ]], Cell[CellGroupData[{ Cell[5872, 147, 43, 0, 49, "Section"], Cell[5918, 149, 564, 9, 104, "Text"], Cell[6485, 160, 763, 11, 134, "Text"], Cell[7251, 173, 520, 8, 89, "Text"], Cell[7774, 183, 346, 6, 74, "Text"], Cell[8123, 191, 601, 9, 104, "Text"] }, Open ]], Cell[CellGroupData[{ Cell[8761, 205, 60, 0, 49, "Section"], Cell[CellGroupData[{ Cell[8846, 209, 53, 0, 43, "Subsection"], Cell[8902, 211, 683, 11, 119, "Text"], Cell[9588, 224, 935, 15, 164, "Text"], Cell[10526, 241, 552, 10, 89, "Text"], Cell[11081, 253, 99, 2, 26, "Input"], Cell[11183, 257, 69, 1, 26, "Input"], Cell[11255, 260, 233, 4, 71, "Input"], Cell[CellGroupData[{ Cell[11513, 268, 90, 1, 26, "Input"], Cell[11606, 271, 60, 1, 26, "Output"] }, Open ]], Cell[11681, 275, 433, 7, 59, "Text"] }, Open ]], Cell[CellGroupData[{ Cell[12151, 287, 63, 0, 43, "Subsection"], Cell[12217, 289, 609, 9, 104, "Text"], Cell[12829, 300, 846, 13, 134, "Text"], Cell[13678, 315, 641, 12, 106, "Input"], Cell[14322, 329, 679, 19, 89, "Text"], Cell[15004, 350, 2737, 43, 69, 2645, 40, "GraphicsData", "PICT", "Graphics"], Cell[17744, 395, 212, 4, 44, "Text"], Cell[17959, 401, 108, 3, 38, "Input"], Cell[CellGroupData[{ Cell[18092, 408, 50, 0, 25, "Input"], Cell[18145, 410, 273, 7, 26, "Output"] }, Open ]] }, Open ]], Cell[CellGroupData[{ Cell[18467, 423, 68, 0, 43, "Subsection"], Cell[18538, 425, 626, 10, 104, "Text"], Cell[19167, 437, 134, 3, 56, "Input"], Cell[19304, 442, 767, 12, 134, "Text"], Cell[20074, 456, 597, 10, 104, "Text"] }, Open ]] }, Open ]], Cell[CellGroupData[{ Cell[20720, 472, 70, 0, 49, "Section"], Cell[20793, 474, 538, 11, 74, "Text"], Cell[21334, 487, 488, 7, 89, "Text"], Cell[21825, 496, 419, 7, 74, "Text"], Cell[22247, 505, 187, 3, 86, "Input"], Cell[22437, 510, 611, 8, 104, "Text"], Cell[23051, 520, 97, 2, 41, "Input"], Cell[23151, 524, 564, 9, 104, "Text"], Cell[23718, 535, 93, 1, 41, "Input"], Cell[23814, 538, 1079, 17, 164, "Text"], Cell[24896, 557, 470, 8, 89, "Text"], Cell[25369, 567, 202, 4, 101, "Input"], Cell[25574, 573, 123, 3, 29, "Text"], Cell[25700, 578, 76, 1, 26, "Input"], Cell[25779, 581, 53, 0, 29, "Text"], Cell[25835, 583, 98, 2, 26, "Input"], Cell[25936, 587, 95, 3, 29, "Text"], Cell[26034, 592, 110, 2, 26, "Input"], Cell[26147, 596, 509, 9, 89, "Text"], Cell[26659, 607, 654, 11, 134, "Text"] }, Open ]], Cell[CellGroupData[{ Cell[27350, 623, 76, 0, 49, "Section"], Cell[CellGroupData[{ Cell[27451, 627, 54, 0, 43, "Subsection"], Cell[27508, 629, 749, 11, 134, "Text"], Cell[28260, 642, 379, 6, 74, "Text"], Cell[28642, 650, 113, 2, 41, "Input"], Cell[28758, 654, 122, 2, 41, "Input"], Cell[28883, 658, 144, 3, 41, "Input"], Cell[29030, 663, 170, 4, 71, "Input"], Cell[29203, 669, 334, 6, 59, "Text"], Cell[29540, 677, 196, 4, 56, "Input"], Cell[29739, 683, 177, 3, 56, "Input"], Cell[29919, 688, 509, 8, 89, "Text"], Cell[30431, 698, 302, 5, 59, "Text"], Cell[30736, 705, 111, 2, 41, "Input"], Cell[30850, 709, 129, 2, 41, "Input"], Cell[30982, 713, 400, 7, 74, "Text"] }, Open ]], Cell[CellGroupData[{ Cell[31419, 725, 57, 0, 43, "Subsection"], Cell[31479, 727, 409, 6, 74, "Text"], Cell[31891, 735, 411, 7, 74, "Text"], Cell[32305, 744, 148, 3, 41, "Input"], Cell[CellGroupData[{ Cell[32478, 751, 60, 1, 26, "Input"], Cell[32541, 754, 113, 2, 41, "Output"] }, Open ]], Cell[32669, 759, 675, 9, 119, "Text"], Cell[33347, 770, 356, 7, 131, "Input"], Cell[33706, 779, 340, 7, 116, "Input"] }, Open ]] }, Open ]], Cell[CellGroupData[{ Cell[34095, 792, 52, 0, 49, "Section"], Cell[34150, 794, 478, 8, 89, "Text"], Cell[34631, 804, 656, 10, 119, "Text"], Cell[CellGroupData[{ Cell[35312, 818, 60, 0, 43, "Subsection"], Cell[35375, 820, 784, 12, 134, "Text"], Cell[36162, 834, 554, 9, 104, "Text"], Cell[36719, 845, 172, 3, 56, "Input"], Cell[36894, 850, 112, 2, 26, "Input"], Cell[37009, 854, 489, 7, 89, "Text"] }, Open ]], Cell[CellGroupData[{ Cell[37535, 866, 66, 0, 43, "Subsection"], Cell[37604, 868, 614, 10, 104, "Text"], Cell[38221, 880, 883, 22, 104, "Text"], Cell[39107, 904, 392, 7, 74, "Text"], Cell[39502, 913, 189, 3, 26, "Input"], Cell[39694, 918, 184, 3, 26, "Input"] }, Open ]], Cell[CellGroupData[{ Cell[39915, 926, 43, 0, 43, "Subsection"], Cell[39961, 928, 592, 10, 104, "Text"], Cell[40556, 940, 176, 4, 29, "Text"], Cell[40735, 946, 590, 9, 104, "Text"] }, Open ]] }, Open ]], Cell[CellGroupData[{ Cell[41374, 961, 31, 0, 49, "Section"], Cell[41408, 963, 432, 7, 89, "Text"], Cell[41843, 972, 711, 13, 104, "Text"], Cell[42557, 987, 399, 7, 74, "Text"], Cell[42959, 996, 316, 6, 59, "Text"], Cell[43278, 1004, 441, 7, 89, "Text"] }, Open ]], Cell[CellGroupData[{ Cell[43756, 1016, 31, 0, 49, "Section"], Cell[43790, 1018, 727, 11, 134, "Text"] }, Open ]], Cell[CellGroupData[{ Cell[44554, 1034, 29, 0, 49, "Section"], Cell[44586, 1036, 233, 7, 19, "Text", CounterAssignments->{{"Text", 0}}, CellTags->"Budd"], Cell[44822, 1045, 234, 7, 34, "Text", CellTags->"Chomsky"], Cell[45059, 1054, 213, 7, 19, "Text", CellTags->"Chaitin"], Cell[45275, 1063, 225, 7, 19, "Text", CellTags->"Gersting"], Cell[45503, 1072, 311, 8, 34, "Text", CellTags->"Gregor"], Cell[45817, 1082, 233, 8, 19, "Text", CellTags->"Hayes"], Cell[46053, 1092, 297, 9, 34, "Text", CellTags->"Johnson"], Cell[46353, 1103, 304, 8, 34, "Text", CellTags->"1995"], Cell[46660, 1113, 333, 8, 34, "Text", CellTags->"1997"], Cell[46996, 1123, 212, 7, 19, "Text", CellTags->"Knuth"], Cell[47211, 1132, 234, 7, 34, "Text", CellTags->"Labahn"], Cell[47448, 1141, 224, 7, 19, "Text", CellTags->"Leermakers"], Cell[47675, 1150, 195, 6, 19, "Text", CellTags->"MaederI"], Cell[47873, 1158, 199, 6, 19, "Text", CellTags->"MaederII"], Cell[48075, 1166, 241, 8, 19, "Text", CellTags->"MaederIMS'95"], Cell[48319, 1176, 242, 7, 34, "Text", CellTags->"MaederDoobs"], Cell[48564, 1185, 293, 9, 34, "Text", CellTags->"Ramsden"], Cell[48860, 1196, 254, 7, 34, "Text", CellTags->"Wolfram"], Cell[49117, 1205, 247, 7, 34, "Text", CellTags->"Leeuven"] }, Open ]] }, Open ]] } ] *) (*********************************************************************** End of Mathematica Notebook file. ***********************************************************************)