(************** Content-type: application/mathematica ************** CreatedBy='Mathematica 5.0' Mathematica-Compatible Notebook This notebook can be used with any Mathematica-compatible application, such as Mathematica, MathReader or Publicon. The data for the notebook starts with the line containing 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[ 72475, 2391]*) (*NotebookOutlinePosition[ 77267, 2566]*) (* CellTagsIndexPosition[ 76355, 2526]*) (*WindowFrame->Normal*) Notebook[{ Cell["\[Copyright] 1996-2003 K. Sutner ", "SmallText"], Cell[CellGroupData[{ Cell["Iteration, Recursion, and Loops", "Title", FontFamily->"Charter", CellTags->"c:1"], Cell[CellGroupData[{ Cell["Primitive Recursion", "Section", CellTags->"c:2"], Cell[TextData[{ "The standard process of building complicated programs from simple ones \ raises the question of the general computational power of a programming \ language. Given certain simple operations, such as the successor function ", Cell[BoxData[ \(TraditionalForm\`x\ \[RightTeeArrow] \ x + 1\)]], ", and certain methods to combine program fragments into larger, and \ presumably more powerful programs, how far can one go? ", "We are here only talking about the ability to write in principle a program \ that implements a certain function, using, say, recursion, not about the \ question whether such a program might be easier to write or maintain using \ some other technique. \n", "\nThe primitive operations are more or less the same in any environment, \ so one really has to take a closer look at the way complicated programs are \ built from simple ones. As it turns out, the most interesting methods are \ loops and recursion. \nIn order to keep our discussion free from specific \ aspects of a particular programming language, let us instead directly \ consider functions (the functions presumable computed by some program or \ other). Furthermore, let us restrict our attention to functions of the type \ ", Cell[BoxData[ \(TraditionalForm\`\(\(\ \)\(f\ : \ \[DoubleStruckCapitalN]\^n\ \[LongRightArrow]\ \[DoubleStruckCapitalN]\^m\)\)\)]], ". In fact, we will mostly discuss scalar functions ", Cell[BoxData[ \(TraditionalForm\`\(\(\ \)\(f\ : \ \[DoubleStruckCapitalN]\^n\ \[LongRightArrow]\ \[DoubleStruckCapitalN]\)\)\)]], ". Other types, such as functions on strings, lists, trees, and so forth, \ are obviously very important for practical purposes, but we want to keep the \ discussion as simple as possible. \n" }], "Text"], Cell[CellGroupData[{ Cell["Basic Functions", "Subsection", CellTags->"c:3"], Cell[TextData[{ "What are reasonable, simple functions that we can safely assume as \ primitives? Here is a very small set of ", StyleBox["basic functions", FontColor->RGBColor[0, 0, 1]], ", that turns out to be sufficient. \n\t\[Bullet] successor function ", Cell[BoxData[ \(TraditionalForm\`S\ : \ \[DoubleStruckCapitalN]\ \[LongRightArrow]\ \ \[DoubleStruckCapitalN]\)]], ", ", Cell[BoxData[ \(TraditionalForm\`S(n)\ = \ n + 1\)]], ",\n\t\[Bullet] projections ", Cell[BoxData[ \(TraditionalForm\`\[Pi]\_i\%\(n : \ \[DoubleStruckCapitalN]\^n\ \[LongRightArrow]\ \[DoubleStruckCapitalN]\)\)]], ", ", Cell[BoxData[ \(TraditionalForm\`\(\[Pi]\_i\%n\)(x\_1, \[Ellipsis], x\_n)\ = \ x\_i\)]], ",\n\t\[Bullet] constants ", Cell[BoxData[ \(TraditionalForm\`N\^\(n : \ \[DoubleStruckCapitalN]\^n\ \[LongRightArrow]\ \[DoubleStruckCapitalN]\)\)]], ", ", Cell[BoxData[ \(TraditionalForm\`\(N\^n\)(x\_1, \[Ellipsis], x\_n)\ = \ 0\)]], ".\nNote that we do not even include a function with constant value ", Cell[BoxData[ \(TraditionalForm\`c\)]], " ", "for each positive integer ", Cell[BoxData[ \(TraditionalForm\`c\ \[GreaterEqual] \ 0\)]], ". Also, we only deal with scalar functions here. " }], "Text"], Cell[TextData[{ "For technical reasons it is helpful to admit the special case ", Cell[BoxData[ \(TraditionalForm\`n\ = \ 0\)]], " for the constants." }], "Text"] }, Closed]], Cell[CellGroupData[{ Cell["Composition", "Subsection", CellTags->"c:4"], Cell[TextData[{ "Given these starting functions, how can be build more complicated ones? \ The most important tool is ", StyleBox["functional composition", FontColor->RGBColor[0, 0, 1]], ". \nSuppose we have functions ", Cell[BoxData[ \(TraditionalForm\`h\ : \ \(\(\[DoubleStruckCapitalN]\)\(\ \)\)\^n\ \[LongRightArrow]\ \[DoubleStruckCapitalN]\)]], " and ", Cell[BoxData[ \(TraditionalForm\`g\_\(i\ : \ \[DoubleStruckCapitalN]\^m\ \ \[LongRightArrow]\ \[DoubleStruckCapitalN]\)\)]], ", ", Cell[BoxData[ \(TraditionalForm\`i\ \[Element] \([n]\)\)]], ". Then \n\t", Cell[BoxData[ \(TraditionalForm\`f\ : \ \[DoubleStruckCapitalN]\^m\[LongRightArrow]\ \ \[DoubleStruckCapitalN]\)]], ", ", Cell[BoxData[ FormBox[ RowBox[{ RowBox[{"h", "(", StyleBox["x", FontWeight->"Bold"], ")"}], " ", "=", " ", RowBox[{"h", "(", RowBox[{ RowBox[{\(g\_1\), "(", StyleBox["x", FontWeight->"Bold"], ")"}], ",", "\[Ellipsis]", ",", RowBox[{\(g\_n\), "(", StyleBox["x", FontWeight->"Bold"], ")"}]}], ")"}]}], TraditionalForm]]], ", \nis the composition of ", Cell[BoxData[ \(TraditionalForm\`h\)]], " and the ", Cell[BoxData[ \(TraditionalForm\`g\_i\)]], ". Here ", Cell[BoxData[ FormBox[ StyleBox["x", FontWeight->"Bold"], TraditionalForm]]], " denotes a vector in ", Cell[BoxData[ \(TraditionalForm\`\[DoubleStruckCapitalN]\^m\)]], ". \nWe write ", Cell[BoxData[ \(TraditionalForm\`f\ = \ h\[SmallCircle]\ \((g\_1, \[Ellipsis], g\_m)\)\)]], ". " }], "Text"], Cell[TextData[{ "For example, we can define a function ", Cell[BoxData[ \(TraditionalForm\`f\ : \ \[DoubleStruckCapitalN]\^3\[LongRightArrow]\ \ \[DoubleStruckCapitalN]\)]], " with constant value 1 by ", Cell[BoxData[ \(TraditionalForm\`f\ = \ S\ \[SmallCircle]\ 0\^3\)]], ". We get a function ", Cell[BoxData[ \(TraditionalForm\`f\_\(2\ : \ \[DoubleStruckCapitalN]\^3\ \[LongRightArrow]\ \[DoubleStruckCapitalN]\)\)]], " with constant value 2 by ", Cell[BoxData[ \(TraditionalForm\`f\_2\ = \ S\ \[SmallCircle]\ f\)]], ", and so forth." }], "Text"], Cell["\<\ For technical reasons it is helpful to admit the special case \ \>", "Text"] }, Closed]], Cell[CellGroupData[{ Cell["Primitive Recursion", "Subsection", CellTags->"c:5"], Cell[TextData[{ "Clearly, composition alone is not enough to produce anything interesting, \ given the very small set of primitive functions that we have. Here is a more \ powerful way to combine given functions: a certain type of recursion, called \ primitive recursion.\nSuppose we have functions ", Cell[BoxData[ \(TraditionalForm\`g\ : \ \(\(\[DoubleStruckCapitalN]\)\(\ \)\)\^n\ \[LongRightArrow]\ \[DoubleStruckCapitalN]\)]], " and ", Cell[BoxData[ \(TraditionalForm\`h\ : \ \[DoubleStruckCapitalN]\^\(n + 2\)\ \ \[LongRightArrow]\ \[DoubleStruckCapitalN]\)]], ", where ", Cell[BoxData[ \(TraditionalForm\`\(\(n\)\(\ \)\(\[GreaterEqual]\)\(\ \)\(0.\)\(\ \)\)\ \)]], "Then we can define a new function ", Cell[BoxData[ \(TraditionalForm\`f\ : \ \[DoubleStruckCapitalN]\^\(n + 1\)\ \[LongRightArrow]\ \[DoubleStruckCapitalN]\)]], " by\n\t", Cell[BoxData[ FormBox[ RowBox[{" ", RowBox[{ RowBox[{"f", "(", RowBox[{"0", ",", StyleBox["x", FontWeight->"Bold"]}], ")"}], " ", "=", " ", RowBox[{"g", "(", StyleBox["x", FontWeight->"Bold"], ")"}]}]}], TraditionalForm]]], ", and \n\t", Cell[BoxData[ FormBox[ RowBox[{ RowBox[{"f", "(", RowBox[{\(n + 1\), ",", StyleBox["x", FontWeight->"Bold"]}], ")"}], " ", "=", " ", RowBox[{"h", "(", " ", RowBox[{"n", ",", " ", RowBox[{"f", "(", RowBox[{"n", ",", StyleBox["x", FontWeight->"Bold"]}], ")"}], ",", " ", StyleBox["x", FontWeight->"Bold"]}], " ", ")"}]}], TraditionalForm]]], ".\nThe function ", Cell[BoxData[ \(TraditionalForm\`f\)]], " is said to be defined from ", Cell[BoxData[ \(TraditionalForm\`g\)]], " and ", Cell[BoxData[ \(TraditionalForm\`h\)]], " by primitive recursion. \nWe write ", Cell[BoxData[ \(TraditionalForm\`f\ = \ PrimRec(\ g, \ h\ )\)]], ". " }], "Text"] }, Closed]], Cell[CellGroupData[{ Cell["Factorials Unraveled", "Subsection", CellTags->"c:6"], Cell[TextData[{ "In the special case ", Cell[BoxData[ \(TraditionalForm\`n = 0\)]], " the function ", Cell[BoxData[ \(TraditionalForm\`g\)]], " is really just a constant, so we have the familiar pattern known, for \ example, from the ususal definition of the factorial function:\n\t", Cell[BoxData[ \(TraditionalForm\`f(0)\ = \ 1\)]], ",\n\t", Cell[BoxData[ \(TraditionalForm\`f( n + 1)\ = \ \((n + 1)\)\ \[CenterDot]\ \(f(n)\)\)]], ". \nHere ", Cell[BoxData[ \(TraditionalForm\`\(\(f\)\(\ \)\(=\)\(\ \)\(PrimRec(\ S\[SmallCircle]N\^0, \ h\ )\)\(\ \)\)\)]], " where ", Cell[BoxData[ \(TraditionalForm\`h(\ x, \ y\ )\ = \ mult(\ S(x), \ y)\)]], ", and mult denotes ordinary multiplication, ", Cell[BoxData[ \(TraditionalForm\`\(\(\ \)\(mult\ : \ \[DoubleStruckCapitalN]\ \ \[Cross]\[DoubleStruckCapitalN]\ \ \[LongRightArrow]\ \[DoubleStruckCapitalN]\ \)\)\)]], ". Thus, ", Cell[BoxData[ \(TraditionalForm\`h\ = \ mult\[SmallCircle]\((\ S\ \[SmallCircle]\ \[Pi]\_1\%2, \ \[Pi]\_2\%2)\)\)]], " in our more formal notation.\nHow much do we need to define \ multiplication? The usual recursive definition is \n\t", Cell[BoxData[ \(TraditionalForm\`mult(0, y)\ = \ 0\)]], ",\n\t", Cell[BoxData[ \(TraditionalForm\`mult(x + 1, y)\ = \ add(\ mult(x, y), \ y\ )\)]], ",\nwhere ", Cell[BoxData[ \(TraditionalForm\`add\ : \ \[DoubleStruckCapitalN]\ \[Cross]\ \ \[DoubleStruckCapitalN]\ \ \[LongRightArrow]\ \[DoubleStruckCapitalN]\)]], " denotes ordinary addition. So, ", Cell[BoxData[ \(TraditionalForm\`mult\ = \ PrimRec(\ N\^1, \ h\ )\)]], " where this time ", Cell[BoxData[ \(TraditionalForm\`h(\ x, \ z, \ y\ )\ = \ add(\ z, \ y)\)]], ", or more formally, ", Cell[BoxData[ \(TraditionalForm\`h\ = \ add\ \[SmallCircle]\ \((\ \[Pi]\_2\%3, \ \[Pi]\_3\%3)\)\)]], ". \nSo, are left with addition. Again, we can write down a simple \ recursive definition:\n\t", Cell[BoxData[ \(TraditionalForm\`add(0, y)\ = \ y\)]], ",\n\t", Cell[BoxData[ \(TraditionalForm\`add(x + 1, y)\ = \ S(add(x, y))\)]], ".\nThis time, ", Cell[BoxData[ \(TraditionalForm\`add\ = \ PrimRec(\ \[Pi]\_1\%1, \ S\ \[SmallCircle]\ \[Pi]\_2\%3\ )\)]], ". In other words, addition can be directly expressed in terms of our \ basic functions, composition, and primitive recursion. But then \ multiplication can be expressed the same way, and the same holds for the \ factorical function:" }], "Text"], Cell[TextData[Cell[BoxData[ FormBox[GridBox[{ {"f", "=", \(PrimRec(\ S\[SmallCircle]N\^0, \ mult\[SmallCircle]\((\ S\ \[SmallCircle]\ \[Pi]\_1\%2, \ \[Pi]\_2\%2)\)\ )\)}, {" ", "=", \(PrimRec(\ S\[SmallCircle]N\^0, \ \(PrimRec(\ N\^1, add\ \[SmallCircle]\ \((\ \[Pi]\_2\%3, \ \[Pi]\_3\%3)\)\ \ )\)\[SmallCircle]\((\ S\ \[SmallCircle]\ \[Pi]\_1\%2, \ \[Pi]\_2\%2)\)\ )\)}, {" ", "=", \(PrimRec(\ S\[SmallCircle]N\^0, \ \(PrimRec(\ N\^1, \(PrimRec(\ \[Pi]\_1\%1, \ S\ \[SmallCircle]\ \[Pi]\_2\%3\ )\)\ \[SmallCircle]\ \ \((\ \[Pi]\_2\%3, \ \[Pi]\_3\%3)\)\ )\)\[SmallCircle]\((\ S\ \[SmallCircle]\ \[Pi]\_1\%2, \ \[Pi]\_2\%2)\)\ )\)} }], TraditionalForm]]]], "Text"], Cell["\<\ Admittedly, a horror. However, it shows that the factorial function \ at heart is just a triple application of recursion to trivial starting \ functions. No other ideas are necessary at all. \ \>", "Text"] }, Closed]], Cell[CellGroupData[{ Cell[" More Primitive Recursive Functions", "Subsection", CellTags->"c:7"], Cell[CellGroupData[{ Cell["Closure Properties", "Subsubsection", CellTags->"c:8"], Cell[TextData[{ "Enumerating more and more primitive recursive functions becomes quite \ tedious after a while. It is more efficient to establish closure properties, \ and then to use them to demonstrate that certain functions can be computed \ using only primitive recursion. A closure property typically is an assertion \ of the form\n\n\t\[Bullet] if a function ", Cell[BoxData[ \(TraditionalForm\`g\)]], " is prim.rec., then the function ", Cell[BoxData[ \(TraditionalForm\`f\ = \ \(\(...\) \(g\)\) ... \)]], " is also prim.rec. \n\nHere is a typical example: closure under \ summation. \n\n", StyleBox["Lemma", FontWeight->"Bold"], ": Let ", Cell[BoxData[ \(TraditionalForm\`f(x, y)\ = \ \[Sum]\_\(z < x\)\ g(z, y)\)]], " where ", Cell[BoxData[ \(TraditionalForm\`g\)]], " is prim.rec. Then ", Cell[BoxData[ \(TraditionalForm\`f\)]], " is also prim.rec. \nProof.\n\n\[EmptySquare]" }], "Text"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[" Implementing Primitive Recursion in Mathematica", "Subsection", CellTags->"c:9"], Cell[TextData[{ "It is very easy to implement primitive recursion in ", StyleBox["Mathematica, ", FontSlant->"Italic"], "more specifically we can define a functional (just a fancy name to \ distinguish it from ordinay functions) ", StyleBox["PrimRec", "SmallText"], " that performs primitive recursion on its argument functions. Composition \ will be expressed as the functional ", StyleBox["Comp", "SmallText"], ". Since functions tend to be polyadic, we do not have to worry too much \ about the precise number of arguments in projections and constants." }], "Text"], Cell[CellGroupData[{ Cell["Code", "Subsubsection", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:10"], Cell[TextData[{ "Set ", StyleBox["$traceprimrec = False", "MR"], " to turn off tracing. " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell["\<\ Clear[Zero,S,Pro,PrimRec,Comp,A,AckerRules,A1,r1,r2,r3]; $traceprimrec = True;\ \>", "Input", InitializationCell->True, AspectRatioFixed->True], Cell["\<\ S = (# + 1)&; Zero = 0&; Pro[ i_Integer ] := ({##}[[i]])&;\ \>", "Input", InitializationCell->True, AspectRatioFixed->True], Cell["\<\ Comp[ f_, g_ ] := f[ g[##] ]&; Comp[ f_, g1_, g2_ ] := f[ g1[##],g2[##] ]&; Comp[ f_, g1_, g2_, g3_ ] := f[ g1[##],g2[##],g3[##] ]&; \t\t \ \>", "Input", InitializationCell->True, AspectRatioFixed->True], Cell["\<\ PrimRec[ h_, g_ ] := Block[ {x,y,prev }, \t\tx = #1; \t\ty = ##2; \t\tIf[ x > 0, \t\t\tprev = PrimRec[h,g][x-1, y ]; \t\tIf[ $traceprimrec, \t\t\tPrint[ \"-> \", x-1,\" \",prev,\" \", y ]]; \t\t\th[ x-1, prev, y ], \t\t\tg[ y ] \t\t] ]&;\ \>", "Input", InitializationCell->True, AspectRatioFixed->True], Cell[BoxData[ \(\($traceprimrec = False;\)\)], "Input"] }, Closed]], Cell[CellGroupData[{ Cell["Constructing Factorials", "Subsubsection", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:11"], Cell["Constants", "Text", Evaluatable->False, AspectRatioFixed->True], Cell["\<\ One = Comp[ S, Zero ]; Two = Comp[ S, One ];\ \>", "Input", AspectRatioFixed->True], Cell["\<\ Two[ 3, 5, 7 ] Two[]\ \>", "Input", AspectRatioFixed->True], Cell["Addition", "Text", Evaluatable->False, AspectRatioFixed->True], Cell["add = PrimRec[ Comp[ S, Pro[2] ], Pro[1] ];", "Input", AspectRatioFixed->True], Cell["add[ 4, 7 ]", "Input", AspectRatioFixed->True], Cell["\<\ Clear[z]; add[ 3, z ]\ \>", "Input", AspectRatioFixed->True], Cell["Subtraction", "Text", Evaluatable->False, AspectRatioFixed->True], Cell["sub1 = PrimRec[ Pro[1], Zero ];", "Input"], Cell["sub1[ 0 ]", "Input"], Cell["sub1[ 4 ]", "Input"], Cell["subb = PrimRec[ Comp[ sub1, Pro[2] ], Pro[1] ];", "Input"], Cell["subb[ 2, 7 ]", "Input"], Cell["subb[ 5, 4 ]", "Input"], Cell["sub = Comp[ subb, Pro[2], Pro[1] ];", "Input"], Cell["sub[ 3, 2 ]", "Input"], Cell["sub[ 3, 5 ]", "Input"], Cell["Multiplication", "Text", Evaluatable->False, AspectRatioFixed->True], Cell["mult = PrimRec[ Comp[ add, Pro[2], Pro[3] ], Zero ];", "Input"], Cell["mult[ 3, 4 ]", "Input"], Cell["Factorial", "Text", Evaluatable->False, AspectRatioFixed->True], Cell["fac = PrimRec[ Comp[mult, Comp[S,Pro[1]], Pro[2]], One ];", "Input"], Cell["fac[4]", "Input"] }, Closed]] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell["Loop Programs", "Section", CellTags->"c:12"], Cell[CellGroupData[{ Cell[" The Definition", "Subsection", CellTags->"c:13"], Cell[TextData[{ "The LOOP programming language is very simple, and straightforward to \ understand for anyone having had experience with a higher level programming \ language. First off, there is only one type of variables in LOOP, namely \ variables ranging over \[DoubleStruckCapitalN], the set of natural numbers. \ As usual, the names of variables are required to start with a letter, \ followed be any sequence of letters and digits.\nThe reserved words in LOOP \ are ", StyleBox["do", FontWeight->"Bold"], ", and ", StyleBox["od", FontWeight->"Bold"], ". Furthermore, there is an assignment operator = and an increment operator \ ++, used in the obvious fashion. The only literal is 0; colons and semicolons \ are used as separators. Thus, we have statements of the form " }], "Text"], Cell["\<\ \tX = 0; \tX = Y; \tX++; \tdo X : od\ \>", "InlineInput"], Cell[TextData[{ "In order to make it easy to attach semantics to this language, we insist \ that in a loop statement the loop variable ", Cell[BoxData[ \(TraditionalForm\`X\)]], " does not occur inside the statement bracketed by ", StyleBox["do", FontWeight->"Bold"], " and ", StyleBox["od", FontWeight->"Bold"], ". The interpretation will be that the statement is executed ", Cell[BoxData[ \(TraditionalForm\`X\)]], " times, depending only on the value of ", Cell[BoxData[ \(TraditionalForm\`X\)]], " at the time the loop was entered. In a syntactically correct program, we \ require that the variables in loops all must have a value at the time the \ statement is executed. It follows that every loop program terminates.\nThus, \ LOOP is very limited. There are no data types other than unsigned integers, \ no subroutines, no while loops, and so on. Nonetheless, LOOP programs are \ very powerful. " }], "Text"], Cell["\<\ For example, we can express the usual the if-then conditional \ construct in terms of a loop. We have to be careful to execute the statement \ only once. \ \>", "Text"], Cell["\<\ \t// if X then \tY = 0; \tdo X : Y = 1; od \tdo Y : od \ \>", "InlineInput"], Cell["\<\ The semantics are quite similar to the way C treats integers as \ Booleans: the value 0 is considered to represent False, any other value \ represents True. Next, the if-then-else construct can be introduced by a combination of a \ loop, and ordinary if-thens.\ \>", "Text"], Cell["\<\ \t// if X then else fi \tif X then fi \tY = 1; \tdo X : Y = 0; od \tif Y then fi \ \>", "InlineInput"], Cell[TextData[{ "In order to compute functions with LOOP, we need to associate some \ input/output behavior with the programs. Let ", Cell[BoxData[ \(TraditionalForm\`P\)]], " be a LOOP program. We say that ", Cell[BoxData[ \(TraditionalForm\`P\)]], " computes the function ", Cell[BoxData[ \(TraditionalForm\`f\ : \ \[DoubleStruckCapitalN]\^n\ \ \[LongRightArrow]\ \[DoubleStruckCapitalN]\^m\)]], " via variables ", Cell[BoxData[ \(TraditionalForm\`x\_1, \[Ellipsis], x\_n\)]], " and ", Cell[BoxData[ \(TraditionalForm\`y\_1, \[Ellipsis], \ y\_m\)]], " iff for every ", Cell[BoxData[ \(TraditionalForm\`n\)]], "-tuple ", Cell[BoxData[ \(TraditionalForm\`a\_1, \[Ellipsis], a\_n\ \[Element] \ \ \[DoubleStruckCapitalN]\)]], " the following holds: if one sets the value variable ", Cell[BoxData[ \(TraditionalForm\`x\_i\)]], " to ", Cell[BoxData[ \(TraditionalForm\`a\_i\)]], " for ", Cell[BoxData[ \(TraditionalForm\`i\ = \ 1, \[Ellipsis], n\)]], " and executes ", Cell[BoxData[ \(TraditionalForm\`P\)]], " the values of variables ", Cell[BoxData[ \(TraditionalForm\`y\_i\)]], " will be ", Cell[BoxData[ \(TraditionalForm\`b\_i\)]], ", for ", Cell[BoxData[ \(TraditionalForm\`i\ = \ 1, \[Ellipsis], n\)]], ", where \n\t", Cell[BoxData[ \(TraditionalForm\`f(a\_1, \[Ellipsis], a\_n)\ \ = \ \ \(\((b\_1, \[Ellipsis], \ b\_m)\)\(.\)\)\)]], "\nThe function ", Cell[BoxData[ \(TraditionalForm\`f\)]], " is LOOP-computable if there exists such a program. " }], "Text"], Cell[TextData[{ "As an example, the next program computes addition, via ", Cell[BoxData[ \(TraditionalForm\`x, \ y\)]], " and ", Cell[BoxData[ \(TraditionalForm\`z\)]], ", so that addition is LOOP-computable. " }], "Text"], Cell["\<\ \t// addition \tz = x; \tdo y : z++; od \ \>", "InlineInput"], Cell[TextData[{ "Similarly we can use LOOP programs to compute relations. More precisely, a \ relation ", Cell[BoxData[ \(TraditionalForm\`R\ \[SubsetEqual] \ \[DoubleStruckCapitalN]\^n\)]], " is computed by a LOOP program P via variables ", Cell[BoxData[ \(TraditionalForm\`x\_1, \[Ellipsis], x\_n\)]], " and ", Cell[BoxData[ \(TraditionalForm\`y\)]], " iff for every ", Cell[BoxData[ \(TraditionalForm\`n\)]], "-tuple ", Cell[BoxData[ \(TraditionalForm\`a\_1, \[Ellipsis], a\_n\ \[Element] \ \ \[DoubleStruckCapitalN]\)]], " the following holds: if one sets the value variable ", Cell[BoxData[ \(TraditionalForm\`x\_i\)]], " to ", Cell[BoxData[ \(TraditionalForm\`a\_i\)]], " for ", Cell[BoxData[ \(TraditionalForm\`i\ = \ 1, \[Ellipsis], n\)]], " and executes ", Cell[BoxData[ \(TraditionalForm\`P\)]], " the value of variable ", Cell[BoxData[ \(TraditionalForm\`y\)]], " will be ", Cell[BoxData[ \(TraditionalForm\`0\)]], " iff ", Cell[BoxData[ \(TraditionalForm\`\(\(R(a\_1, \[Ellipsis], a\_n)\)\(\ \)\)\)]], " holds, and 1 otherwise. \nIn other words, ", Cell[BoxData[ \(TraditionalForm\`P\)]], " computes the characteristic function ", Cell[BoxData[ \(TraditionalForm\`\[Chi]\_R\)]], ". A relation is LOOP-decidable iff there exists such a program. \n\nFor \ example, equality is LOOP-decidable, but it takes quite a bit of effort to \ show that this is the case. " }], "Text"] }, Closed]], Cell[CellGroupData[{ Cell[" A Hierarchy", "Subsection", CellTags->"c:14"], Cell[TextData[{ "There is a natural way to organize LOOP-programs into a hierarchy: a \ program ", Cell[BoxData[ \(TraditionalForm\`P\)]], " is in ", Cell[BoxData[ \(TraditionalForm\`\[ScriptCapitalL]\_n\)]], " if the loop statements in ", Cell[BoxData[ \(TraditionalForm\`\(\(P\)\(\ \)\)\)]], " are nested at most ", Cell[BoxData[ \(TraditionalForm\`n\)]], " levels deep. More precisely, \n\n\t\[FilledCircle] ", Cell[BoxData[ \(TraditionalForm\`\[ScriptCapitalL]\_0\)]], " is the collection of all LOOP-programs without loop statements,\n\t\ \[FilledCircle] ", Cell[BoxData[ \(TraditionalForm\`\[ScriptCapitalL]\_\(n + 1\)\)]], " is the collection of all LOOP-programs such that in any loop statement\n\t\ ", StyleBox[" ", "SmallText"], StyleBox["do X : S od", "MR"], " we have ", Cell[BoxData[ \(TraditionalForm\`S\)]], " is in ", Cell[BoxData[ \(TraditionalForm\`\(\[Union]\_\(i \[LessEqual] n\)\[ScriptCapitalL]\_i\ \)\)]], ".\n\nNote that the hierarchy is strictly ascending: ", Cell[BoxData[ \(TraditionalForm\`\[ScriptCapitalL]\_n\ \[Subset] \ \[ScriptCapitalL]\ \_\(n + 1\)\)]], ". \nLikewise, a function is ", Cell[BoxData[ \(TraditionalForm\`\[ScriptCapitalL]\_n\)]], "-computable iff there is a program in ", Cell[BoxData[ \(TraditionalForm\`\[ScriptCapitalL]\_n\)]], " that computes the function.\n\nWe will now show how to define a number of \ standard functions in this hierarchy. We have already seen that addition is \ in ", Cell[BoxData[ \(TraditionalForm\`\[ScriptCapitalL]\_1\)]], ". " }], "Text"], Cell[CellGroupData[{ Cell[" Multiplicaction", "Subsubsection", CellTags->"c:15"], Cell[TextData[{ "We have seen that addition is in ", Cell[BoxData[ \(TraditionalForm\`\[ScriptCapitalL]\_1\)]], ", a similar construction shows that multiplication is in ", Cell[BoxData[ \(TraditionalForm\`\[ScriptCapitalL]\_2\)]], "." }], "Text"], Cell["\<\ \t// multiplication x * y ==> z \tz = 0; \tdo x : \t\tdo y : \t\t\tz++; \t\tod \tod \ \>", "InlineInput"] }, Closed]], Cell[CellGroupData[{ Cell[" Predecessors and Subtraction", "Subsubsection", CellTags->"c:16"], Cell[TextData[{ "Here is a function that turns out to be in ", Cell[BoxData[ \(TraditionalForm\`\[ScriptCapitalL]\_1\)]], ", though it requires a little trick to show that it is: the predecessor \ function ", Cell[BoxData[ \(TraditionalForm\`\(\(\ \)\(\(pre( 0)\)\(\ \ \)\(=\)\(\ \)\(0\)\(\ \)\)\)\)]], " and ", Cell[BoxData[ \(TraditionalForm\`pre(x + 1)\ = \ x\)]], ". \n\nThe following program computes ", Cell[BoxData[ \(TraditionalForm\`pre\)]], " via ", Cell[BoxData[ \(TraditionalForm\`x\)]], " and ", Cell[BoxData[ \(TraditionalForm\`z\)]], ". " }], "Text"], Cell["\<\ \t// predecessor x ==> z \ty = 0; \tz = 0; \tdo x : \t\tz = y; \t\ty++; \tod \ \>", "InlineInput"], Cell[TextData[{ "Now, proper subtraction ", Cell[BoxData[ \(TraditionalForm\`x\ \(-\&\[Bullet]\ y\)\)]], " is easy:" }], "Text"], Cell["\<\ \t// subtraction x - y ==> z \tz = x; \tdo y : \t\tz = pre(Z); \tod \ \>", "InlineInput"], Cell[TextData[{ "As written, this is not a legitimate LOOP-program, the function call to \ pre has to be replaced by the previous program, after suitable renaming of \ variables. Also note that this is an example of an ", Cell[BoxData[ \(TraditionalForm\`\[ScriptCapitalL]\_2\)]], " program. " }], "Text"] }, Closed]], Cell[CellGroupData[{ Cell[" Equality", "Subsubsection", CellTags->"c:17"], Cell[TextData[{ "Using proper subtraction and addition we can finally show that equality is \ LOOP-decidable. The idea is that \n\n\t", Cell[BoxData[ \(TraditionalForm\`x\ = \ \(y\ \ \ \[DoubleLongLeftRightArrow]\ \ \ \ \((x\ \(-\&\[Bullet]\ y\))\)\ \ + \ \((y\ \(-\&\[Bullet]\ x\))\)\ = \ 0\)\)]], "\n\nThe following program decides equality of ", Cell[BoxData[ \(TraditionalForm\`x\)]], " and ", Cell[BoxData[ \(TraditionalForm\`y\)]], " with output variable ", Cell[BoxData[ \(TraditionalForm\`z\)]], ". Again we use some obvious abbreviations to keep the length of the \ program under control." }], "Text"], Cell["\<\ \tz1 = sub(x,y); \tz2 = sub(y,x); \tz3 = add(z1,z2); \tif z3 then z = 0; else z = 1; fi \t\ \>", "InlineInput"], Cell["\<\ It is a good exercise to write the program out in full to determine \ its position in the hierarchy.\ \>", "Text"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[" An Implementation", "Subsection", CellTags->"c:18"], Cell[TextData[{ "The reader will have noticed that it is quite straightforward to implement \ LOOP-programs in ", StyleBox["Mathematica", FontSlant->"Italic"], ". The only slight adjustment one has to make is to use a ", StyleBox["Do[]", "MR"], " statement in place of the loop construct (the iterator has to move to the \ end).\nFor example, the LOOP-program for multiplication takes the form" }], "Text"], Cell[BoxData[{ \(x\ = \ 3; \ y\ = \ 5;\), "\n", \(\(z = \ 0;\)\), "\n", \(\(Do[\ Do[\ \(z++\), \ {x}], \ {y}\ ];\)\), "\n", \(z\)}], "Input"], Cell["And here is the predecessor program:", "Text"], Cell[BoxData[{ \(\(x\ = \ 5;\)\), "\n", \(\(y\ = \ \(z\ = \ 0\);\)\), "\n", \(Do[\ z\ = \ y; \ \(y++\), \ {x}\ ]\), "\n", \(z\)}], "Input"], Cell["It is a good idea to implement the equality testing program.", "Text"] }, Closed]], Cell[CellGroupData[{ Cell[" Closure Properties", "Subsection", CellTags->"c:19"], Cell[TextData[{ "It is worth taking a closer look at the abbreviations that we used \ informally to communicate LOOP-programs in the last section. Intuitively it \ is clear how one would go about translating our pseudo code into real \ LOOP-programs, but it is worth while pinning down the essential properties of \ these programs that one can use to demonstrate that certain functions are \ LOOP-computable.\n\nThe key idea here is again that of a ", StyleBox["closure property", FontColor->RGBColor[0, 0, 1]], ", an assertion of the form: if such and such functions are \ LOOP-computable, so are such and such functions. Starting from very primitive \ functions that are obviously LOOP-computable, we can build up more and more \ complicated functions by invoking closure properties. All these arguments are \ constructive in the sense that, if need be, one could actually write out a \ LOOP-program in full that computes the corresponding function. " }], "Text"], Cell[CellGroupData[{ Cell["Composition", "Subsubsection", CellTags->"c:20"], Cell[TextData[{ "The crucial closure property of LOOP-programs is closure under \ composition.\n\n", StyleBox["Theorem", FontWeight->"Bold"], ": Closure under Composition\nSuppose ", Cell[BoxData[ \(TraditionalForm\`f\ : \ \(\(\[DoubleStruckCapitalN]\)\(\ \)\)\^n\ \[LongRightArrow]\ \[DoubleStruckCapitalN]\)]], " and ", Cell[BoxData[ \(TraditionalForm\`g\_\(i\ : \ \[DoubleStruckCapitalN]\^m\ \ \[LongRightArrow]\ \[DoubleStruckCapitalN]\)\)]], ", ", Cell[BoxData[ \(TraditionalForm\`i\ \[Element] \([n]\)\)]], ", are LOOP-computable. Then \n\t", Cell[BoxData[ \(TraditionalForm\`h\ : \ \[DoubleStruckCapitalN]\^m\[LongRightArrow]\ \ \[DoubleStruckCapitalN]\)]], ", ", Cell[BoxData[ FormBox[ RowBox[{ RowBox[{"h", "(", StyleBox["x", FontWeight->"Bold"], ")"}], " ", "=", " ", RowBox[{"f", "(", RowBox[{ RowBox[{\(g\_1\), "(", StyleBox["x", FontWeight->"Bold"], ")"}], ",", "\[Ellipsis]", ",", RowBox[{\(g\_n\), "(", StyleBox["x", FontWeight->"Bold"], ")"}]}], ")"}]}], TraditionalForm]]], ", \nis also LOOP-computable. Here ", Cell[BoxData[ FormBox[ StyleBox["x", FontWeight->"Bold"], TraditionalForm]]], " denotes a vector in ", Cell[BoxData[ \(TraditionalForm\`\[DoubleStruckCapitalN]\^m\)]], ". \nProof.\nFor the sake of simplicity we will only consider the case ", Cell[BoxData[ \(TraditionalForm\`n\ = \ \(m\ = \ 1\)\)]], ", is is not hard to generalize the argument. Thus, we are given \ LOOP-computable functions ", Cell[BoxData[ \(TraditionalForm\`f, g\ : \ \[DoubleStruckCapitalN]\ \[LongRightArrow]\ \ \[DoubleStruckCapitalN]\)]], " and we have to show that ", Cell[BoxData[ \(TraditionalForm\`h(x)\ = \ f(g(x))\)]], " is again LOOP-computable. Suppose ", Cell[BoxData[ \(TraditionalForm\`P\_1\)]], " is a LOOP-program that computes ", Cell[BoxData[ \(TraditionalForm\`\(\(f\)\(\ \)\)\)]], " via ", Cell[BoxData[ \(TraditionalForm\`x\_1\)]], "and ", Cell[BoxData[ \(TraditionalForm\`y\_1\)]], ", and also uses internal variables ", Cell[BoxData[ \(TraditionalForm\`z\_1, \[Ellipsis], z\_k\)]], ". Likewise, ", Cell[BoxData[ \(TraditionalForm\`P\_2\)]], "computes ", Cell[BoxData[ \(TraditionalForm\`g\)]], " via ", Cell[BoxData[ \(TraditionalForm\`x\_2\)]], "and ", Cell[BoxData[ \(TraditionalForm\`y\_2\)]], ", using internal variables ", Cell[BoxData[ \(TraditionalForm\`z\_1\%\[Prime], \ \[Ellipsis], z\_l\%\[Prime]\)]], ". We may safely assume that all these variables are distinct (rename \ otherwise). Now consider the program" }], "Text"], Cell[TextData[{ "\n\t", Cell[BoxData[ \(TraditionalForm\`P\_2\)]], "\n\t", Cell[BoxData[ \(TraditionalForm\`\(x\_1\ = \ y\_2;\)\)]], "\n\t", Cell[BoxData[ \(TraditionalForm\`P\_1\)]], "\n\t" }], "InlineInput"], Cell[TextData[{ "This program computes ", Cell[BoxData[ \(TraditionalForm\`h\)]], " via ", Cell[BoxData[ \(TraditionalForm\`x\_2\)]], " and ", Cell[BoxData[ \(TraditionalForm\`y\_1\)]], ". \n\[EmptySquare]" }], "Text"] }, Closed]], Cell[CellGroupData[{ Cell["Primitive Recursion", "Subsubsection", CellTags->"c:21"], Cell["\<\ Somewhat more surprising is the closure of LOOP-program, or rather, \ LOOP-computable functions, under primitive recursion.\ \>", "Text"], Cell[TextData[{ StyleBox["Theorem", FontWeight->"Bold"], ": Closure under Primitive Recursion\nThe LOOP-computable functions are \ closed under primitive recursion. If ", Cell[BoxData[ \(TraditionalForm\`g\ : \ \(\(\[DoubleStruckCapitalN]\)\(\ \)\)\^n\ \[LongRightArrow]\ \[DoubleStruckCapitalN]\)]], " and ", Cell[BoxData[ \(TraditionalForm\`h\ : \ \[DoubleStruckCapitalN]\^\(n + 2\)\ \ \[LongRightArrow]\ \[DoubleStruckCapitalN]\)]], " ", "are LOOP-computable, then so is ", Cell[BoxData[ \(TraditionalForm\`f\ : \ \[DoubleStruckCapitalN]\^\(n + 1\)\ \[LongRightArrow]\ \[DoubleStruckCapitalN]\)]], " defined by\n\t", Cell[BoxData[ FormBox[ RowBox[{" ", RowBox[{ RowBox[{"f", "(", RowBox[{"0", ",", StyleBox["x", FontWeight->"Bold"]}], ")"}], " ", "=", " ", RowBox[{"g", "(", StyleBox["x", FontWeight->"Bold"], ")"}]}]}], TraditionalForm]]], ", and \n\t", Cell[BoxData[ FormBox[ RowBox[{ RowBox[{"f", "(", RowBox[{\(n + 1\), ",", StyleBox["x", FontWeight->"Bold"]}], ")"}], " ", "=", " ", RowBox[{"h", "(", " ", RowBox[{"n", ",", " ", RowBox[{"f", "(", RowBox[{"n", ",", StyleBox["x", FontWeight->"Bold"]}], ")"}], ",", " ", StyleBox["x", FontWeight->"Bold"]}], " ", ")"}]}], TraditionalForm]]], ".\n\nProof.\nThe proof utilizes are standard method to compute functions \ defined by primitive recursion: dynamic programming. First compute ", Cell[BoxData[ \(TraditionalForm\`f(0, x)\)]], ", then ", Cell[BoxData[ \(TraditionalForm\`f(1, x)\)]], ", and so forth, until the desired value ", Cell[BoxData[ \(TraditionalForm\`f(n, x)\)]], " is reached. Note that it suffices to store the last value (we do not need \ to maintain an array of all values already computed), so it is quite easy to \ write a corresponding LOOP-program. \nFor the sake of simplicity we will only \ consider the case ", Cell[BoxData[ \(TraditionalForm\`n\ = \ 1\)]], ", is is not hard to generalize the argument. Thus, we are given \ LOOP-computable functions ", Cell[BoxData[ \(TraditionalForm\`g\ : \ \[DoubleStruckCapitalN]\ \[LongRightArrow]\ \ \[DoubleStruckCapitalN]\)]], " and ", Cell[BoxData[ \(TraditionalForm\`h\ : \ \(\(\[DoubleStruckCapitalN]\^3\ \ \[LongRightArrow]\ \[DoubleStruckCapitalN]\)\(\ \)\)\)]], ". Let us say ", Cell[BoxData[ \(TraditionalForm\`P\_g\)]], " is a LOOP-program that computes ", Cell[BoxData[ \(TraditionalForm\`\(\(g\)\(\ \)\)\)]], " via ", Cell[BoxData[ \(TraditionalForm\`x\_1\)]], "and ", Cell[BoxData[ \(TraditionalForm\`y\_1\)]], ", and uses internal variables ", Cell[BoxData[ \(TraditionalForm\`z\_1, \[Ellipsis], z\_k\)]], ". Likewise, ", Cell[BoxData[ \(TraditionalForm\`P\_h\)]], "computes ", Cell[BoxData[ \(TraditionalForm\`h\)]], " via ", Cell[BoxData[ \(TraditionalForm\`x\_2, \ x\_3, \ x\_4\)]], " and ", Cell[BoxData[ \(TraditionalForm\`y\_2\)]], ", using internal variables ", Cell[BoxData[ \(TraditionalForm\`z\_1\%\[Prime], \ \[Ellipsis], z\_l\%\[Prime]\)]], ". We may safely assume that all these variables are distinct (rename \ otherwise), and we may also assume that the input variables do not change \ their values during the execution of the program. Now consider the program" }], "Text"], Cell[TextData[{ "\n\t", Cell[BoxData[ \(TraditionalForm\`P\_g\)]], "\n\t", Cell[BoxData[ \(TraditionalForm\`\(x\_2 = \ 0;\)\)]], "\n\t", Cell[BoxData[ \(TraditionalForm\`\(\(x\_3 = y\_1;\)\(\ \)\)\)]], "\n\t", Cell[BoxData[ \(TraditionalForm\`\(x\_4 = \ x\_1;\)\)]], "\n\t", Cell[BoxData[ \(TraditionalForm\`\(x\_1\ = \ y\_2;\)\)]], "\n\tdo z : \n\t\t", Cell[BoxData[ \(TraditionalForm\`P\_h\)]], "\n\t\t", Cell[BoxData[ \(TraditionalForm\`\(\(x\_2++\);\)\)]], "\n\t\t", Cell[BoxData[ \(TraditionalForm\`\(x\_3 = \ y\_2;\)\)]], "\n\tod" }], "InlineInput"], Cell[TextData[{ "This program computes ", Cell[BoxData[ \(TraditionalForm\`f\)]], " via ", Cell[BoxData[ \(TraditionalForm\`z, x\_1\)]], " and ", Cell[BoxData[ \(TraditionalForm\`y\_2\)]], ". Proof is by induction on ", Cell[BoxData[ \(TraditionalForm\`z\)]], ".\n\[EmptySquare]" }], "Text"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[" Characterizations", "Subsection", CellTags->"c:22"], Cell["\<\ Are there ways to describe LOOP-computable functions other than in \ terms of LOOP-programs? For general LOOP-computable functions the answer is \ relatively easy, thanks to the strong closure propeties discussed in the last \ section. \ \>", "Text"], Cell[CellGroupData[{ Cell["LOOP-Programs", "Subsubsection", CellTags->"c:23"], Cell[TextData[{ "\n", StyleBox["Theorem", FontWeight->"Bold"], ": A function is LOOP-computable iff it is primitive recursive.\nProof.\n\ \[EmptySquare]" }], "Text"] }, Closed]], Cell[CellGroupData[{ Cell[TextData[{ Cell[BoxData[ \(TraditionalForm\`\[ScriptCapitalL]\_0\)]], "-Programs" }], "Subsubsection", CellTags->"c:24"], Cell[TextData[{ "In the absence of any loops, we are left with assignments, setting \ variables to 0, and using the increment operator. Clearly, the functions that \ can be computed in this limited environment are very primitive. For the sake \ of simplicity, we consider only scalar functions. \n\n", StyleBox["Theorem", FontWeight->"Bold"], ": A function ", Cell[BoxData[ \(TraditionalForm\`f\ : \ \[DoubleStruckCapitalN]\^k\[LongRightArrow]\ \ \[DoubleStruckCapitalN]\)]], " is ", Cell[BoxData[ \(TraditionalForm\`\[ScriptCapitalL]\_0\)]], "-computable iff it is constant or of the form ", Cell[BoxData[ FormBox[ RowBox[{ RowBox[{"f", "(", StyleBox["x", FontWeight->"Bold"], ")"}], " ", "=", " ", \(x\_i\ + \ c\)}], TraditionalForm]]], " where ", Cell[BoxData[ \(TraditionalForm\`c\)]], " is constant.\nProof.\nIt is clear that constants and functions of the \ form ", Cell[BoxData[ \(TraditionalForm\`f(x)\ = \ x\_i\ + \ c\)]], " are ", Cell[BoxData[ \(TraditionalForm\`\[ScriptCapitalL]\_0\)]], "-computable. \nFor the opposite direction, we proceed by induction on the \ length of the program. Since we do not allow undefined output variables, the \ smallest possible program is one assignment of the form ", Cell[BoxData[ \(TraditionalForm\`\(\(X\ = \ 0;\)\(\ \)\)\)]], ", and it computes the constant 0 function. Now consider a program ", Cell[BoxData[ \(TraditionalForm\`P\)]], " of the form ", Cell[BoxData[ \(TraditionalForm\`Q\ S\)]], " where ", Cell[BoxData[ \(TraditionalForm\`\(\(Q\)\(\ \)\)\)]], " is a program, and ", Cell[BoxData[ \(TraditionalForm\`S\)]], " the last statement. ", Cell[BoxData[ \(TraditionalForm\`P\)]], " computes the same function as ", Cell[BoxData[ \(TraditionalForm\`Q\)]], " unless the last statement is of the form ", Cell[BoxData[ \(TraditionalForm\`\(X\ = \ exp;\)\)]], " or ", Cell[BoxData[ \(TraditionalForm\`\(\(\ \)\(\(X++\);\)\)\)]], " where ", Cell[BoxData[ \(TraditionalForm\`X\)]], " is the output variable. The case ", Cell[BoxData[ \(TraditionalForm\`\(X\ = \ 0;\)\)]], " is obvious, so suppose ", Cell[BoxData[ \(TraditionalForm\`\(X\ = \ Y;\)\)]], " is the last statement. Consider the function ", Cell[BoxData[ \(TraditionalForm\`g\)]], " computed by ", Cell[BoxData[ \(TraditionalForm\`Q\)]], " with output variable ", Cell[BoxData[ \(TraditionalForm\`Y\)]], ". Then ", Cell[BoxData[ \(TraditionalForm\`f\ = \ g\)]], ", and our claim follows. On the other hand, if ", Cell[BoxData[ \(TraditionalForm\`\(\(X++\);\)\)]], " is the last statment, consider the function computed by ", Cell[BoxData[ \(TraditionalForm\`Q\)]], " with output variable ", Cell[BoxData[ \(TraditionalForm\`X\)]], ". Then ", Cell[BoxData[ FormBox[ RowBox[{ RowBox[{"f", "(", StyleBox["x", FontWeight->"Bold"], ")"}], " ", "=", " ", RowBox[{ RowBox[{"g", "(", StyleBox["x", FontWeight->"Bold"], ")"}], " ", "+", " ", "1"}]}], TraditionalForm]]], ", and we are done. \n\[EmptySquare]" }], "Text"] }, Closed]], Cell[CellGroupData[{ Cell[TextData[{ Cell[BoxData[ \(TraditionalForm\`\[ScriptCapitalL]\_1\)]], "-Programs" }], "Subsubsection", CellTags->"c:25"], Cell[TextData[{ "Unnested loops already add quite a bit of computational power to our \ programs, but we can still get a complete picture. The following example \ shows that integer quotient by 3, ", Cell[BoxData[ \(TraditionalForm\`f\ : \ \[DoubleStruckCapitalN]\ \[LongRightArrow]\ \ \[DoubleStruckCapitalN]\)]], ", ", Cell[BoxData[ \(TraditionalForm\`f(x)\ = \ x\ div\ 3\)]], ", is ", Cell[BoxData[ \(TraditionalForm\`\[ScriptCapitalL]\_1\)]], "-computable. The code is given in ", StyleBox["Mathematica", FontSlant->"Italic"], ", make sure you understand how the corresponding LOOP-program works. " }], "Text"], Cell[BoxData[{ \(Clear[quot, n, q, x0, x1, x2]\), "\n", \(quot[n_]\ := \ \n\((\ x0\ = \ \ \(x1\ = \ \(x2\ = \ 0\)\); \n\ \ \ Do[\ \ \ \n\t\ \ \ \ t = x0; \ x0 = x2; \ x2 = x1; \ x1 = t; \ \n\t\t\ \ \(x0++\), \n\t{n}\ ]; \n\t x2)\)\)}], "Input"], Cell[BoxData[ \(quot\ /@ \ Range[0, 10]\)], "Input"], Cell[TextData[{ "A function is ", StyleBox["simple", FontColor->RGBColor[0, 0, 1]], " iff it can be obtained from the basic functions plus the following \ functions using only composition:\n\t\[Bullet] addition and predecessor,\n\t\ \[Bullet] quotient and remainder with respect to a constant ", Cell[BoxData[ \(TraditionalForm\`c\)]], ",\n\t\[Bullet] ", Cell[BoxData[ \(TraditionalForm\`ite(x, u, v)\ = \ if\ x\ then\ u\ else\ v\)]], ".\nThus, the function ", Cell[BoxData[ \(TraditionalForm\`\((x\ + \ y)\)\ mod\ 5\)]], " is simple, but ", Cell[BoxData[ \(TraditionalForm\`x\ mod\ y\)]], " is not. " }], "Text"], Cell[TextData[{ "We leave it as an exercise to check that all the functions listed are ", Cell[BoxData[ \(TraditionalForm\`\[ScriptCapitalL]\_1\)]], "-computable. The quotient example given above is more or less the harde \ ones. Surprisingly, simple functions is all we get from unnested loops. \n\n\ ", StyleBox["Theorem", FontWeight->"Bold"], ": A function is ", Cell[BoxData[ \(TraditionalForm\`\[ScriptCapitalL]\_1\)]], "-computable iff it is simple.\n\nAnother very interesting property of \ ", Cell[BoxData[ \(TraditionalForm\`\[ScriptCapitalL]\_1\)]], "-computable functions is that one can decide whether they are equal. In \ other words, given two ", Cell[BoxData[ \(TraditionalForm\`\[ScriptCapitalL]\_1\)]], "-programs ", Cell[BoxData[ \(TraditionalForm\`P\_1\)]], " and ", Cell[BoxData[ \(TraditionalForm\`P\_2\)]], ", and input/output variables, one can test whether they compute the same \ functions. Unfortunately, this is an example of a so-called NP-hard problem, \ a problem that does not seem to have solutions that take less than \ exponentially many steps, and so are not practically solvable. " }], "Text"] }, Closed]], Cell[CellGroupData[{ Cell[TextData[{ Cell[BoxData[ \(TraditionalForm\`\[ScriptCapitalL]\_2\)]], "-Programs" }], "Subsubsection", CellTags->"c:26"], Cell[TextData[{ "One can push things a little bit further, and give an elegant description \ of ", Cell[BoxData[ \(TraditionalForm\`\[ScriptCapitalL]\_2\)]], "-computable functions. However, it takes quite a bit more effort this time \ to find the right set of starting functions, since ", Cell[BoxData[ \(TraditionalForm\`\[ScriptCapitalL]\_2\)]], "-computable functions turn out to be a whole lot more powerfule than one \ might suspect. " }], "Text"], Cell[TextData[{ "For example, it is obvious that multiplication is ", Cell[BoxData[ \(TraditionalForm\`\[ScriptCapitalL]\_2\)]], ". But it is conceivable the exponentiation requires another loop, and so \ might be ", Cell[BoxData[ \(TraditionalForm\`\[ScriptCapitalL]\_3\)]], " but not ", Cell[BoxData[ \(TraditionalForm\`\[ScriptCapitalL]\_2\)]], ". The the following program shows that ", Cell[BoxData[ \(TraditionalForm\`f(x)\ = \ 2\^x\)]], " is in fact ", Cell[BoxData[ \(TraditionalForm\`\[ScriptCapitalL]\_2\)]], "-computable." }], "Text"], Cell["\<\ \tz = 1; \tdo x: \t\ty = z; \t\tdo z: y++; od \t\tz = y; \tod \t\ \>", "InlineInput"], Cell["Let's make sure this really works properly. ", "Text"], Cell[BoxData[{ \(\(x\ = \ 5;\)\), "\n", \(\(z\ = \ 1;\)\), "\n", \(\(Do[\ y = z; \ \n\t\t\t\tDo[\ \(y++\), \ {z}]; \n\t\ \ \ \ \ z\ = \ y, \n\t{x}];\)\), "\n", \(z\)}], "Input"], Cell[TextData[{ "But then even ", Cell[BoxData[ \(TraditionalForm\`g(x)\ = \ 2\^\(2\^x\)\)]], " is ", Cell[BoxData[ \(TraditionalForm\`\[ScriptCapitalL]\_2\)]], "-computable. In pseudo-code, the program looks like this:" }], "Text"], Cell["\<\ \tz1 = f(x); \tz2 = 1; \tdo z1: \t\ty = z; \t\tdo z: y++; od \t\tz = y; \tod \t\ \>", "InlineInput"], Cell[TextData[{ "And this is just the tip of an iceberg: by virtually the same argument, ", Cell[BoxData[ \(TraditionalForm\`2\^\(g(x)\)\)]], " is ", Cell[BoxData[ \(TraditionalForm\`\[ScriptCapitalL]\_2\)]], "-computable, ", Cell[BoxData[ \(TraditionalForm\`2\^\(2\^\(g(x)\)\)\)]], "is ", Cell[BoxData[ \(TraditionalForm\`\[ScriptCapitalL]\_2\)]], "-computable, and so forth. In fact, all the functions \n\n\t", Cell[BoxData[ \(TraditionalForm\`f(x)\ = \ 2\^\(2\^\(\[AscendingEllipsis]\^\(2\^x\)\)\)\)]], " \n\t\nwhere the stack of 2's is arbitrarily high, are ", Cell[BoxData[ \(TraditionalForm\`\[ScriptCapitalL]\_2\)]], "-computable. " }], "Text"], Cell[TextData[{ "Here is a class of functions sufficiently general to capture doubly nested \ loops. A function is ", StyleBox["elementary", FontColor->RGBColor[0, 0, 1]], " iff it can be obtained from the basic functions plus the following \ functions using only composition:\n\t\[Bullet] addition and proper \ subtraction,\n\t\[Bullet] multiplication and quotient,\n\t\[Bullet] \ summation ", Cell[BoxData[ \(TraditionalForm\`\[Sum]\_x\)]], " and products ", Cell[BoxData[ \(TraditionalForm\`\[Product]\_x\)]], ".\nBy summation we mean functions of the form ", Cell[BoxData[ \(TraditionalForm\`f(x, y)\ = \ \[Sum]\_\(z < x\)\ g(z, y)\)]], " where ", Cell[BoxData[ \(TraditionalForm\`g\)]], " is a given function, and likewise for products. The surprising result is \ that " }], "Text"], Cell[TextData[{ StyleBox["Theorem", FontWeight->"Bold"], ": A function is ", Cell[BoxData[ \(TraditionalForm\`\[ScriptCapitalL]\_2\)]], "-computable iff it is elementary." }], "Text"], Cell[TextData[{ "Again, this sounds extremely implausible. Suppose we have a function ", Cell[BoxData[ \(TraditionalForm\`g(x)\)]], " that is ", Cell[BoxData[ \(TraditionalForm\`\[ScriptCapitalL]\_2\)]], "-computable but not ", Cell[BoxData[ \(TraditionalForm\`\[ScriptCapitalL]\_1\)]], "-computable (such functions exist, though we have not proven this). Then, \ the function ", Cell[BoxData[ \(TraditionalForm\`f(x)\ = \ \[Sum]\_\(z < x\)\ g(z)\)]], " is again ", Cell[BoxData[ \(TraditionalForm\`\[ScriptCapitalL]\_2\)]], "-computable, but the obvious LOOP-program for it has 3 nested loops, \ rather than the permitted 2. It is absolutely not clear how to reduce the \ nesting depth. The proof requires a clever trick of simulating deeply nested \ programs by ", Cell[BoxData[ \(TraditionalForm\`\[ScriptCapitalL]\_2\)]], "-programs. " }], "Text"], Cell["\<\ Just about any practical number theoretic function is elementary, \ and if we code standard data structures as integers, all the usual algorithms \ on these data structures translate into elementary functions. In fact, there \ are elementary functions that grow much too rapidly to be of much practical \ value. \ \>", "Text"], Cell[TextData[{ "\nWe state without proof yet another rather remarkable theorem.\n", StyleBox["Theorem", FontWeight->"Bold"], ": It is undecidable whether two ", Cell[BoxData[ \(TraditionalForm\`\[ScriptCapitalL]\_2\)]], "-programs compute the same function.\n\nIn other words, there is no \ program that takes as input two ", Cell[BoxData[ \(TraditionalForm\`\[ScriptCapitalL]\_2\)]], "-programs, and a list of their input/output variables, and determines \ whether the programs compute the same function." }], "Text"] }, Closed]] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell["Iteration", "Section", CellTags->"c:27"], Cell[TextData[{ "Iteration is another standard way to construct complicated functions. For \ iteration, it is best to consider vector valued functions ", Cell[BoxData[ \(TraditionalForm\`f\ : \ \[DoubleStruckCapitalN]\^k\ \ \[LongRightArrow]\ \[DoubleStruckCapitalN]\^k\)]], ":\n\t", Cell[BoxData[ \(TraditionalForm\`f\^\(\(0\)\(\ \)\) = \ id\)]], ", and ", Cell[BoxData[ \(TraditionalForm\`f\^\(n + 1\)\ = \ f\[SmallCircle]f\^n\)]], ". \nFor our purposes, we can collect all these iterates of ", Cell[BoxData[ \(TraditionalForm\`f\)]], " into one function\n\t", Cell[BoxData[ \(TraditionalForm\`\(f\^*\)\ : \ \[DoubleStruckCapitalN]\^\(k + 1\)\ \[LongRightArrow]\ \[DoubleStruckCapitalN]\)]], " defined by ", Cell[BoxData[ FormBox[ RowBox[{ RowBox[{\(f\^*\), "(", RowBox[{"n", ",", StyleBox["x", FontWeight->"Bold"]}], ")"}], " ", "=", " ", RowBox[{\(f\^n\), "(", StyleBox["x", FontWeight->"Bold"], ")"}]}], TraditionalForm]]], ".\ncorresponding to the ", StyleBox["Nest", "SmallText"], " operation in ", StyleBox["Mathematica ", FontSlant->"Italic"], "(though ", StyleBox["Nest", "SmallText"], " accomodates only the scalar case ", Cell[BoxData[ \(TraditionalForm\`k = 1\)]], ").\n\nFor example, ", Cell[BoxData[ \(TraditionalForm\`\(S\^*\)(a, b)\ = \ a\ + \ b\)]], " where ", Cell[BoxData[ \(TraditionalForm\`\(\(S\)\(\ \)\)\)]], " is the successor function. Likewise, ", Cell[BoxData[ \(TraditionalForm\`\(\(\(A\^*\)(a, b, 0)\)\(\ \)\(=\)\((b, a\ b)\)\(\ \)\)\)]], " if we let ", Cell[BoxData[ \(TraditionalForm\`A(x, y)\ = \ \((x, x + y)\)\)]], ". Hence, we can express addition and multiplication in terms of \ iteration. " }], "Text"], Cell[CellGroupData[{ Cell["Iteration and Primitive Recursion", "Subsection", CellTags->"c:28"], Cell["\<\ Intuitivel, there is a connection between iteration and recursion, \ since in both cases the same function is applied repeatedly. We now show that \ iteration and primitive recursion are in fact in some sense equivalent. \ \ \>", "Text"], Cell[TextData[{ StyleBox["Theorem", FontWeight->"Bold"], ": Iteration can be expressed in terms of primitive recursion.\nProof.\nWe \ will only deal with the scalar case. So suppose we have a function ", Cell[BoxData[ \(TraditionalForm\`f\ : \ \[DoubleStruckCapitalN]\ \[LongRightArrow]\ \ \[DoubleStruckCapitalN]\)]], " and its iterate ", Cell[BoxData[ \(TraditionalForm\`\(\(\ \)\(\(f\^*\)\ : \ \[DoubleStruckCapitalN]\ \ \[Cross]\ \[DoubleStruckCapitalN]\[LongRightArrow]\ \[DoubleStruckCapitalN]\)\ \)\)]], ". Note that \n\t", Cell[BoxData[ FormBox[GridBox[{ {\(\(f\^*\)(0, x)\), "=", "x"}, {\(\(f\^*\)(n + 1, x)\), "=", \(f(\(f\^*\)(n, x))\)} }], TraditionalForm]]], "\nwhich amounts to a primitive recursive definition of ", Cell[BoxData[ \(TraditionalForm\`\(f\^*\)\)]], " in terms of ", Cell[BoxData[ \(TraditionalForm\`f\)]], ". More formally, ", Cell[BoxData[ \(TraditionalForm\`f\ = \ PrimRec(g, h)\)]], " where ", Cell[BoxData[ \(TraditionalForm\`g(x)\ = x\)]], " and ", Cell[BoxData[ \(TraditionalForm\`h(n, z, x)\ = \ f(z)\)]], ". \n\[EmptySquare]" }], "Text"], Cell[TextData[{ StyleBox["Theorem", FontWeight->"Bold"], ": Primitive recursion can be expressed in terms of iteration.\nProof.\n\ Suppose we have ", Cell[BoxData[ \(TraditionalForm\`g\ : \ \(\(\[DoubleStruckCapitalN]\)\(\ \)\)\^n\ \[LongRightArrow]\ \[DoubleStruckCapitalN]\)]], " and ", Cell[BoxData[ \(TraditionalForm\`h\ : \ \[DoubleStruckCapitalN]\^\(n + 2\)\ \ \[LongRightArrow]\ \[DoubleStruckCapitalN]\)]], ", and let \n\t", Cell[BoxData[ FormBox[ RowBox[{" ", RowBox[{ RowBox[{"f", "(", RowBox[{"0", ",", StyleBox["x", FontWeight->"Bold"]}], ")"}], " ", "=", " ", RowBox[{"g", "(", StyleBox["x", FontWeight->"Bold"], ")"}]}]}], TraditionalForm]]], ", and \n\t", Cell[BoxData[ FormBox[ RowBox[{ RowBox[{"f", "(", RowBox[{\(n + 1\), ",", StyleBox["x", FontWeight->"Bold"]}], ")"}], " ", "=", " ", RowBox[{"h", "(", " ", RowBox[{"n", ",", " ", RowBox[{"f", "(", RowBox[{"n", ",", StyleBox["x", FontWeight->"Bold"]}], ")"}], ",", " ", StyleBox["x", FontWeight->"Bold"]}], " ", ")"}]}], TraditionalForm]]], ".\nDefine a vector function ", Cell[BoxData[ \(TraditionalForm\`F\ : \ \[DoubleStruckCapitalN]\^\(n + 2\)\ \ \[LongRightArrow]\ \[DoubleStruckCapitalN]\^\(n + 2\)\)]], " by \n\t", Cell[BoxData[ FormBox[ RowBox[{\(F(n, z, x)\), " ", "=", " ", RowBox[{"(", RowBox[{\(x + 1\), ",", RowBox[{"h", "(", RowBox[{"n", ",", "z", ",", StyleBox["x", FontWeight->"Bold"]}], ")"}], ",", StyleBox[" ", FontWeight->"Bold"], StyleBox["x", FontWeight->"Bold"]}], ")"}]}], TraditionalForm]]], ".\nThen ", Cell[BoxData[ FormBox[ RowBox[{ RowBox[{"f", "(", RowBox[{"n", ",", StyleBox["x", FontWeight->"Bold"]}], ")"}], " ", "=", " ", RowBox[{\(\[Pi]\_2\%3\), "(", " ", RowBox[{\(F\^*\), "(", RowBox[{"n", ",", "0", ",", RowBox[{"g", "(", StyleBox["x", FontWeight->"Bold"], ")"}], ",", StyleBox["x", FontWeight->"Bold"]}], ")"}], ")"}]}], TraditionalForm]]], ". \nProof by induction on ", Cell[BoxData[ \(TraditionalForm\`n\)]], " that: ", Cell[BoxData[ FormBox[ RowBox[{" ", RowBox[{ RowBox[{\(F\^*\), "(", RowBox[{"n", ",", "0", ",", RowBox[{"g", "(", StyleBox["x", FontWeight->"Bold"], ")"}], ",", StyleBox["x", FontWeight->"Bold"]}], ")"}], " ", "=", " ", \((n, f(n, x), x)\)}]}], TraditionalForm]]], ".\n\[EmptySquare]\n\nLet us implement the simulation from the last \ theorem." }], "Text"], Cell[BoxData[{ \(Clear[F, n, z, x, g, h]\), "\n", \(\(F[{n_, z_, x_}]\ := \ {n + 1, h[n, z, x], x};\)\)}], "Input"], Cell[BoxData[ \(Nest[F, {0, g[x], x}, \ 3]\ // \ TableForm\)], "Input"], Cell["\<\ Here is multiplication expressed in terms of iteration and \ addition.\ \>", "Text"], Cell[BoxData[{ \(\(g[x_]\ := \ 0;\)\), "\n", \(\(h[n_, z_, x_]\ := \ z\ + \ x;\)\)}], "Input"], Cell[BoxData[ \(Nest[F, {0, g[x], x}, \ 5]\)], "Input"] }, Closed]], Cell[CellGroupData[{ Cell[" Rapidly Growing Functions", "Subsection", CellTags->"c:29"], Cell[TextData[{ "Iteration is a favorite tool in theory to produce rapidly growing \ functions. Here is one sequence of functions that grows very quickly.\n\t\n\t\ ", Cell[BoxData[ FormBox[GridBox[{ {\(\(f\_0\)(x)\), "=", \(\(\ \)\(x\ + \ 1\)\)}, {\(\(\(f\_\(n + 1\)\)(x)\)\(\ \)\), "=", \(\(f\_n\%x\)(1)\)} }], TraditionalForm]]], "\n\t\nThus, ", Cell[BoxData[ \(TraditionalForm\`\(f\_1\)(x)\ = \ 2 x\ + \ 1\)]], ", ", Cell[BoxData[ \(TraditionalForm\`\(f\_3\)(x)\ = \ 2\^\(x + 1\) - \ 1\)]], ", and so forth.\n" }], "Text"], Cell[BoxData[{ \(Clear[ff]\), "\n", \(\(ff[0, x_]\ := \ x + 2;\)\), "\n", \(\(ff[n_, x_]\ := \ \(ff[n, x]\ = \ Nest[\ ff[n - 1, #] &, \ 1, \ x\ ]\);\)\)}], "InputOnly"], Cell["Needless to say, we cannot compute large values.", "Text"], Cell[BoxData[ \({\(ff[0, #] &\)\ /@ \ Range[0, 8], \n\(ff[1, #] &\)\ /@ \ Range[0, 8], \n\(ff[2, #] &\)\ /@ \ Range[0, 8], \n\(ff[3, #] &\)\ /@ \ Range[0, 3]}\ // \ TableForm\)], "Input"], Cell[TextData[{ "Note that ", Cell[BoxData[ \(TraditionalForm\`\(f\_3\)(4)\)]], " is already too large for our system. " }], "Text"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell["The Ackermann Function", "Section", CellTags->"c:30"], Cell["\<\ As we have seen, primitive recursion, iteration, and loops are in \ some sense equivalent in their computational strength. One might wonder at \ this point if there are any computable functions (in the intuitive sense, \ say, computable by a C program) that fail to be, say, primitive recursive. \ There is a rather famous example of one such function, the so-called \ Ackermann function. It is clearly computable in an intuitive sense, and one \ can show that it cannot be written as a primitive recursive function. \ Equivalently, there is no LOOP-program that computes this function, nor can \ it be computed using iteration. \ \>", "Text"], Cell[CellGroupData[{ Cell["The Ackermann Function", "Subsection", CellTags->"c:31"], Cell["\<\ The key idea behind Ackermann's counterexample to the suggestion \ that computable is the same as primitive recursive is to construct a function \ that grows more rapidly than any primitive recursive function, very much like \ the sequence of functions obtained by repeated iteration in the last section. \ Since there is a natural hierarchy of primitive recursive functions it is \ not too difficicult to accomplish this: as the arguments grow larger, the \ Ackermann function out-grows primitive recursive functions of greater and \ greater depth. Of course, we have to make sure that the whole function still \ is computable.\ \>", "Text"], Cell[TextData[{ "The Ackermann function is of the form ", Cell[BoxData[ \(TraditionalForm\`A\ : \ \[DoubleStruckCapitalN]\ \[Cross]\ \ \[DoubleStruckCapitalN]\ \[LongRightArrow]\ \[DoubleStruckCapitalN]\)]], " and is defined by the following equations:\n\n\t", Cell[BoxData[ FormBox[GridBox[{ {\(\(A(0, y)\)\(\ \)\), "=", \(y + 1\)}, {\(A(x + 1, 0)\), "=", \(A(x, 1)\)}, {\(A(x + 1, y + 1)\), "=", \(A(\ x, \ A(x + 1, y))\)} }], TraditionalForm]]], "\n\t\nNote the double recursion in the last case, a priori this does not \ fit into the framework of primitive recursion, though, of course, there might \ be some clever way to rephrase the definition. \nIt is helpful to think of ", Cell[BoxData[ \(TraditionalForm\`A\)]], " as a family of functions defined by ", Cell[BoxData[ \(TraditionalForm\`\(A\_x\)(y)\ = \ A(x, y)\)]], ". Then \n\t\n\t", Cell[BoxData[ FormBox[GridBox[{ {\(\(A\_0\)(y)\), "=", \(y + 1\)}, {\(\(A\_1\)(y)\), "=", \(y + 2\)}, {\(\(A\_2\)(y)\), "=", \(2 y + 3\)}, {\(\(A\_3\)(y)\), "=", \(2\^\(y + 3\) - \ 3\)}, {\(\(A\_4\)(x)\), "\[TildeTilde]", \(2\^\(2\^\(\[AscendingEllipsis]\^2\)\)\)} }], TraditionalForm]]], "\n\t\nwhich indicates that ", Cell[BoxData[ \(TraditionalForm\`A\_x\)]], " grows more and more rapidly as ", Cell[BoxData[ \(TraditionalForm\`x\)]], " increases. ", Cell[BoxData[ \(TraditionalForm\`A\_4\)]], " already corresponds to some form of super-exponentiation, there are some \ ", Cell[BoxData[ \(TraditionalForm\`\(\(y\)\(-\)\)\)]], "many 2's in the stack of exponents, and ", Cell[BoxData[ \(TraditionalForm\`A\_5\)]], " grows much too fast to be of any practical importance. " }], "Text"], Cell[CellGroupData[{ Cell["Ackermann Code", "Subsubsection", CellTags->"c:32"], Cell["\<\ This is a verbatim implementation of the equations from \ above.\ \>", "Text"], Cell[BoxData[{\(ClearAll[A]\), "\[IndentingNewLine]", RowBox[{ RowBox[{\(A[0, y_]\), " ", ":=", " ", StyleBox[\(y + 1\), FontColor->RGBColor[0, 0, 1]]}], StyleBox[";", FontColor->RGBColor[0, 0, 1]]}], "\[IndentingNewLine]", RowBox[{ RowBox[{\(A[x_, 0]\), " ", ":=", " ", RowBox[{\(A[x, 0]\), "=", StyleBox[" ", FontColor->RGBColor[0, 0, 1]], StyleBox[\(A[x - 1, 1]\), FontColor->RGBColor[0, 0, 1]]}]}], StyleBox[";", FontColor->RGBColor[0, 0, 1]]}], "\[IndentingNewLine]", RowBox[{ RowBox[{\(A[x_, y_]\), " ", ":=", " ", RowBox[{\(A[x, y]\), "=", StyleBox[" ", FontColor->RGBColor[0, 0, 1]], StyleBox[\(A[x - 1, A[x, y - 1]]\), FontColor->RGBColor[0, 0, 1]]}]}], ";"}]}], "Input"], Cell[BoxData[ \(Table[\ A[i, j], \ {i, 0, 3}, \ {j, 0, 5}\ ]\ // \ TableForm\)], "Input"], Cell[BoxData[ \(?? A\)], "Input"] }, Closed]], Cell[CellGroupData[{ Cell["Level 4", "Subsubsection", CellTags->"c:33"], Cell["Things start to become very tedious at level 4.", "Text"], Cell[BoxData[ \(A[4, 0]\)], "Input"], Cell[BoxData[ \(A[4, 1]\)], "Input"], Cell[BoxData[ \(\($RecursionLimit\ = \ 10000;\)\)], "Input"], Cell["\<\ We can still obtain the value for A(4,1) by cheating a bit and \ avoiding calls to the lower levels.\ \>", "Text"], Cell[BoxData[{ \(ClearAll[A]\), "\[IndentingNewLine]", \(\(A[0, y_]\ := \ y + 1;\)\), "\[IndentingNewLine]", \(\(A[1, y_]\ := \ y + 2;\)\), "\[IndentingNewLine]", \(\(A[2, y_]\ := \ 2 y + 3;\)\), "\[IndentingNewLine]", \(\(A[3, y_]\ := \ 2^\((y + 3)\) - 3;\)\), "\[IndentingNewLine]", \(\(A[x_, 0]\ := \ \(A[x, 0] = \ A[x - 1, 1]\);\)\), "\[IndentingNewLine]", \(A[x_, y_]\ := \ \(A[x, y] = \ A[x - 1, A[x, y - 1]]\)\)}], "Input"], Cell[BoxData[ \(Table[\ A[i, j], \ {i, 0, 3}, \ {j, 0, 5}\ ]\ // \ TableForm\)], "Input"], Cell[BoxData[ \(A[4, 1]\)], "Input"], Cell[BoxData[ \(?? A\)], "Input"], Cell[BoxData[ \(\(?*Slide*\)\)], "Input"] }, Closed]], Cell[CellGroupData[{ Cell["Solving", "Subsubsection", CellTags->"c:34"], Cell[BoxData[ \(<< DiscreteMath`RSolve`\)], "Input"], Cell[BoxData[ \(ClearAll[a, n]\)], "Input"], Cell[BoxData[ \(RSolve[\ \ {a[n + 1]\ \[Equal] \ 2\ a[n]\ + \ 3, \ a[0] \[Equal] 5}, \ a[n], \ n\ ]\)], "Input"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[TextData[{ Cell[BoxData[ \(TraditionalForm\`A\)]], " is well-defined, but not PR" }], "Subsection", CellTags->"c:35"], Cell[TextData[{ "Also note that there is the problem of whether these equations do in fact \ define a total function of two arguments. This is certainly not true for \ random systems of equations. For example,\n\n\t", Cell[BoxData[ FormBox[GridBox[{ {\(f(0, 0)\), "=", "0"}, {\(f(x + 1, y)\), "=", \(f(x, y + 1)\)} }], TraditionalForm]]], "\n\t\ndoes not uniquely define ", Cell[BoxData[ \(TraditionalForm\`f\)]], ", in fact, any function of the form ", Cell[BoxData[ \(TraditionalForm\`f(x, y)\ = \ g(x + y)\)]], " is a solution as long as ", Cell[BoxData[ \(TraditionalForm\`g(0)\ = \ 0\)]], ". On the other hand, \n\n\t", Cell[BoxData[ FormBox[GridBox[{ {\(g(x, 0)\), "=", \(x + 1\)}, {\(g(x, y + 1)\), "=", \(g(x + 1, y)\)}, {\(g(x + 1, y + 1)\), "=", \(g(x, g(x, y))\)} }], TraditionalForm]]], "\n\t\nhas no solution at all. For ", Cell[BoxData[ \(TraditionalForm\`g(1, 1)\ = \ \(g(2, 0)\ = \ 3\)\)]], ", but at the same time ", Cell[BoxData[ \(TraditionalForm\`g(1, 1)\ = \ \(g(0, g(0, 0))\ = \ \(g(0, 1)\ = \ \(g(1, 0)\ = \ 2\)\)\)\)]], ". Note that the second system of equations looks uncomfortably similar to \ the Ackermann system. " }], "Text"], Cell[TextData[{ "\n", StyleBox["Theorem", FontWeight->"Bold"], ": The Ackermann function is well-defined on \[DoubleStruckCapitalN] \ \[Cross] \[DoubleStruckCapitalN].\nProof. \nIn order to see that ", Cell[BoxData[ \(TraditionalForm\`A\)]], " is indeed well-defined, consider the usual product order on ", Cell[BoxData[ \(TraditionalForm\`\[DoubleStruckCapitalN]\ \[Cross]\ \ \[DoubleStruckCapitalN]\)]], ": ", Cell[BoxData[ \(TraditionalForm\`\((x, y)\)\ \[Precedes] \ \((x\^\[Prime], y\^\[Prime])\)\ \ \ iff\ \ \ x\ < \ \(x\^\[Prime]\) or\ \ \((\ x\ = \ x\^\[Prime]\ and\ \ y\ < \ y\^\[Prime])\)\)]], ". It is not hard to see that ", Cell[BoxData[ \(TraditionalForm\` \[Precedes] \)]], " is a well-ordering. Now consider the equations for ", Cell[BoxData[ \(TraditionalForm\`A\)]], " as the definition of a recursive function. We have to show that for any \ value of ", Cell[BoxData[ \(TraditionalForm\`a\)]], " and ", Cell[BoxData[ \(TraditionalForm\`b\)]], " the recursion in the call ", Cell[BoxData[ \(TraditionalForm\`A(a, b)\)]], " terminates. Let us only consider equations 3. First, there is a call to \ ", Cell[BoxData[ \(TraditionalForm\`A(a, b - 1)\)]], ". Since ", Cell[BoxData[ \(TraditionalForm\`\((a, b - 1)\)\)]], " precedes ", Cell[BoxData[ \(TraditionalForm\`\((a, b)\)\)]], ", we may assume that this call terminates, returning some value ", Cell[BoxData[ \(TraditionalForm\`c\)]], ". But then the next call is of the form ", Cell[BoxData[ \(TraditionalForm\`A(\ a - 1, c)\)]], " which must also terminate since ", Cell[BoxData[ \(TraditionalForm\`\((a - 1, c)\)\ \[Precedes] \ \((a, c)\)\)]], ", regardless of the value of ", Cell[BoxData[ \(TraditionalForm\`c\)]], ". \n\[EmptySquare]" }], "Text"], Cell["\<\ It is tempting to compute a few values of the function. Note, \ though, that the result become catastrophically large even for relatively \ small inputs, so one should not expect to get too much mileage out of the \ implementation. We memoize to achieve some minor speedup. \ \>", "Text"], Cell["\<\ ClearAll[A] A[ 0, y_Integer ] := A[0, y] = y + 1; A[ x_Integer, 0 ] := A[x, 0] = A[x - 1, 1]; A[ x_Integer, y_Integer ] := \t\tA[x,y] = A[x-1, A[x, y-1]];\ \>", "Input", AspectRatioFixed->True], Cell["A[ 2, 2 ]", "Input", AspectRatioFixed->True], Cell["??A", "Input", AspectRatioFixed->True], Cell["We state the crucial theorem without proof.", "Text"], Cell[TextData[{ StyleBox["Theorem", FontWeight->"Bold"], ": For any primitive recursive function ", Cell[BoxData[ \(TraditionalForm\`f\ : \ \[DoubleStruckCapitalN]\ \[LongRightArrow]\ \ \[DoubleStruckCapitalN]\)]], " there exists ", Cell[BoxData[ \(TraditionalForm\`x\ \[GreaterEqual] \ 0, \ y\_0\ \[GreaterEqual] \ 0\)]], " such that ", Cell[BoxData[ \(TraditionalForm\`\[ForAll] y\ > \ \(y\_0\)(\ \ f(y)\ < \ \(A\_x\)( y)\ )\)]], ". " }], "Text"], Cell[TextData[{ StyleBox["Corollary", FontWeight->"Bold"], ": The Ackermann function is not primitive recursive. " }], "Text"] }, Closed]] }, Closed]] }, Open ]] }, FrontEndVersion->"5.0 for X", ScreenRectangle->{{0, 1280}, {0, 1024}}, AutoGeneratedPackage->None, WindowSize->{884, 996}, WindowMargins->{{1, Automatic}, {Automatic, 0}}, PrintingStartingPageNumber->322, PrintingPageRange->{Automatic, Automatic}, PrintingOptions->{"PaperSize"->{612, 792}, "PaperOrientation"->"Portrait", "Magnification"->1}, ShowCellLabel->False, Magnification->1.5, StyleDefinitions -> "Classic.nb" ] (******************************************************************* 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->{ "c:1"->{ Cell[1833, 55, 92, 2, 235, "Title", CellTags->"c:1"]}, "c:2"->{ Cell[1950, 61, 57, 1, 88, "Section", CellTags->"c:2"]}, "c:3"->{ Cell[3827, 98, 56, 1, 42, "Subsection", CellTags->"c:3"]}, "c:4"->{ Cell[5411, 148, 52, 1, 42, "Subsection", CellTags->"c:4"]}, "c:5"->{ Cell[7954, 233, 60, 1, 42, "Subsection", CellTags->"c:5"]}, "c:6"->{ Cell[10207, 302, 61, 1, 42, "Subsection", CellTags->"c:6"]}, "c:7"->{ Cell[14034, 404, 76, 1, 42, "Subsection", CellTags->"c:7"]}, "c:8"->{ Cell[14135, 409, 62, 1, 42, "Subsubsection", CellTags->"c:8"]}, "c:9"->{ Cell[15218, 443, 89, 1, 42, "Subsection", CellTags->"c:9"]}, "c:10"->{ Cell[15921, 462, 97, 3, 42, "Subsubsection", Evaluatable->False, CellTags->"c:10"]}, "c:11"->{ Cell[17125, 524, 116, 3, 42, "Subsubsection", Evaluatable->False, CellTags->"c:11"]}, "c:12"->{ Cell[18651, 604, 52, 1, 47, "Section", CellTags->"c:12"]}, "c:13"->{ Cell[18728, 609, 57, 1, 42, "Subsection", CellTags->"c:13"]}, "c:14"->{ Cell[24939, 822, 54, 1, 42, "Subsection", CellTags->"c:14"]}, "c:15"->{ Cell[26678, 877, 61, 1, 42, "Subsubsection", CellTags->"c:15"]}, "c:16"->{ Cell[27171, 905, 74, 1, 42, "Subsubsection", CellTags->"c:16"]}, "c:17"->{ Cell[28614, 973, 54, 1, 42, "Subsubsection", CellTags->"c:17"]}, "c:18"->{ Cell[29639, 1014, 60, 1, 42, "Subsection", CellTags->"c:18"]}, "c:19"->{ Cell[30623, 1047, 61, 1, 42, "Subsection", CellTags->"c:19"]}, "c:20"->{ Cell[31687, 1069, 56, 1, 42, "Subsubsection", CellTags->"c:20"]}, "c:21"->{ Cell[35159, 1190, 64, 1, 42, "Subsubsection", CellTags->"c:21"]}, "c:22"->{ Cell[40079, 1351, 60, 1, 42, "Subsection", CellTags->"c:22"]}, "c:23"->{ Cell[40427, 1363, 58, 1, 42, "Subsubsection", CellTags->"c:23"]}, "c:24"->{ Cell[40703, 1377, 137, 5, 42, "Subsubsection", CellTags->"c:24"]}, "c:25"->{ Cell[44266, 1493, 137, 5, 42, "Subsubsection", CellTags->"c:25"]}, "c:26"->{ Cell[47349, 1586, 137, 5, 42, "Subsubsection", CellTags->"c:26"]}, "c:27"->{ Cell[53000, 1779, 48, 1, 47, "Section", CellTags->"c:27"]}, "c:28"->{ Cell[54970, 1841, 75, 1, 42, "Subsection", CellTags->"c:28"]}, "c:29"->{ Cell[60243, 2004, 68, 1, 42, "Subsection", CellTags->"c:29"]}, "c:30"->{ Cell[61603, 2050, 61, 1, 47, "Section", CellTags->"c:30"]}, "c:31"->{ Cell[62345, 2067, 64, 1, 42, "Subsection", CellTags->"c:31"]}, "c:32"->{ Cell[64972, 2133, 59, 1, 42, "Subsubsection", CellTags->"c:32"]}, "c:33"->{ Cell[66182, 2175, 52, 1, 42, "Subsubsection", CellTags->"c:33"]}, "c:34"->{ Cell[67339, 2220, 52, 1, 28, "Subsubsection", CellTags->"c:34"]}, "c:35"->{ Cell[67679, 2237, 134, 5, 42, "Subsection", CellTags->"c:35"]} } *) (*CellTagsIndex CellTagsIndex->{ {"c:1", 73323, 2415}, {"c:2", 73399, 2418}, {"c:3", 73476, 2421}, {"c:4", 73556, 2424}, {"c:5", 73637, 2427}, {"c:6", 73718, 2430}, {"c:7", 73800, 2433}, {"c:8", 73882, 2436}, {"c:9", 73967, 2439}, {"c:10", 74050, 2442}, {"c:11", 74163, 2446}, {"c:12", 74277, 2450}, {"c:13", 74358, 2453}, {"c:14", 74442, 2456}, {"c:15", 74526, 2459}, {"c:16", 74613, 2462}, {"c:17", 74700, 2465}, {"c:18", 74787, 2468}, {"c:19", 74872, 2471}, {"c:20", 74957, 2474}, {"c:21", 75045, 2477}, {"c:22", 75133, 2480}, {"c:23", 75218, 2483}, {"c:24", 75306, 2486}, {"c:25", 75395, 2489}, {"c:26", 75484, 2492}, {"c:27", 75573, 2495}, {"c:28", 75655, 2498}, {"c:29", 75740, 2501}, {"c:30", 75825, 2504}, {"c:31", 75907, 2507}, {"c:32", 75992, 2510}, {"c:33", 76080, 2513}, {"c:34", 76168, 2516}, {"c:35", 76256, 2519} } *) (*NotebookFileOutline Notebook[{ Cell[1754, 51, 54, 0, 40, "SmallText"], Cell[CellGroupData[{ Cell[1833, 55, 92, 2, 235, "Title", CellTags->"c:1"], Cell[CellGroupData[{ Cell[1950, 61, 57, 1, 88, "Section", CellTags->"c:2"], Cell[2010, 64, 1792, 30, 468, "Text"], Cell[CellGroupData[{ Cell[3827, 98, 56, 1, 42, "Subsection", CellTags->"c:3"], Cell[3886, 101, 1310, 35, 197, "Text"], Cell[5199, 138, 175, 5, 43, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[5411, 148, 52, 1, 42, "Subsection", CellTags->"c:4"], Cell[5466, 151, 1756, 54, 168, "Text"], Cell[7225, 207, 602, 16, 70, "Text"], Cell[7830, 225, 87, 3, 68, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[7954, 233, 60, 1, 42, "Subsection", CellTags->"c:5"], Cell[8017, 236, 2153, 61, 243, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[10207, 302, 61, 1, 42, "Subsection", CellTags->"c:6"], Cell[10271, 305, 2615, 68, 443, "Text"], Cell[12889, 375, 890, 18, 105, "Text"], Cell[13782, 395, 215, 4, 68, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[14034, 404, 76, 1, 42, "Subsection", CellTags->"c:7"], Cell[CellGroupData[{ Cell[14135, 409, 62, 1, 42, "Subsubsection", CellTags->"c:8"], Cell[14200, 412, 969, 25, 343, "Text"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[15218, 443, 89, 1, 42, "Subsection", CellTags->"c:9"], Cell[15310, 446, 586, 12, 143, "Text"], Cell[CellGroupData[{ Cell[15921, 462, 97, 3, 42, "Subsubsection", Evaluatable->False, CellTags->"c:10"], Cell[16021, 467, 157, 6, 43, "Text", Evaluatable->False], Cell[16181, 475, 157, 5, 70, "Input", InitializationCell->True], Cell[16341, 482, 137, 6, 90, "Input", InitializationCell->True], Cell[16481, 490, 218, 8, 130, "Input", InitializationCell->True], Cell[16702, 500, 324, 16, 290, "Input", InitializationCell->True], Cell[17029, 518, 59, 1, 51, "Input"] }, Closed]], Cell[CellGroupData[{ Cell[17125, 524, 116, 3, 42, "Subsubsection", Evaluatable->False, CellTags->"c:11"], Cell[17244, 529, 73, 2, 43, "Text", Evaluatable->False], Cell[17320, 533, 95, 4, 70, "Input"], Cell[17418, 539, 71, 4, 70, "Input"], Cell[17492, 545, 72, 2, 43, "Text", Evaluatable->False], Cell[17567, 549, 87, 1, 50, "Input"], Cell[17657, 552, 54, 1, 50, "Input"], Cell[17714, 555, 72, 4, 70, "Input"], Cell[17789, 561, 75, 2, 43, "Text", Evaluatable->False], Cell[17867, 565, 49, 0, 50, "Input"], Cell[17919, 567, 26, 0, 50, "Input"], Cell[17948, 569, 26, 0, 50, "Input"], Cell[17977, 571, 65, 0, 50, "Input"], Cell[18045, 573, 30, 0, 50, "Input"], Cell[18078, 575, 30, 0, 50, "Input"], Cell[18111, 577, 52, 0, 50, "Input"], Cell[18166, 579, 28, 0, 50, "Input"], Cell[18197, 581, 28, 0, 50, "Input"], Cell[18228, 583, 78, 2, 43, "Text", Evaluatable->False], Cell[18309, 587, 70, 0, 50, "Input"], Cell[18382, 589, 29, 0, 50, "Input"], Cell[18414, 591, 73, 2, 43, "Text", Evaluatable->False], Cell[18490, 595, 74, 0, 50, "Input"], Cell[18567, 597, 23, 0, 50, "Input"] }, Closed]] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[18651, 604, 52, 1, 47, "Section", CellTags->"c:12"], Cell[CellGroupData[{ Cell[18728, 609, 57, 1, 42, "Subsection", CellTags->"c:13"], Cell[18788, 612, 809, 16, 218, "Text"], Cell[19600, 630, 79, 5, 96, "InlineInput"], Cell[19682, 637, 964, 23, 218, "Text"], Cell[20649, 662, 178, 4, 68, "Text"], Cell[20830, 668, 103, 7, 138, "InlineInput"], Cell[20936, 677, 285, 6, 118, "Text"], Cell[21224, 685, 147, 8, 159, "InlineInput"], Cell[21374, 695, 1654, 54, 193, "Text"], Cell[23031, 751, 244, 8, 68, "Text"], Cell[23278, 761, 73, 6, 117, "InlineInput"], Cell[23354, 769, 1548, 48, 243, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[24939, 822, 54, 1, 42, "Subsection", CellTags->"c:14"], Cell[24996, 825, 1657, 48, 318, "Text"], Cell[CellGroupData[{ Cell[26678, 877, 61, 1, 42, "Subsubsection", CellTags->"c:15"], Cell[26742, 880, 269, 8, 43, "Text"], Cell[27014, 890, 120, 10, 201, "InlineInput"] }, Closed]], Cell[CellGroupData[{ Cell[27171, 905, 74, 1, 42, "Subsubsection", CellTags->"c:16"], Cell[27248, 908, 643, 22, 118, "Text"], Cell[27894, 932, 113, 10, 201, "InlineInput"], Cell[28010, 944, 140, 5, 43, "Text"], Cell[28153, 951, 103, 8, 159, "InlineInput"], Cell[28259, 961, 318, 7, 93, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[28614, 973, 54, 1, 42, "Subsubsection", CellTags->"c:17"], Cell[28671, 976, 667, 18, 193, "Text"], Cell[29341, 996, 122, 7, 138, "InlineInput"], Cell[29466, 1005, 124, 3, 43, "Text"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[29639, 1014, 60, 1, 42, "Subsection", CellTags->"c:18"], Cell[29702, 1017, 420, 9, 118, "Text"], Cell[30125, 1028, 162, 4, 120, "Input"], Cell[30290, 1034, 52, 0, 43, "Text"], Cell[30345, 1036, 162, 4, 120, "Input"], Cell[30510, 1042, 76, 0, 43, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[30623, 1047, 61, 1, 42, "Subsection", CellTags->"c:19"], Cell[30687, 1050, 975, 15, 318, "Text"], Cell[CellGroupData[{ Cell[31687, 1069, 56, 1, 42, "Subsubsection", CellTags->"c:20"], Cell[31746, 1072, 2878, 87, 343, "Text"], Cell[34627, 1161, 242, 11, 117, "InlineInput"], Cell[34872, 1174, 250, 11, 68, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[35159, 1190, 64, 1, 42, "Subsubsection", CellTags->"c:21"], Cell[35226, 1193, 147, 3, 68, "Text"], Cell[35376, 1198, 3677, 103, 493, "Text"], Cell[39056, 1303, 638, 26, 245, "InlineInput"], Cell[39697, 1331, 333, 14, 68, "Text"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[40079, 1351, 60, 1, 42, "Subsection", CellTags->"c:22"], Cell[40142, 1354, 260, 5, 93, "Text"], Cell[CellGroupData[{ Cell[40427, 1363, 58, 1, 42, "Subsubsection", CellTags->"c:23"], Cell[40488, 1366, 178, 6, 118, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[40703, 1377, 137, 5, 42, "Subsubsection", CellTags->"c:24"], Cell[40843, 1384, 3386, 104, 468, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[44266, 1493, 137, 5, 42, "Subsubsection", CellTags->"c:25"], Cell[44406, 1500, 658, 17, 118, "Text"], Cell[45067, 1519, 300, 6, 212, "Input"], Cell[45370, 1527, 57, 1, 51, "Input"], Cell[45430, 1530, 671, 19, 168, "Text"], Cell[46104, 1551, 1208, 30, 293, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[47349, 1586, 137, 5, 42, "Subsubsection", CellTags->"c:26"], Cell[47489, 1593, 477, 11, 118, "Text"], Cell[47969, 1606, 599, 18, 93, "Text"], Cell[48571, 1626, 97, 9, 180, "InlineInput"], Cell[48671, 1637, 60, 0, 43, "Text"], Cell[48734, 1639, 219, 6, 189, "Input"], Cell[48956, 1647, 256, 8, 45, "Text"], Cell[49215, 1657, 112, 10, 201, "InlineInput"], Cell[49330, 1669, 732, 21, 186, "Text"], Cell[50065, 1692, 849, 22, 218, "Text"], Cell[50917, 1716, 204, 7, 43, "Text"], Cell[51124, 1725, 921, 24, 168, "Text"], Cell[52048, 1751, 336, 6, 118, "Text"], Cell[52387, 1759, 552, 13, 168, "Text"] }, Closed]] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[53000, 1779, 48, 1, 47, "Section", CellTags->"c:27"], Cell[53051, 1782, 1894, 55, 293, "Text"], Cell[CellGroupData[{ Cell[54970, 1841, 75, 1, 42, "Subsection", CellTags->"c:28"], Cell[55048, 1844, 247, 5, 93, "Text"], Cell[55298, 1851, 1209, 35, 238, "Text"], Cell[56510, 1888, 3221, 92, 318, "Text"], Cell[59734, 1982, 125, 2, 74, "Input"], Cell[59862, 1986, 76, 1, 51, "Input"], Cell[59941, 1989, 94, 3, 43, "Text"], Cell[60038, 1994, 106, 2, 74, "Input"], Cell[60147, 1998, 59, 1, 51, "Input"] }, Closed]], Cell[CellGroupData[{ Cell[60243, 2004, 68, 1, 42, "Subsection", CellTags->"c:29"], Cell[60314, 2007, 598, 16, 215, "Text"], Cell[60915, 2025, 196, 4, 88, "InputOnly"], Cell[61114, 2031, 64, 0, 43, "Text"], Cell[61181, 2033, 225, 4, 120, "Input"], Cell[61409, 2039, 145, 5, 43, "Text"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[61603, 2050, 61, 1, 47, "Section", CellTags->"c:30"], Cell[61667, 2053, 653, 10, 193, "Text"], Cell[CellGroupData[{ Cell[62345, 2067, 64, 1, 42, "Subsection", CellTags->"c:31"], Cell[62412, 2070, 653, 10, 193, "Text"], Cell[63068, 2082, 1879, 47, 555, "Text"], Cell[CellGroupData[{ Cell[64972, 2133, 59, 1, 42, "Subsubsection", CellTags->"c:32"], Cell[65034, 2136, 88, 3, 43, "Text"], Cell[65125, 2141, 876, 22, 120, "Input"], Cell[66004, 2165, 101, 2, 51, "Input"], Cell[66108, 2169, 37, 1, 51, "Input"] }, Closed]], Cell[CellGroupData[{ Cell[66182, 2175, 52, 1, 42, "Subsubsection", CellTags->"c:33"], Cell[66237, 2178, 63, 0, 43, "Text"], Cell[66303, 2180, 40, 1, 51, "Input"], Cell[66346, 2183, 40, 1, 51, "Input"], Cell[66389, 2186, 65, 1, 51, "Input"], Cell[66457, 2189, 125, 3, 43, "Text"], Cell[66585, 2194, 482, 8, 189, "Input"], Cell[67070, 2204, 101, 2, 51, "Input"], Cell[67174, 2208, 40, 1, 51, "Input"], Cell[67217, 2211, 37, 1, 51, "Input"], Cell[67257, 2214, 45, 1, 51, "Input"] }, Closed]], Cell[CellGroupData[{ Cell[67339, 2220, 52, 1, 28, "Subsubsection", CellTags->"c:34"], Cell[67394, 2223, 56, 1, 39, "Input"], Cell[67453, 2226, 47, 1, 39, "Input"], Cell[67503, 2229, 127, 2, 39, "Input"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[67679, 2237, 134, 5, 42, "Subsection", CellTags->"c:35"], Cell[67816, 2244, 1345, 35, 405, "Text"], Cell[69164, 2281, 1935, 57, 318, "Text"], Cell[71102, 2340, 298, 5, 93, "Text"], Cell[71403, 2347, 207, 7, 130, "Input"], Cell[71613, 2356, 52, 1, 50, "Input"], Cell[71668, 2359, 46, 1, 50, "Input"], Cell[71717, 2362, 59, 0, 43, "Text"], Cell[71779, 2364, 518, 16, 68, "Text"], Cell[72300, 2382, 135, 4, 43, "Text"] }, Closed]] }, Closed]] }, Open ]] } ] *) (******************************************************************* End of Mathematica Notebook file. *******************************************************************)