(* Content-type: application/mathematica *)

(*** Wolfram Notebook File ***)
(* http://www.wolfram.com/nb *)

(* CreatedBy='Mathematica 6.0' *)

(*CacheID: 234*)
(* Internal cache information:
NotebookFileLineBreakTest
NotebookFileLineBreakTest
NotebookDataPosition[       145,          7]
NotebookDataLength[    112355,       2534]
NotebookOptionsPosition[    107232,       2369]
NotebookOutlinePosition[    107618,       2386]
CellTagsIndexPosition[    107575,       2383]
WindowFrame->Normal
ContainsDynamic->False*)

(* Beginning of Notebook Content *)
Notebook[{

Cell[CellGroupData[{
Cell["\<\
Some notes on the foundations of universal computation and the \
decidability/universality frontier.\
\>", "Title",
 CellChangeTimes->{{3.401373605659685*^9, 3.4013736148905277`*^9}, {
  3.401373802217329*^9, 3.401373808896308*^9}, {3.4147794642162447`*^9, 
  3.414779494986808*^9}, {3.41548937280751*^9, 3.415489384557571*^9}}],

Cell[CellGroupData[{

Cell[BoxData[
 RowBox[{"Print", "[", 
  RowBox[{"Text", "[", 
   RowBox[{"Style", "[", 
    RowBox[{
     RowBox[{
     "\"\<Hector \
Zenil\\nhectorz@andrew.cmu.edu\\nhector.zenil@lifl.fr\\n\>\"", "<>", 
      RowBox[{"DateString", "[", 
       RowBox[{"{", 
        RowBox[{
        "\"\<DayName\>\"", ",", " ", "\"\<, \>\"", ",", "\"\<MonthName\>\"", 
         ",", "\"\< \>\"", ",", "\"\<Day\>\"", ",", "\"\<, \>\"", ",", 
         "\"\<Year\>\""}], "}"}], "]"}]}], ",", "Gray", ",", "Italic", ",", 
     "18"}], "]"}], "]"}], "]"}]], "Input",
 CellChangeTimes->{{3.399301557117675*^9, 3.399301594169798*^9}, {
   3.400489340616968*^9, 3.400489350635304*^9}, {3.4007066703609657`*^9, 
   3.400706671131136*^9}, {3.400754107190681*^9, 3.400754128156077*^9}, {
   3.4013740891498404`*^9, 3.40137416224048*^9}, 3.401374326307199*^9, {
   3.414779400108629*^9, 3.414779438374804*^9}, {3.414779519283985*^9, 
   3.414779528830934*^9}, 3.4154893622824*^9}],

Cell[BoxData[
 InterpretationBox[Cell[BoxData[
   StyleBox["\<\"Hector Zenil\\nhectorz@andrew.cmu.edu\\nhector.zenil@lifl.fr\
\\nTuesday, March 25, 2008\"\>",
    StripOnInput->False,
    FrontFaceColor->GrayLevel[0.5],
    BackFaceColor->GrayLevel[0.5],
    GraphicsColor->GrayLevel[0.5],
    FontSize->18,
    FontSlant->Italic,
    FontColor->GrayLevel[0.5]]], "Text", "TR"],
  Text[
   Style["Hector Zenil\nhectorz@andrew.cmu.edu\nhector.zenil@lifl.fr\n\
Tuesday, March 25, 2008", 
    GrayLevel[0.5], Italic, 18]]]], "Print",
 GeneratedCell->False,
 CellAutoOverwrite->False,
 CellChangeTimes->{{3.3993015381084547`*^9, 3.399301557627346*^9}, 
   3.399301594756094*^9, 3.40048935145286*^9, 3.4004895749584*^9, {
   3.400706661100019*^9, 3.4007066725765553`*^9}, {3.4007541238237553`*^9, 
   3.400754137891369*^9}, {3.401374092609914*^9, 3.4013741000247583`*^9}, {
   3.401374135119349*^9, 3.401374167878574*^9}, {3.401565298999093*^9, 
   3.401565302607462*^9}, {3.414779433289567*^9, 3.414779438664716*^9}, 
   3.4147795295547333`*^9, 3.4154893654264402`*^9}]
}, {2}]],

Cell[CellGroupData[{

Cell["Summary", "Section",
 CellChangeTimes->{{3.4013738447357903`*^9, 3.401373845754067*^9}, {
  3.4154893957587833`*^9, 3.415489396492627*^9}}],

Cell["\<\
The 2,3 Turing machine that Stephen Wolfram suspected to be universal since \
the publication of his book A New Kind of Science (NKS) in 2002, turned out \
to be universal after the Alex Smith proof. This\[AliasDelimiter] was made by \
means of allowing an infinite non-periodic but  computationally simple enough \
background supporting but not performing the actual computation carried out \
by the machine. The aim of this notebook is to survey the necessary and \
sufficient conditions of computational universality and the consequences \
after the proof in question taking the seminal concept in computer science of \
computational universality to its limits. \
\>", "Text",
 CellFrame->{{0, 0}, {0.5, 0}},
 CellChangeTimes->{{3.401373605659685*^9, 3.401373635723077*^9}, {
   3.401374317145101*^9, 3.401374317276535*^9}, 3.401629403745278*^9, {
   3.4016294420165854`*^9, 3.4016297182842293`*^9}, {3.4147792278314857`*^9, 
   3.414779298331052*^9}, {3.4154894057345324`*^9, 3.4154894358562813`*^9}, 
   3.415489482127195*^9},
 TextJustification->1.]
}, Open  ]],

Cell[CellGroupData[{

Cell["Introduction", "Section",
 CellChangeTimes->{{3.401373605659685*^9, 3.401373640747263*^9}, {
  3.40137391861185*^9, 3.401373921699676*^9}}],

Cell["\<\
Various tools and methods have been devised for proving computational \
universality. Most of them involve the emulation of another system already \
known to be universal. A proof following that way can show emulation either \
of a specific universal system or of a whole class of systems that contain \
universal examples, for instance, tag systems.

Alexander Smith, a student from the University of Birmingham in the UK, has \
proved by means of emulating 2-color tag systems through a sequence of \
translations, that the 2,3 Turing machine that Stephen Wolfram suspected to \
be universal since the publication of his New Kind of Science (NKS) in 2002, \
is in fact a universal Turing machine. Tag systems, invented by Emil Post in \
1920, are sets of rules that specify a fixed number of elements to be removed \
from the beginning of a sequence and a set of elements to be appended onto \
the end based on the elements that were removed. An m-color tag system denote \
a tag system in which its rules always delete m elements from the beginning \
of the sequence. For each m>1, the set of m-color tag systems is \
Turing-complete. In particular, a 2-color tag system can be constructed to \
emulate a universal Turing machine. A Turing machine can be shown to be a \
universal Turing machine by proving that it can emulate a complete class of \
m-color tag systems with m>1.

A Turing machine M is an abstract device that performs operations over a \
tape. The tape is unbounded in both directions and divided into single \
squares. Each square of the tape has a color from a fixed finite list of \
colors. Usually a color often called \"blank\", supposed to represent the \
\"emptiness\" of the tape, is used to fill the tape in both directions, this \
color can be regarded as the background over which the Turing machine \
operates. There is a \"head\" that can read a color at a time, choose to \
write a new color in place, and then move to the left or to the right. The \
Turing machine is always provided with a finite input usually called initial \
condition or initial configuration. The machine also has a non-empty and \
finite set of states and a partial function that, according to the current \
state and the color of the tape under the head, determines the next state, \
what should be written and the movement of the head. Usually denoted by \
\[Delta] it fully describes the behavior of a Turing machine. This \
description constitutes the standard model of a Turing machine, namely a one \
bi-infinite tape, one head, deterministic, with a blank color and a halting \
state machine. A whole kind of variations turned out to be equivalent in \
terms of computational power, such as adding several tapes or heads, \
constraining the tape to a single direction or allowing non- deterministic \
transitions, none of them provide any additional computational power. 

Universal computation is the central concept in computer science since Alan \
Turing published his paper in 1936.  It can be regarded in fact as the birth \
of computer science itself. A universal Turing machine is a Turing machine \
able to perform, via a suitable encoding, the computation of any other \
possible Turing machine. Turing model plays also a variety of explanatory \
roles in science, for instance, Turing's model  is an example of how a \
computation by a human being or a mechanical device could be performed step \
by step and it is also used as the fundamental unit in many fields such as \
computational complexity nd algorithmic information theory. Beginning in the \
early sixties Marvin Minsky built a 7,4 universal Turing machine and a race \
with Watanabe, Rogozhin and others, in order to find smaller universal Turing \
machines began. Minsky\[CloseCurlyQuote]s machine simulates Turing machines \
via 2-color tag systems, which were proved by himself and Cooke to be \
Turing-complete. Recently, Neary and Woods gave small universal machines that \
simulate Turing machines via a new variant of tag systems, what they called \
bi-tag systems. It turned out that tailoring variations of tag systems was an \
extremely powerful tool to find and construct smaller Turing machines. Six \
months ago a research prize to find the final the smallest universal Turing \
machine was announced. A large fraction of Wolfram's NKS deals with \
presenting minimal systems. The set of this prize was to motivate the \
research on Wolfram's minimal program. In his NKS, Stephen Wolfram found a \
universal 2,5 Turing machine and suggested that a particular 2,3 machine \
might be universal. If so, because it is known that no universal Turing \
machine is possible with 2 states and 2 colors, that 2,3 Turing machine would \
be the smallest. Today the answer to the question has come in an exciting \
way. That particular Turing machine is universal and its proof didn't come \
alone, we have learned a lot and Alex Smith has done a remarkable \
contribution by shaking the foundations of the concept of computational \
universality. 

One traditional aim in math is to look at the most simple model or theory in \
a way that no axiom be redundant or derivable from the others. In computer \
science one can also ask for the minimal description of a computational \
model. One can wonder in general what are those essential elements necessary \
for universal computation. An essential element would be essential as far as \
it is necessary for the description of a universal Turing machine for which \
without it, the description would no longer be that of a universal Turing \
machine. That would happen, as it is well-known, if one does not allow a set \
of states, which play the role of a kind of memory that supplies a universal \
Turing machine, among with the unbounded tape, with its characteristic power. \
As for the colors since without them there would be nothing to compute with.  \
 \
\>", "Text",
 CellChangeTimes->{{3.401373605659685*^9, 3.401373647899744*^9}, {
   3.40137394642647*^9, 3.401373946957281*^9}, {3.4013743173994417`*^9, 
   3.401374320237974*^9}, {3.401374536963847*^9, 3.401374537585504*^9}, 
   3.401560610210888*^9, {3.401565321036063*^9, 3.401565324963784*^9}, {
   3.4016065353668947`*^9, 3.401606545071971*^9}, {3.4016297424581738`*^9, 
   3.401629773142941*^9}, {3.401629846877912*^9, 3.401629846942246*^9}, {
   3.401629883335136*^9, 3.401629928483782*^9}, {3.401629961442099*^9, 
   3.401629975252431*^9}, {3.401630015593972*^9, 3.4016300519190407`*^9}, {
   3.401630086854528*^9, 3.4016301219053507`*^9}, {3.4016301646395073`*^9, 
   3.401630261733857*^9}, {3.401630336422945*^9, 3.401630337053061*^9}, {
   3.401630517668333*^9, 3.4016306921624393`*^9}, {3.4016312447276373`*^9, 
   3.401631244923934*^9}, {3.401632268203607*^9, 3.401632372564715*^9}, {
   3.401632458364924*^9, 3.401632726188723*^9}, {3.401632897011655*^9, 
   3.401633015203802*^9}, {3.401633045823626*^9, 3.401633135810063*^9}, {
   3.401633174901622*^9, 3.401633538022315*^9}, {3.401633572256814*^9, 
   3.401633790958461*^9}, {3.401633867708561*^9, 3.401634010374419*^9}, {
   3.401634050643683*^9, 3.4016340636241198`*^9}, {3.401634095306349*^9, 
   3.40163418697031*^9}, {3.401634222302739*^9, 3.401634322920478*^9}, {
   3.401634379156027*^9, 3.401634469226536*^9}, {3.40163450162285*^9, 
   3.401634543979199*^9}, 3.401636304465445*^9, {3.401644658675111*^9, 
   3.4016446773450537`*^9}, {3.4016447112040863`*^9, 
   3.4016447262666597`*^9}, {3.401644778167342*^9, 3.4016447851086197`*^9}, {
   3.40164484971275*^9, 3.4016448772316236`*^9}, {3.401724769155034*^9, 
   3.4017248012639713`*^9}, {3.401724860149994*^9, 3.401724876466501*^9}, {
   3.4017249807189493`*^9, 3.401724991965362*^9}, {3.4017250368449993`*^9, 
   3.4017251656041813`*^9}, {3.401725205505669*^9, 3.401725231643518*^9}, {
   3.4017252696741533`*^9, 3.401725286944766*^9}},
 TextJustification->1.],

Cell["\<\
The rules for the Turing machine proved to be universal are : \
\>", "Text",
 CellChangeTimes->{{3.401635254950952*^9, 3.40163526106843*^9}, {
  3.4016354033160458`*^9, 3.401635413121711*^9}, {3.4016355544972486`*^9, 
  3.4016355611818457`*^9}}],

Cell[CellGroupData[{

Cell[BoxData[
 RowBox[{
  RowBox[{"{", 
   RowBox[{
    RowBox[{
     RowBox[{"{", 
      RowBox[{"1", ",", "2"}], "}"}], "\[Rule]", 
     RowBox[{"{", 
      RowBox[{"1", ",", "1", ",", 
       RowBox[{"-", "1"}]}], "}"}]}], ",", 
    RowBox[{
     RowBox[{"{", 
      RowBox[{"1", ",", "1"}], "}"}], "\[Rule]", 
     RowBox[{"{", 
      RowBox[{"1", ",", "2", ",", 
       RowBox[{"-", "1"}]}], "}"}]}], ",", 
    RowBox[{
     RowBox[{"{", 
      RowBox[{"1", ",", "0"}], "}"}], "\[Rule]", 
     RowBox[{"{", 
      RowBox[{"2", ",", "1", ",", "1"}], "}"}]}], ",", 
    RowBox[{
     RowBox[{"{", 
      RowBox[{"2", ",", "2"}], "}"}], "\[Rule]", 
     RowBox[{"{", 
      RowBox[{"1", ",", "0", ",", "1"}], "}"}]}], ",", 
    RowBox[{
     RowBox[{"{", 
      RowBox[{"2", ",", "1"}], "}"}], "\[Rule]", 
     RowBox[{"{", 
      RowBox[{"2", ",", "2", ",", "1"}], "}"}]}], ",", 
    RowBox[{
     RowBox[{"{", 
      RowBox[{"2", ",", "0"}], "}"}], "\[Rule]", 
     RowBox[{"{", 
      RowBox[{"1", ",", "2", ",", 
       RowBox[{"-", "1"}]}], "}"}]}]}], "}"}], "//", "Column"}]], "Input",
 CellChangeTimes->{{3.401635564095188*^9, 3.401635565001779*^9}}],

Cell[BoxData[
 TagBox[GridBox[{
    {
     RowBox[{
      RowBox[{"{", 
       RowBox[{"1", ",", "2"}], "}"}], "\[Rule]", 
      RowBox[{"{", 
       RowBox[{"1", ",", "1", ",", 
        RowBox[{"-", "1"}]}], "}"}]}]},
    {
     RowBox[{
      RowBox[{"{", 
       RowBox[{"1", ",", "1"}], "}"}], "\[Rule]", 
      RowBox[{"{", 
       RowBox[{"1", ",", "2", ",", 
        RowBox[{"-", "1"}]}], "}"}]}]},
    {
     RowBox[{
      RowBox[{"{", 
       RowBox[{"1", ",", "0"}], "}"}], "\[Rule]", 
      RowBox[{"{", 
       RowBox[{"2", ",", "1", ",", "1"}], "}"}]}]},
    {
     RowBox[{
      RowBox[{"{", 
       RowBox[{"2", ",", "2"}], "}"}], "\[Rule]", 
      RowBox[{"{", 
       RowBox[{"1", ",", "0", ",", "1"}], "}"}]}]},
    {
     RowBox[{
      RowBox[{"{", 
       RowBox[{"2", ",", "1"}], "}"}], "\[Rule]", 
      RowBox[{"{", 
       RowBox[{"2", ",", "2", ",", "1"}], "}"}]}]},
    {
     RowBox[{
      RowBox[{"{", 
       RowBox[{"2", ",", "0"}], "}"}], "\[Rule]", 
      RowBox[{"{", 
       RowBox[{"1", ",", "2", ",", 
        RowBox[{"-", "1"}]}], "}"}]}]}
   },
   ColumnsEqual->False,
   GridBoxAlignment->{"Columns" -> {{Left}}},
   GridBoxItemSize->{"Columns" -> {{Automatic}}, "Rows" -> {{Automatic}}},
   RowsEqual->False],
  "Column"]], "Output",
 CellChangeTimes->{3.401635565227806*^9}]
}, {2}]],

Cell["\<\
where this means {state, color} -> {state, color, offset}. These rules can be \
represented pictorially by :\
\>", "Text",
 CellChangeTimes->{{3.401635254950952*^9, 3.40163526106843*^9}, {
  3.4016354033160458`*^9, 3.401635418052816*^9}, {3.401635538769494*^9, 
  3.401635539325522*^9}, {3.401636893790298*^9, 3.401636898989917*^9}}],

Cell[CellGroupData[{

Cell[BoxData[
 RowBox[{"Import", "[", 
  "\"\<http://www.wolframscience.com/prizes/tm23/images/turing_machine.gif\>\"\
", "]"}]], "Input",
 CellChangeTimes->{{3.4016356647418423`*^9, 3.401635667507024*^9}}],

Cell[BoxData[
 GraphicsBox[RasterBox[CompressedData["
1:eJztm2t2mzAQhQ3IID/AbmJjYtKOu4OupUvIBrr/f5UQDgMjoVGwG/eE25ao
h3uG0Sc6etj9+fbn91u8WCx+qT/naLH4MculS5DC7HcNfm/71yGzCoz+SGTW
YfYvRGZ+Z1z6Qu9MYDLrTZg9LPpDVeCZjEsMMkfUvj2ZTd21p5NJs+qqLCV+
6k6uom5ChsT+gbtHyYzmQsmknYz9tBtJndqxLGSS106S+En0752q4U1ChsSO
8BMomQS1SS4WMigZ3dUNnEZSJ/aeJpOJUPRkeNNPBgDdvTmZHFCA/4vMDgB5
bk7mBGIk9QAyuTX7vn/onkamAChQVxlkzsg+dJOuCoDO3yOT2+w9ITK1irOz
ZN/3XxtqtJvxmEZGPRLl7iezBog6+9A97OpGRe96gMjo5Gs+maKNwyMjlVvn
PY2MCoJeGi8Z3VV4n268ZFbaTlM3yRf3JKPnomlkIhWlmz68ZM5hZC4uMsI8
ll1nhBk/HhmdpO74NDJngV53xr8mYYajtQ/dlgqMuKOeFqYUsMkof27Jvu/v
kjbDMXHW7slP5mRSbO0kwHhXu2ZuiLHJ5KamMsmsTC38t2RqPA1/nMzF1H3+
rG3e1Io5a5vSGbYGHo1tIYMjyi7F1k4C4GRGl2IR+O3YXzV/Scv33UQ5Br5q
+i1Lmco01RfB2DeNxbbtm4b+Ai33LWSYqV/Wld+O/bvhXSqy0hvV7U8hjqMr
vVH1Vnr+rtpOIb51Gg/vdVMyx9poU9fkno1ME1bhsEWnZOrGvjtas6Gpb4y9
tka3nUJgecOn6fNV1E3IRFWV6N/ql+TUmSUSY98kn1QaT6LUP/ypX2Si8kiE
1Eco43XGiF3GjBvV1Gh4k5CRjraRhUyTxRKaK7GTAGWThhCxupbe1NsMhNCP
JblPJvOMyPhnbfx8PhnBJXMwZEBfD97U2zWBgK6N7TchE7/G9yQDsA0gsweI
eWSaCWrVrm+J3UFmm24DyOwP+wAyRWLme/JkB5ktwDKAzAvAIYBMYjYcXDIq
GUi5ZGI1SrBnk1GpNKPEJqP3hQFktD2ATLvrDCEDbDIlmGHikYF2fx1EZssm
E4eRyT9ApmSTeQl6Z2R7ksAmswx+Z8qwd6Y5eyF2R50xyTDrjBomwa8zu/ag
jV+B02XI3BSXL8y5qSGTR4l+LJtMCSKgAgs4xPwK3B6a8MkYsWdtIy6ZVvy5
CQLmJlWC4wAyCTQfTH4+mcTRNvapZFKzhNjz1sDN6UphDizvQEYgMuw1MG0b
u4WMzLKsEuqSSca+SbszUVnd9ORKaomo+UGebCGTdWKQkcieeVP32D/7E3+s
+bsQLs1kXJrJuDSTcWkm49JMxqWZjEszGZcei0zo94eD3IwPsD4e/N7flF59
9v+VeVj9BZnhNaM=
   "], {{0, 0}, {282, 48}},
   ColorFunction->(Apply[RGBColor, 
     Part[CompressedData["
1:eJx1080uA1EYBuCJuAFCEATXYfFdg0r8RUgk1hZiydqSqP5OsXADktZKECti
0ZZWO/XTJhRRM7UmSr935nyNOfEkkzeTd3rmzDmnIwtLgcU2wzCGm1d788rn
gMbhWtKAD/ppMIf6oUYDYEo/DRbNQIniMVaSvhPOaHODnXq/P5I+tM3y1AVJ
L/elV/MZgyz1wYX0HZClbsiTVQTphyBNe7ssTdkMSB+NsFctVR8OsWctVT8P
dS1VvwJV77ty2vtn4V1L1bvPV7RU/dcne5P9GYWa9IcpVqVUkj1RL6xLX35g
jtz7cxDuKWGyOwrAlfRTUKRJKGjf5+6XRRNw461DUPrGN7NpDhw6OWat+bjn
JkNmnF16+30g/TI8UnCLtVL1PVCQ+fnPpzvurZxf//qsgi25k2C2tn5q3ur/
4l/HNXC08StlVqdYlFne+TuXPhJmL1r+Hf8/+n768xcILIGl
      "], #]]& ),
   ColorFunctionScaling->False],
  Background->None,
  ImageSize->{282, 48},
  PlotRange->{{0, 282}, {0, 48}}]], "Output",
 CellChangeTimes->{3.4016356720582438`*^9}]
}, {2}]],

Cell[CellGroupData[{

Cell["\<\
A visual representation of the evolution of the 2,3 universal Turing machine \
after 20 steps\
\>", "Subsection",
 CellGroupingRules->{GroupTogetherGrouping, 10000.},
 CellChangeTimes->{{3.401373605659685*^9, 3.401373676388452*^9}, 
   3.4013743211723948`*^9, {3.401566046779655*^9, 3.401566059455983*^9}, {
   3.40156850282556*^9, 3.401568527431107*^9}, {3.401568562487171*^9, 
   3.401568572623019*^9}, 3.401568618610668*^9, {3.4015687192524757`*^9, 
   3.401568735568383*^9}, {3.401634568400344*^9, 3.40163457376365*^9}, {
   3.40163535339677*^9, 3.4016353830725727`*^9}, {3.401635588273806*^9, 
   3.401635614399951*^9}, {3.401636892422336*^9, 3.401636947208084*^9}}],

Cell[BoxData[
 RowBox[{
  RowBox[{"Color1", "=", 
   RowBox[{"RGBColor", "[", 
    RowBox[{"{", 
     RowBox[{"0.977", ",", "0.952", ",", "0."}], "}"}], "]"}]}], 
  ";"}]], "Input",
 CellGroupingRules->{GroupTogetherGrouping, 10000.},
 CellChangeTimes->{{3.3876780049196014`*^9, 3.3876780571390195`*^9}, 
   3.387678350611526*^9, {3.3877498362248926`*^9, 3.387749841771838*^9}, 
   3.3877498782879305`*^9, 3.3877500188991055`*^9, 3.4015684614456663`*^9, {
   3.4015686017938766`*^9, 3.401568618610853*^9}}],

Cell[BoxData[
 RowBox[{
  RowBox[{"Color2", "=", 
   RowBox[{"RGBColor", "[", 
    RowBox[{"{", 
     RowBox[{"0.965", ",", "0.401", ",", "0.18"}], "}"}], "]"}]}], 
  ";"}]], "Input",
 CellGroupingRules->{GroupTogetherGrouping, 10000.},
 CellChangeTimes->{{3.3876779946225944`*^9, 3.387677998950775*^9}, {
   3.387678033076212*^9, 3.3876780549983673`*^9}, 3.3876783486115007`*^9, {
   3.3877498497719407`*^9, 3.387749880366082*^9}, 3.387750017070957*^9, 
   3.4015684614457903`*^9, {3.401568601794011*^9, 3.4015686186109877`*^9}}],

Cell[BoxData[
 RowBox[{
  RowBox[{"TM23Graphics", "[", 
   RowBox[{"data_", ",", "opts___"}], "]"}], ":=", 
  RowBox[{"ArrayPlot", "[", 
   RowBox[{
    RowBox[{
     RowBox[{
      RowBox[{"Join", "[", 
       RowBox[{
        RowBox[{"{", "0", "}"}], ",", "#", ",", 
        RowBox[{"{", "0", "}"}]}], "]"}], "&"}], "/@", 
     RowBox[{"Last", "/@", "data"}]}], ",", 
    RowBox[{"ColorRules", "\[Rule]", 
     RowBox[{"{", 
      RowBox[{
       RowBox[{"0", "\[Rule]", "White"}], ",", 
       RowBox[{"1", "\[Rule]", "Color1"}], ",", 
       RowBox[{"2", "\[Rule]", "Color2"}]}], "}"}]}], ",", "opts", ",", 
    RowBox[{"Epilog", "\[Rule]", 
     RowBox[{"MapIndexed", "[", 
      RowBox[{
       RowBox[{
        RowBox[{"Translate", "[", 
         RowBox[{
          RowBox[{"Rotate", "[", 
           RowBox[{
            RowBox[{"With", "[", 
             RowBox[{
              RowBox[{"{", 
               RowBox[{"r", "=", ".18"}], "}"}], ",", 
              RowBox[{"{", 
               RowBox[{
                RowBox[{"Disk", "[", 
                 RowBox[{
                  RowBox[{"{", 
                   RowBox[{"0", ",", "0"}], "}"}], ",", "r"}], "]"}], ",", 
                RowBox[{"Polygon", "[", 
                 RowBox[{"{", 
                  RowBox[{
                   RowBox[{"{", 
                    RowBox[{"r", ",", "0"}], "}"}], ",", 
                   RowBox[{"{", 
                    RowBox[{
                    RowBox[{"-", "r"}], ",", "0"}], "}"}], ",", 
                   RowBox[{"{", 
                    RowBox[{"0", ",", ".6"}], "}"}], ",", 
                   RowBox[{"{", 
                    RowBox[{"r", ",", "0"}], "}"}]}], "}"}], "]"}]}], "}"}]}],
              "]"}], ",", 
            RowBox[{"2", 
             RowBox[{"(", 
              RowBox[{
               RowBox[{"#", "[", 
                RowBox[{"[", 
                 RowBox[{"1", ",", "1"}], "]"}], "]"}], "-", "1"}], ")"}], 
             RowBox[{"\[Pi]", "/", "2"}]}], ",", 
            RowBox[{"{", 
             RowBox[{"0", ",", "0"}], "}"}]}], "]"}], ",", 
          RowBox[{"{", 
           RowBox[{
            RowBox[{
             RowBox[{"#", "[", 
              RowBox[{"[", 
               RowBox[{"1", ",", "2"}], "]"}], "]"}], "+", 
             RowBox[{"1", "/", "2"}]}], ",", 
            RowBox[{
             RowBox[{"Length", "[", "data", "]"}], "-", 
             RowBox[{"First", "[", "#2", "]"}], "+", 
             RowBox[{"1", "/", "2"}]}]}], "}"}]}], "]"}], "&"}], ",", 
       "data"}], "]"}]}]}], "]"}]}]], "Input",
 CellGroupingRules->{GroupTogetherGrouping, 10000.},
 CellChangeTimes->{{3.3876781243273797`*^9, 3.3876781700779653`*^9}, {
   3.387678207000313*^9, 3.3876782075784454`*^9}, {3.3876782852044387`*^9, 
   3.387678320908021*^9}, 3.401568461445942*^9, {3.401568601794132*^9, 
   3.401568618611113*^9}}],

Cell[BoxData[
 RowBox[{
  RowBox[{"TMIcon", "[", "s_", "]"}], ":=", 
  RowBox[{"Rotate", "[", 
   RowBox[{
    RowBox[{"With", "[", 
     RowBox[{
      RowBox[{"{", 
       RowBox[{"r", "=", ".18"}], "}"}], ",", 
      RowBox[{"{", 
       RowBox[{
        RowBox[{"Disk", "[", 
         RowBox[{
          RowBox[{"{", 
           RowBox[{"0", ",", "0"}], "}"}], ",", "r"}], "]"}], ",", 
        RowBox[{"Polygon", "[", 
         RowBox[{"{", 
          RowBox[{
           RowBox[{"{", 
            RowBox[{"r", ",", "0"}], "}"}], ",", 
           RowBox[{"{", 
            RowBox[{
             RowBox[{"-", "r"}], ",", "0"}], "}"}], ",", 
           RowBox[{"{", 
            RowBox[{"0", ",", ".6"}], "}"}], ",", 
           RowBox[{"{", 
            RowBox[{"r", ",", "0"}], "}"}]}], "}"}], "]"}]}], "}"}]}], "]"}], 
    ",", 
    RowBox[{"2", 
     RowBox[{"(", 
      RowBox[{"s", "-", "1"}], ")"}], 
     RowBox[{"\[Pi]", "/", "2"}]}], ",", 
    RowBox[{"{", 
     RowBox[{"0", ",", "0"}], "}"}]}], "]"}]}]], "Input",
 CellGroupingRules->{GroupTogetherGrouping, 10000.},
 CellChangeTimes->{{3.3880698956654224`*^9, 3.3880698979310765`*^9}, {
   3.388069928509593*^9, 3.388069936681573*^9}, 3.401568461446073*^9, {
   3.4015686017942743`*^9, 3.40156861861124*^9}}],

Cell[BoxData[
 RowBox[{
  RowBox[{"TM23NestList", "[", 
   RowBox[{"init_", ",", "t_"}], "]"}], ":=", 
  RowBox[{"NestList", "[", 
   RowBox[{
    RowBox[{
     RowBox[{"(", 
      RowBox[{"Join", "[", 
       RowBox[{
        RowBox[{"{", "1", "}"}], ",", 
        RowBox[{"Mod", "[", 
         RowBox[{
          RowBox[{"Accumulate", "[", "#", "]"}], ",", "2"}], "]"}], ",", 
        RowBox[{
         RowBox[{"{", 
          RowBox[{
           RowBox[{"{", "1", "}"}], ",", 
           RowBox[{"{", 
            RowBox[{"1", ",", "0", ",", "1"}], "}"}]}], "}"}], "[", 
         RowBox[{"[", 
          RowBox[{"1", "+", 
           RowBox[{"Mod", "[", 
            RowBox[{
             RowBox[{"Total", "[", "#", "]"}], ",", "2"}], "]"}]}], "]"}], 
         "]"}]}], "]"}], ")"}], "&"}], ",", "init", ",", "t"}], 
   "]"}]}]], "Input",
 CellGroupingRules->{GroupTogetherGrouping, 10000.},
 CellChangeTimes->{{3.38789085534375*^9, 3.387890862453125*^9}, 
   3.4015684614467173`*^9, {3.401568601794873*^9, 3.401568618611874*^9}}],

Cell[BoxData[
 RowBox[{
  RowBox[{"StepCount", "[", "hist_", "]"}], ":=", 
  RowBox[{
   RowBox[{
    RowBox[{"-", "7"}], " ", 
    RowBox[{"(", 
     RowBox[{
      RowBox[{"Length", "[", "hist", "]"}], "-", "1"}], ")"}]}], "+", 
   RowBox[{"2", " ", 
    RowBox[{"Total", "[", 
     RowBox[{"Rest", "[", 
      RowBox[{"Length", "/@", "hist"}], "]"}], "]"}]}], "+", 
   RowBox[{"2", 
    RowBox[{"Count", "[", 
     RowBox[{
      RowBox[{"Rest", "[", "hist", "]"}], ",", "1", ",", 
      RowBox[{"{", "2", "}"}]}], "]"}]}], "+", 
   RowBox[{"Length", "[", 
    RowBox[{"Last", "[", "hist", "]"}], "]"}], "-", 
   RowBox[{"Length", "[", 
    RowBox[{"First", "[", "hist", "]"}], "]"}]}]}]], "Input",
 CellGroupingRules->{GroupTogetherGrouping, 10000.},
 CellChangeTimes->{{3.3878124569375*^9, 3.387812544140625*^9}, {
   3.387890826515625*^9, 3.387890827171875*^9}, 3.401568461446843*^9, {
   3.4015686017949877`*^9, 3.401568618612001*^9}}]
}, Closed]],

Cell[CellGroupData[{

Cell[BoxData[
 RowBox[{"TM23Graphics", "[", 
  RowBox[{
   RowBox[{"TuringMachine", "[", 
    RowBox[{
     RowBox[{"{", 
      RowBox[{"596440", ",", "2", ",", "3"}], "}"}], ",", 
     RowBox[{"{", 
      RowBox[{"1", ",", 
       RowBox[{"{", 
        RowBox[{
         RowBox[{"{", "}"}], ",", "0"}], "}"}]}], "}"}], ",", "20"}], "]"}], 
   ",", 
   RowBox[{"Mesh", "\[Rule]", "True"}], ",", 
   RowBox[{"ImageSize", "\[Rule]", "120"}]}], "]"}]], "Input",
 CellChangeTimes->{{3.3876781464995384`*^9, 3.387678193734518*^9}, {
  3.401568692490534*^9, 3.401568703585293*^9}, {3.4016352086816893`*^9, 
  3.401635208753644*^9}}],

Cell[BoxData[
 GraphicsBox[{RasterBox[CompressedData["
1:eJxTTMoPSmVmYGAQBWJOIAaxIeCDPTp9V4Wtcarze3uBCMstJ8re2cNU4hJ/
WCWyzv3hO3uX7pznv1fetOe6vrjAluu4PS5xUu3FpZ5UeqD8RWua1v4aKP9S
y1+kqh9s/qJWOAyUv6gVDkPFX0M9HZJaDgw2f5EaL0PdX0O9PCTVX0Ol3KCW
vwZbvUxrfw2U+6nlL1q3Y2ntL2qpHyr+GurpcKiUD6TSw9VfQ708JNVfA+2u
4UYDAGf1Tsc=
    "], {{0, 0}, {9, 21}}, {0, 1}], {
    {GrayLevel[
      NCache[-1 + GoldenRatio, 0.6180339887498949]], 
     StyleBox[
      LineBox[{{{0, 21}, {9, 21}}, {{0, 20}, {9, 20}}, {{0, 19}, {9, 19}}, {{
       0, 18}, {9, 18}}, {{0, 17}, {9, 17}}, {{0, 16}, {9, 16}}, {{0, 15}, {9,
        15}}, {{0, 14}, {9, 14}}, {{0, 13}, {9, 13}}, {{0, 12}, {9, 12}}, {{0,
        11}, {9, 11}}, {{0, 10}, {9, 10}}, {{0, 9}, {9, 9}}, {{0, 8}, {9, 
       8}}, {{0, 7}, {9, 7}}, {{0, 6}, {9, 6}}, {{0, 5}, {9, 5}}, {{0, 4}, {9,
        4}}, {{0, 3}, {9, 3}}, {{0, 2}, {9, 2}}, {{0, 1}, {9, 1}}, {{0, 0}, {
       9, 0}}}],
      Antialiasing->False]}, 
    {GrayLevel[
      NCache[-1 + GoldenRatio, 0.6180339887498949]], 
     StyleBox[
      LineBox[{{{0, 0}, {0, 21}}, {{1, 0}, {1, 21}}, {{2, 0}, {2, 21}}, {{3, 
       0}, {3, 21}}, {{4, 0}, {4, 21}}, {{5, 0}, {5, 21}}, {{6, 0}, {6, 
       21}}, {{7, 0}, {7, 21}}, {{8, 0}, {8, 21}}, {{9, 0}, {9, 21}}}],
      Antialiasing->False]}}},
  Epilog->{
    GeometricTransformationBox[
     GeometricTransformationBox[{
       DiskBox[{0, 0}, 0.18], 
       PolygonBox[{{0.18, 0}, {-0.18, 0}, {0, 0.6}, {0.18, 0}}]}, {{{1, 0}, {
       0, 1}}, {0, 0}}], 
     NCache[{
       Rational[7, 2], 
       Rational[41, 2]}, {3.5, 20.5}]], 
    GeometricTransformationBox[
     GeometricTransformationBox[{
       DiskBox[{0, 0}, 0.18], 
       PolygonBox[{{0.18, 0}, {-0.18, 0}, {0, 0.6}, {0.18, 0}}]}, {{{-1, 0}, {
       0, -1}}, {0, 0}}], 
     NCache[{
       Rational[9, 2], 
       Rational[39, 2]}, {4.5, 19.5}]], 
    GeometricTransformationBox[
     GeometricTransformationBox[{
       DiskBox[{0, 0}, 0.18], 
       PolygonBox[{{0.18, 0}, {-0.18, 0}, {0, 0.6}, {0.18, 0}}]}, {{{1, 0}, {
       0, 1}}, {0, 0}}], 
     NCache[{
       Rational[7, 2], 
       Rational[37, 2]}, {3.5, 18.5}]], 
    GeometricTransformationBox[
     GeometricTransformationBox[{
       DiskBox[{0, 0}, 0.18], 
       PolygonBox[{{0.18, 0}, {-0.18, 0}, {0, 0.6}, {0.18, 0}}]}, {{{1, 0}, {
       0, 1}}, {0, 0}}], 
     NCache[{
       Rational[5, 2], 
       Rational[35, 2]}, {2.5, 17.5}]], 
    GeometricTransformationBox[
     GeometricTransformationBox[{
       DiskBox[{0, 0}, 0.18], 
       PolygonBox[{{0.18, 0}, {-0.18, 0}, {0, 0.6}, {0.18, 0}}]}, {{{-1, 0}, {
       0, -1}}, {0, 0}}], 
     NCache[{
       Rational[7, 2], 
       Rational[33, 2]}, {3.5, 16.5}]], 
    GeometricTransformationBox[
     GeometricTransformationBox[{
       DiskBox[{0, 0}, 0.18], 
       PolygonBox[{{0.18, 0}, {-0.18, 0}, {0, 0.6}, {0.18, 0}}]}, {{{1, 0}, {
       0, 1}}, {0, 0}}], 
     NCache[{
       Rational[9, 2], 
       Rational[31, 2]}, {4.5, 15.5}]], 
    GeometricTransformationBox[
     GeometricTransformationBox[{
       DiskBox[{0, 0}, 0.18], 
       PolygonBox[{{0.18, 0}, {-0.18, 0}, {0, 0.6}, {0.18, 0}}]}, {{{1, 0}, {
       0, 1}}, {0, 0}}], 
     NCache[{
       Rational[7, 2], 
       Rational[29, 2]}, {3.5, 14.5}]], 
    GeometricTransformationBox[
     GeometricTransformationBox[{
       DiskBox[{0, 0}, 0.18], 
       PolygonBox[{{0.18, 0}, {-0.18, 0}, {0, 0.6}, {0.18, 0}}]}, {{{-1, 0}, {
       0, -1}}, {0, 0}}], 
     NCache[{
       Rational[9, 2], 
       Rational[27, 2]}, {4.5, 13.5}]], 
    GeometricTransformationBox[
     GeometricTransformationBox[{
       DiskBox[{0, 0}, 0.18], 
       PolygonBox[{{0.18, 0}, {-0.18, 0}, {0, 0.6}, {0.18, 0}}]}, {{{-1, 0}, {
       0, -1}}, {0, 0}}], 
     NCache[{
       Rational[11, 2], 
       Rational[25, 2]}, {5.5, 12.5}]], 
    GeometricTransformationBox[
     GeometricTransformationBox[{
       DiskBox[{0, 0}, 0.18], 
       PolygonBox[{{0.18, 0}, {-0.18, 0}, {0, 0.6}, {0.18, 0}}]}, {{{1, 0}, {
       0, 1}}, {0, 0}}], 
     NCache[{
       Rational[9, 2], 
       Rational[23, 2]}, {4.5, 11.5}]], 
    GeometricTransformationBox[
     GeometricTransformationBox[{
       DiskBox[{0, 0}, 0.18], 
       PolygonBox[{{0.18, 0}, {-0.18, 0}, {0, 0.6}, {0.18, 0}}]}, {{{1, 0}, {
       0, 1}}, {0, 0}}], 
     NCache[{
       Rational[7, 2], 
       Rational[21, 2]}, {3.5, 10.5}]], 
    GeometricTransformationBox[
     GeometricTransformationBox[{
       DiskBox[{0, 0}, 0.18], 
       PolygonBox[{{0.18, 0}, {-0.18, 0}, {0, 0.6}, {0.18, 0}}]}, {{{1, 0}, {
       0, 1}}, {0, 0}}], 
     NCache[{
       Rational[5, 2], 
       Rational[19, 2]}, {2.5, 9.5}]], 
    GeometricTransformationBox[
     GeometricTransformationBox[{
       DiskBox[{0, 0}, 0.18], 
       PolygonBox[{{0.18, 0}, {-0.18, 0}, {0, 0.6}, {0.18, 0}}]}, {{{1, 0}, {
       0, 1}}, {0, 0}}], 
     NCache[{
       Rational[3, 2], 
       Rational[17, 2]}, {1.5, 8.5}]], 
    GeometricTransformationBox[
     GeometricTransformationBox[{
       DiskBox[{0, 0}, 0.18], 
       PolygonBox[{{0.18, 0}, {-0.18, 0}, {0, 0.6}, {0.18, 0}}]}, {{{-1, 0}, {
       0, -1}}, {0, 0}}], 
     NCache[{
       Rational[5, 2], 
       Rational[15, 2]}, {2.5, 7.5}]], 
    GeometricTransformationBox[
     GeometricTransformationBox[{
       DiskBox[{0, 0}, 0.18], 
       PolygonBox[{{0.18, 0}, {-0.18, 0}, {0, 0.6}, {0.18, 0}}]}, {{{1, 0}, {
       0, 1}}, {0, 0}}], 
     NCache[{
       Rational[7, 2], 
       Rational[13, 2]}, {3.5, 6.5}]], 
    GeometricTransformationBox[
     GeometricTransformationBox[{
       DiskBox[{0, 0}, 0.18], 
       PolygonBox[{{0.18, 0}, {-0.18, 0}, {0, 0.6}, {0.18, 0}}]}, {{{1, 0}, {
       0, 1}}, {0, 0}}], 
     NCache[{
       Rational[5, 2], 
       Rational[11, 2]}, {2.5, 5.5}]], 
    GeometricTransformationBox[
     GeometricTransformationBox[{
       DiskBox[{0, 0}, 0.18], 
       PolygonBox[{{0.18, 0}, {-0.18, 0}, {0, 0.6}, {0.18, 0}}]}, {{{-1, 0}, {
       0, -1}}, {0, 0}}], 
     NCache[{
       Rational[7, 2], 
       Rational[9, 2]}, {3.5, 4.5}]], 
    GeometricTransformationBox[
     GeometricTransformationBox[{
       DiskBox[{0, 0}, 0.18], 
       PolygonBox[{{0.18, 0}, {-0.18, 0}, {0, 0.6}, {0.18, 0}}]}, {{{-1, 0}, {
       0, -1}}, {0, 0}}], 
     NCache[{
       Rational[9, 2], 
       Rational[7, 2]}, {4.5, 3.5}]], 
    GeometricTransformationBox[
     GeometricTransformationBox[{
       DiskBox[{0, 0}, 0.18], 
       PolygonBox[{{0.18, 0}, {-0.18, 0}, {0, 0.6}, {0.18, 0}}]}, {{{-1, 0}, {
       0, -1}}, {0, 0}}], 
     NCache[{
       Rational[11, 2], 
       Rational[5, 2]}, {5.5, 2.5}]], 
    GeometricTransformationBox[
     GeometricTransformationBox[{
       DiskBox[{0, 0}, 0.18], 
       PolygonBox[{{0.18, 0}, {-0.18, 0}, {0, 0.6}, {0.18, 0}}]}, {{{1, 0}, {
       0, 1}}, {0, 0}}], 
     NCache[{
       Rational[13, 2], 
       Rational[3, 2]}, {6.5, 1.5}]], 
    GeometricTransformationBox[
     GeometricTransformationBox[{
       DiskBox[{0, 0}, 0.18], 
       PolygonBox[{{0.18, 0}, {-0.18, 0}, {0, 0.6}, {0.18, 0}}]}, {{{-1, 0}, {
       0, -1}}, {0, 0}}], 
     NCache[{
       Rational[15, 2], 
       Rational[1, 2]}, {7.5, 0.5}]]},
  Frame->False,
  FrameLabel->{None, None},
  FrameTicks->{{None, None}, {None, None}},
  ImageSize->120]], "Output",
 CellChangeTimes->{{3.387678184984406*^9, 3.3876782170004406`*^9}, {
   3.3876783055953245`*^9, 3.387678323267426*^9}, {3.3876783587522554`*^9, 
   3.387678364486704*^9}, 3.387890297515625*^9, 3.387896342897087*^9, 
   3.4015684665863533`*^9, {3.401568696901493*^9, 3.401568703881315*^9}, 
   3.4016352091693363`*^9}]
}, {2}]]
}, Open  ]],

Cell[CellGroupData[{

Cell["\<\
On the necessary and sufficient conditions for universal computation\
\>", "Section",
 CellChangeTimes->{{3.401373605659685*^9, 3.401373655163785*^9}, {
  3.4154896237787313`*^9, 3.415489628689082*^9}}],

Cell["\<\
One could probably think that it would be possible to dispose even of the \
whole physical description of a Turing machine, namely the head and the tape, \
and remain with the transition function that characterize its behavior in \
every sense. And that is totally fair, such descriptions in those terms exist \
and have been studied for the same time but probably not to the same extent \
as for Turing machines. Those computational models avoiding physical \
descriptions continue to be broadly studied as, for instance, functions going \
from N to N, where N is the set of natural numbers. And one can think of \
Turing machines in those terms. However, most of the success of the Turing \
model is that it did not only successfully capture the seminal concept of \
computation as the others also did, but it does it in more explanatory terms, \
as  history has shown by favoring it in a great extent over the others. \
Introducing elements such as a head and a tape has allowed people to better \
understand what is underneath, and finally accept what the Turing model \
explains, what mechanically and intuitively we call computation (modulo the \
Church-Turing thesis). Moreover, the intuitive relation with a physical \
device with pedagogical qualities that would be lost in behalf of a higher \
abstraction if one disposes of them.\
\>", "Text",
 CellChangeTimes->{{3.401373605659685*^9, 3.401373660667788*^9}, {
   3.4013743202814198`*^9, 3.401374320776387*^9}, 3.4016065559285603`*^9, {
   3.401635890370946*^9, 3.401635890998131*^9}, {3.401636354104484*^9, 
   3.401636626485312*^9}, {3.4017253803705463`*^9, 3.401725448988797*^9}},
 TextJustification->1.],

Cell[CellGroupData[{

Cell["Halting state vs. unbounded computation", "Subsection",
 CellChangeTimes->{{3.401373605659685*^9, 3.401373676388452*^9}, 
   3.4013743211723948`*^9, {3.401566046779655*^9, 3.401566059455983*^9}}],

Cell["\<\
It has been agreed, not without some initial reluctance, that halting states \
as an special state in the set Q of states of a Turing machine that tells the \
machine to halt, is an arbitrary element in the minimal description of a \
Turing machine that can be taken away so the Turing machine would remain a \
Turing machine that potentially would compute up to reach a special halting \
configuration. That was pushed and evidenced through other studied systems \
behaving in a similar fashion such as tag systems itself that can meet other \
termination criteria, or for cellular automata for which, in general, no \
clear termination exists other than an arbitrary termination step. Since the \
universality proof of rule 110 cellular automata, the concept of universality \
was no longer necessarily associated to a proof of undecidability of its \
halting state. Other concepts have come since, such as partial halting \
problems and unbounded computation as in the study of cellular automata. In \
the same way, one would be able to wonder where a computation begins and if \
it is not just a continuation of another. A consequence of the arbitrariness \
of the halting state is therefore the arbitrariness of the starting state \
since the starting state could be any other step between, such as in the case \
for the halting. \
\>", "Text",
 CellChangeTimes->{{3.401373605659685*^9, 3.40137366750023*^9}, {
  3.401374320835338*^9, 3.401374321121876*^9}, {3.40163665147209*^9, 
  3.4016367218016567`*^9}, {3.401636783963331*^9, 3.401636867461379*^9}, {
  3.401725505344102*^9, 3.4017256311422358`*^9}, {3.415489603537973*^9, 
  3.4154896198344183`*^9}},
 TextJustification->1.],

Cell[CellGroupData[{

Cell["Cellular automaton rule 110 arbitrary halted after 10 steps", \
"Subsubsection",
 CellChangeTimes->{{3.401373605659685*^9, 3.401373676388452*^9}, 
   3.4013743211723948`*^9, {3.401566469424124*^9, 3.401566509710493*^9}, {
   3.401566816059948*^9, 3.401566859753483*^9}, {3.4015668942509747`*^9, 
   3.401566922018914*^9}, {3.40156706989191*^9, 3.401567087888564*^9}, {
   3.4015671500453863`*^9, 3.401567150154702*^9}}],

Cell[CellGroupData[{

Cell[BoxData[
 RowBox[{"ArrayPlot", "[", 
  RowBox[{
   RowBox[{"CellularAutomaton", "[", 
    RowBox[{"110", ",", " ", 
     RowBox[{"{", 
      RowBox[{
       RowBox[{"{", "1", "}"}], ",", " ", "0"}], "}"}], ",", " ", "10"}], 
    "]"}], ",", " ", 
   RowBox[{"Mesh", " ", "->", " ", "All"}], ",", " ", 
   RowBox[{"ImageSize", " ", "->", " ", "200"}]}], "]"}]], "Input",
 CellGroupingRules->{GroupTogetherGrouping, 10000.},
 CellChangeTimes->{{3.401567022583529*^9, 3.4015670819139633`*^9}, {
   3.401567137708797*^9, 3.401567145804267*^9}, 3.4015672280013123`*^9}],

Cell[BoxData[
 GraphicsBox[{
   RasterBox[{{0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 0}, {1, 0, 0, 1, 1, 1, 1, 1, 0, 
    0, 0}, {1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0}, {1, 1, 1, 0, 0, 1, 0, 1, 0, 0, 
    0}, {1, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0}, {1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 
    0}, {1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0}, {1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 
    0}, {1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0}, {1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 
    0}, {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0}}, {{0, 0}, {11, 11}}, {0, 1}], {
    {GrayLevel[
      NCache[-1 + GoldenRatio, 0.6180339887498949]], 
     StyleBox[
      LineBox[{{{0, 11}, {11, 11}}, {{0, 10}, {11, 10}}, {{0, 9}, {11, 9}}, {{
       0, 8}, {11, 8}}, {{0, 7}, {11, 7}}, {{0, 6}, {11, 6}}, {{0, 5}, {11, 
       5}}, {{0, 4}, {11, 4}}, {{0, 3}, {11, 3}}, {{0, 2}, {11, 2}}, {{0, 
       1}, {11, 1}}, {{0, 0}, {11, 0}}}],
      Antialiasing->False]}, 
    {GrayLevel[
      NCache[-1 + GoldenRatio, 0.6180339887498949]], 
     StyleBox[
      LineBox[{{{0, 0}, {0, 11}}, {{1, 0}, {1, 11}}, {{2, 0}, {2, 11}}, {{3, 
       0}, {3, 11}}, {{4, 0}, {4, 11}}, {{5, 0}, {5, 11}}, {{6, 0}, {6, 
       11}}, {{7, 0}, {7, 11}}, {{8, 0}, {8, 11}}, {{9, 0}, {9, 11}}, {{10, 
       0}, {10, 11}}, {{11, 0}, {11, 11}}}],
      Antialiasing->False]}}},
  Frame->False,
  FrameLabel->{None, None},
  FrameTicks->{{None, None}, {None, None}},
  ImageSize->200]], "Input",
 CellGroupingRules->{GroupTogetherGrouping, 10000.},
 CellChangeTimes->{{3.4015670461124363`*^9, 3.401567082159615*^9}, {
   3.40156714279738*^9, 3.401567146404375*^9}, 3.401567228001482*^9}]
}, {2}]]
}, Open  ]],

Cell[CellGroupData[{

Cell["\<\
Turing machine halted after reaching the down-arrow state and a gray cell (an \
arbitrary terminal configuration)\
\>", "Subsubsection",
 CellChangeTimes->{{3.401373605659685*^9, 3.401373676388452*^9}, 
   3.4013743211723948`*^9, {3.401566469424124*^9, 3.401566509710493*^9}, {
   3.401566816059948*^9, 3.401566859753483*^9}, {3.4015668942509747`*^9, 
   3.401566898170621*^9}, {3.401566931189102*^9, 3.4015669647410603`*^9}, {
   3.401567101377408*^9, 3.401567132137714*^9}, {3.4016065746000557`*^9, 
   3.401606669547263*^9}, {3.401636880949869*^9, 3.401636884630069*^9}, {
   3.401645265483964*^9, 3.401645275671495*^9}, {3.401725668658317*^9, 
   3.401725673664299*^9}}],

Cell[CellGroupData[{

Cell[BoxData[{
 RowBox[{
  RowBox[{"TM23GraphicsX", "[", 
   RowBox[{"data_", ",", "tt_", ",", "opts___"}], "]"}], ":=", 
  RowBox[{"ArrayPlot", "[", 
   RowBox[{
    RowBox[{
     RowBox[{
      RowBox[{"Join", "[", 
       RowBox[{
        RowBox[{"{", "0", "}"}], ",", "#", ",", 
        RowBox[{"{", "0", "}"}]}], "]"}], "&"}], "/@", 
     RowBox[{"Last", "/@", "data"}]}], ",", "opts", ",", 
    RowBox[{"Epilog", "\[Rule]", 
     RowBox[{"{", 
      RowBox[{
       RowBox[{"{", 
        RowBox[{
         RowBox[{"FaceForm", "[", 
          RowBox[{"Opacity", "[", "0", "]"}], "]"}], ",", 
         RowBox[{"EdgeForm", "[", 
          RowBox[{"Directive", "[", 
           RowBox[{
            RowBox[{"Thickness", "[", ".02", "]"}], ",", "Red"}], "]"}], 
          "]"}], ",", 
         RowBox[{
          RowBox[{
           RowBox[{"Rectangle", "[", 
            RowBox[{"#", ",", 
             RowBox[{"#", "+", "1"}]}], "]"}], "&"}], "[", 
          RowBox[{"{", 
           RowBox[{
            RowBox[{"data", "[", 
             RowBox[{"[", 
              RowBox[{"tt", ",", "1", ",", "2"}], "]"}], "]"}], ",", 
            RowBox[{
             RowBox[{"Length", "[", "data", "]"}], "-", "tt"}]}], "}"}], 
          "]"}]}], "}"}], ",", 
       RowBox[{"{", 
        RowBox[{"LightGray", ",", 
         RowBox[{"Rectangle", "[", 
          RowBox[{
           RowBox[{"{", 
            RowBox[{"0", ",", "0"}], "}"}], ",", 
           RowBox[{"{", 
            RowBox[{
             RowBox[{"2", "+", 
              RowBox[{"Length", "[", 
               RowBox[{"data", "[", 
                RowBox[{"[", 
                 RowBox[{"1", ",", "2"}], "]"}], "]"}], "]"}]}], ",", 
             RowBox[{
              RowBox[{"Length", "[", "data", "]"}], "-", "tt", "-", "1"}]}], 
            "}"}]}], "]"}]}], "}"}], ",", 
       RowBox[{"MapIndexed", "[", 
        RowBox[{
         RowBox[{
          RowBox[{"Translate", "[", 
           RowBox[{
            RowBox[{"Rotate", "[", 
             RowBox[{
              RowBox[{"With", "[", 
               RowBox[{
                RowBox[{"{", 
                 RowBox[{"r", "=", ".18"}], "}"}], ",", 
                RowBox[{"{", 
                 RowBox[{
                  RowBox[{"Disk", "[", 
                   RowBox[{
                    RowBox[{"{", 
                    RowBox[{"0", ",", "0"}], "}"}], ",", "r"}], "]"}], ",", 
                  RowBox[{"Polygon", "[", 
                   RowBox[{"{", 
                    RowBox[{
                    RowBox[{"{", 
                    RowBox[{"r", ",", "0"}], "}"}], ",", 
                    RowBox[{"{", 
                    RowBox[{
                    RowBox[{"-", "r"}], ",", "0"}], "}"}], ",", 
                    RowBox[{"{", 
                    RowBox[{"0", ",", ".6"}], "}"}], ",", 
                    RowBox[{"{", 
                    RowBox[{"r", ",", "0"}], "}"}]}], "}"}], "]"}]}], "}"}]}],
                "]"}], ",", 
              RowBox[{"2", 
               RowBox[{"(", 
                RowBox[{
                 RowBox[{"#", "[", 
                  RowBox[{"[", 
                   RowBox[{"1", ",", "1"}], "]"}], "]"}], "+", "1"}], ")"}], 
               RowBox[{"\[Pi]", "/", "2"}]}], ",", 
              RowBox[{"{", 
               RowBox[{"0", ",", "0"}], "}"}]}], "]"}], ",", 
            RowBox[{"{", 
             RowBox[{
              RowBox[{
               RowBox[{"#", "[", 
                RowBox[{"[", 
                 RowBox[{"1", ",", "2"}], "]"}], "]"}], "+", 
               RowBox[{"1", "/", "2"}]}], ",", 
              RowBox[{
               RowBox[{"Length", "[", "data", "]"}], "-", 
               RowBox[{"First", "[", "#2", "]"}], "+", 
               RowBox[{"1", "/", "2"}]}]}], "}"}]}], "]"}], "&"}], ",", 
         RowBox[{"Take", "[", 
          RowBox[{"data", ",", "tt"}], "]"}]}], "]"}]}], "}"}]}]}], 
   "]"}]}], "\n", 
 RowBox[{
  RowBox[{"TuringMarker", "[", 
   RowBox[{"coord_List", ",", 
    RowBox[{"{", 
     RowBox[{"s_Integer", ",", "stot_Integer"}], "}"}]}], "]"}], ":=", 
  RowBox[{"With", "[", 
   RowBox[{
    RowBox[{"{", 
     RowBox[{
      RowBox[{"rot", "=", 
       RowBox[{
        RowBox[{"(", 
         RowBox[{
          RowBox[{"{", 
           RowBox[{
            RowBox[{"{", 
             RowBox[{
              RowBox[{"Cos", "[", "#1", "]"}], ",", 
              RowBox[{"Sin", "[", "#1", "]"}]}], "}"}], ",", 
            RowBox[{"{", 
             RowBox[{
              RowBox[{"-", 
               RowBox[{"Sin", "[", "#1", "]"}]}], ",", 
              RowBox[{"Cos", "[", "#1", "]"}]}], "}"}]}], "}"}], "&"}], ")"}],
         "[", 
        RowBox[{"N", "[", 
         RowBox[{
          RowBox[{"(", 
           RowBox[{"2", " ", 
            RowBox[{"(", 
             RowBox[{"s", "-", "1"}], ")"}], " ", "\[Pi]"}], ")"}], "/", 
          "stot"}], "]"}], "]"}]}], ",", 
      RowBox[{"r", "=", "0.18"}]}], "}"}], ",", 
    RowBox[{"{", 
     RowBox[{
      RowBox[{"GrayLevel", "[", "0", "]"}], ",", 
      RowBox[{"Disk", "[", 
       RowBox[{"coord", ",", "r"}], "]"}], ",", 
      RowBox[{"If", "[", 
       RowBox[{
        RowBox[{"s", ">", "0"}], ",", 
        RowBox[{"Polygon", "[", 
         RowBox[{
          RowBox[{"(", 
           RowBox[{
            RowBox[{"coord", "+", 
             RowBox[{"rot", ".", "#1"}]}], "&"}], ")"}], "/@", 
          RowBox[{"{", 
           RowBox[{
            RowBox[{"{", 
             RowBox[{"r", ",", "0"}], "}"}], ",", 
            RowBox[{"{", 
             RowBox[{
              RowBox[{"-", "r"}], ",", "0"}], "}"}], ",", 
            RowBox[{"{", 
             RowBox[{"0", ",", ".6"}], "}"}], ",", 
            RowBox[{"{", 
             RowBox[{"r", ",", "0"}], "}"}]}], "}"}]}], "]"}], ",", 
        RowBox[{"{", "}"}]}], "]"}]}], "}"}]}], "]"}]}], "\n", 
 RowBox[{"TM23GraphicsX", "[", 
  RowBox[{
   RowBox[{"TuringMachine", "[", 
    RowBox[{
     RowBox[{"{", 
      RowBox[{"596440", ",", "2", ",", "3"}], "}"}], ",", 
     RowBox[{"{", 
      RowBox[{"1", ",", 
       RowBox[{"{", 
        RowBox[{
         RowBox[{"{", "}"}], ",", "0"}], "}"}]}], "}"}], ",", "8"}], "]"}], 
   ",", "8", ",", 
   RowBox[{"Mesh", "\[Rule]", "True"}], ",", 
   RowBox[{"ImageSize", "\[Rule]", 
    RowBox[{"{", 
     RowBox[{"Automatic", ",", "200"}], "}"}]}]}], "]"}]}], "Input",
 CellChangeTimes->{{3.3876780049196014`*^9, 3.3876780571390195`*^9}, 
   3.387678350611526*^9, {3.3877498362248926`*^9, 3.387749841771838*^9}, 
   3.3877498782879305`*^9, 3.3877500188991055`*^9, {3.401566088944282*^9, 
   3.4015661688545103`*^9}, {3.401566205517345*^9, 3.401566330957231*^9}, {
   3.401566366104685*^9, 3.401566398270636*^9}, {3.401566449284144*^9, 
   3.401566449580971*^9}, {3.4015665356475286`*^9, 3.4015667204448643`*^9}, {
   3.401566751292696*^9, 3.401566779322405*^9}, {3.401566982125515*^9, 
   3.40156701262869*^9}},
 CellID->1440177572],

Cell[BoxData[
 GraphicsBox[{
   RasterBox[{{2, 1, 1, 0, 2, 2}, {2, 1, 1, 1, 2, 2}, {2, 1, 2, 1, 2, 2}, {2, 
    1, 2, 0, 2, 2}, {2, 1, 0, 0, 2, 2}, {2, 2, 0, 0, 2, 2}, {2, 2, 1, 0, 2, 
    2}, {2, 2, 1, 2, 2, 2}, {2, 2, 2, 2, 2, 2}}, {{0, 0}, {6, 9}}, {0, 2}], {
    {GrayLevel[
      NCache[-1 + GoldenRatio, 0.6180339887498949]], 
     StyleBox[
      LineBox[{{{0, 9}, {6, 9}}, {{0, 8}, {6, 8}}, {{0, 7}, {6, 7}}, {{0, 
       6}, {6, 6}}, {{0, 5}, {6, 5}}, {{0, 4}, {6, 4}}, {{0, 3}, {6, 3}}, {{0,
        2}, {6, 2}}, {{0, 1}, {6, 1}}, {{0, 0}, {6, 0}}}],
      Antialiasing->False]}, 
    {GrayLevel[
      NCache[-1 + GoldenRatio, 0.6180339887498949]], 
     StyleBox[
      LineBox[{{{0, 0}, {0, 9}}, {{1, 0}, {1, 9}}, {{2, 0}, {2, 9}}, {{3, 
       0}, {3, 9}}, {{4, 0}, {4, 9}}, {{5, 0}, {5, 9}}, {{6, 0}, {6, 9}}}],
      Antialiasing->False]}}},
  Epilog->{{
     FaceForm[
      Opacity[0]], 
     EdgeForm[
      Directive[
       Thickness[0.02], 
       RGBColor[1, 0, 0]]], 
     RectangleBox[{3, 1}, {4, 2}]}, {
     GrayLevel[0.85], 
     RectangleBox[{0, 0}, {6, 0}]}, {
     GeometricTransformationBox[
      GeometricTransformationBox[{
        DiskBox[{0, 0}, 0.18], 
        PolygonBox[{{0.18, 0}, {-0.18, 0}, {0, 0.6}, {0.18, 0}}]}, {{{1, 0}, {
        0, 1}}, {0, 0}}], 
      NCache[{
        Rational[5, 2], 
        Rational[17, 2]}, {2.5, 8.5}]], 
     GeometricTransformationBox[
      GeometricTransformationBox[{
        DiskBox[{0, 0}, 0.18], 
        PolygonBox[{{0.18, 0}, {-0.18, 0}, {0, 0.6}, {0.18, 0}}]}, {{{-1, 
        0}, {0, -1}}, {0, 0}}], 
      NCache[{
        Rational[7, 2], 
        Rational[15, 2]}, {3.5, 7.5}]], 
     GeometricTransformationBox[
      GeometricTransformationBox[{
        DiskBox[{0, 0}, 0.18], 
        PolygonBox[{{0.18, 0}, {-0.18, 0}, {0, 0.6}, {0.18, 0}}]}, {{{1, 0}, {
        0, 1}}, {0, 0}}], 
      NCache[{
        Rational[5, 2], 
        Rational[13, 2]}, {2.5, 6.5}]], 
     GeometricTransformationBox[
      GeometricTransformationBox[{
        DiskBox[{0, 0}, 0.18], 
        PolygonBox[{{0.18, 0}, {-0.18, 0}, {0, 0.6}, {0.18, 0}}]}, {{{1, 0}, {
        0, 1}}, {0, 0}}], 
      NCache[{
        Rational[3, 2], 
        Rational[11, 2]}, {1.5, 5.5}]], 
     GeometricTransformationBox[
      GeometricTransformationBox[{
        DiskBox[{0, 0}, 0.18], 
        PolygonBox[{{0.18, 0}, {-0.18, 0}, {0, 0.6}, {0.18, 0}}]}, {{{-1, 
        0}, {0, -1}}, {0, 0}}], 
      NCache[{
        Rational[5, 2], 
        Rational[9, 2]}, {2.5, 4.5}]], 
     GeometricTransformationBox[
      GeometricTransformationBox[{
        DiskBox[{0, 0}, 0.18], 
        PolygonBox[{{0.18, 0}, {-0.18, 0}, {0, 0.6}, {0.18, 0}}]}, {{{1, 0}, {
        0, 1}}, {0, 0}}], 
      NCache[{
        Rational[7, 2], 
        Rational[7, 2]}, {3.5, 3.5}]], 
     GeometricTransformationBox[
      GeometricTransformationBox[{
        DiskBox[{0, 0}, 0.18], 
        PolygonBox[{{0.18, 0}, {-0.18, 0}, {0, 0.6}, {0.18, 0}}]}, {{{1, 0}, {
        0, 1}}, {0, 0}}], 
      NCache[{
        Rational[5, 2], 
        Rational[5, 2]}, {2.5, 2.5}]], 
     GeometricTransformationBox[
      GeometricTransformationBox[{
        DiskBox[{0, 0}, 0.18], 
        PolygonBox[{{0.18, 0}, {-0.18, 0}, {0, 0.6}, {0.18, 0}}]}, {{{-1, 
        0}, {0, -1}}, {0, 0}}], 
      NCache[{
        Rational[7, 2], 
        Rational[3, 2]}, {3.5, 1.5}]]}},
  Frame->False,
  FrameLabel->{None, None},
  FrameTicks->{{None, None}, {None, None}},
  ImageSize->{Automatic, 200}]], "Output",
 CellChangeTimes->{
  3.4015661707863207`*^9, 3.401566206882661*^9, {3.401566247872254*^9, 
   3.4015662941742697`*^9}, {3.4015663509470997`*^9, 3.401566398901657*^9}, 
   3.401566449889226*^9, {3.401566536544142*^9, 3.401566720819687*^9}, {
   3.4015667519004087`*^9, 3.401566779721291*^9}, {3.401566987554455*^9, 
   3.401567012935961*^9}}]
}, {2}]]
}, Open  ]]
}, Open  ]],

Cell[CellGroupData[{

Cell["Unbounded vs. infinite tape", "Subsection",
 CellChangeTimes->{{3.401373605659685*^9, 3.401373676388452*^9}, 
   3.4013743211723948`*^9}],

Cell["\<\
Being that 2,3 Turing machine universal one would fairly ask to perform and \
show an actual computation, let's say that we want to feed the machine with \
some encoding of the arithmetic operation 2^2 and get the correct answer 4. \
One has to bear in mind that these devices are already so small that any \
encoding of even very simple operations require a lot of effort under the \
description of the proof, but that doesn't mean that there is no other way to \
compute that operation with the same machine in a simpler way.

A suitable encoding is initially required because one would need to be able \
to encode by hand such an initial condition, recalling that the difficulty \
resides in the lack of  elements and rules--the product of the colors and \
states--to describe something intuitively meaningful for us. Even if you find \
a simple intuitive encoding for that operation, if you want to perform any \
other you would require to find or build another different encoding unless \
you come up with a general suitable encoding just as the one used for the 2,3 \
Turing machine proof letting it to behave universal. Then you probably could \
conceive a compiler, either with your own encoding or the encoding in the \
current proof including a translation between the tag system and any \
expression in regular mathematical language or any other high-level \
programming language. A fair question to make is of course whether or not \
such a compiler or the Turing machine itself would be computationally \
efficient. And the relationship between universality and complexity classes \
at the border of decidability has begun to be recently discussed in this same \
context and we will say more, regarding the 2,3 Turing machine, below. 

For descriptions of a Turing machine, it is often found that they are \
provided with unbounded tapes, whether to one or both directions. This is \
somehow tricky and unleashes an old debate with philosophical and practical \
content. If one allows an actual infinity one can easily wonder if the model \
is longer feasible since nothing seems to suggest that we can use or take \
advantage of any non-finite element in physical terms. Even if one is not \
intending to construct a Turing machine but to think of such kinf of \
computation around, one could still wonder if such a \"natural\" Turing \
machine would have access to an infinite source, if so, then the Turing \
machine would also easily reach capabilities beyond the characteristic power \
of the Turing machine model. One way to overcome these troubles (neither \
being able to provide a finite tape nor an actual inifinite tape) is by \
allowing the tape to grow indefinitely in length. In favor of that term, one \
can put all digital computers into that class by thinking that it is always \
possible to provide the machine with some extra memory as long as the \
computation need it. But the concept in question, if the tape is actually \
infinite or not, has a lot to do with the actual content of the tape. When \
the tape is filled with a \"blank\" color, one is actually filling it. How is \
that would be compatible with the notion of a finite configuration or initial \
condition? Well, the way to round the problem is by thinking that the \
supposed color is actually the physical background that supports the Turing \
machine computation and that it does not play any particular role other than \
supporting it. And that is also compatible with both cases, either \
constructing such a device, like a digital computer, or finding one around as \
a representation of a physical phenomena.\
\>", "Text",
 CellChangeTimes->{{3.401373605659685*^9, 3.401373683316606*^9}, {
   3.401374321231284*^9, 3.401374322130982*^9}, {3.4013743914961977`*^9, 
   3.4013743936968822`*^9}, {3.401553025357498*^9, 3.401553042853986*^9}, 
   3.401565980948505*^9, {3.4016369848317013`*^9, 3.401637021945608*^9}, {
   3.4016370600809193`*^9, 3.401637202713232*^9}, {3.4016372562383757`*^9, 
   3.401637324936459*^9}, {3.401637355920615*^9, 3.401637377191057*^9}, {
   3.401637409777773*^9, 3.401637435709538*^9}, {3.4016374684137697`*^9, 
   3.401637468697857*^9}, {3.401637707950136*^9, 3.401637749640031*^9}, {
   3.401638025808766*^9, 3.401638122632348*^9}, {3.40163816046052*^9, 
   3.401638187753221*^9}, {3.401638253763259*^9, 3.401638308716707*^9}, {
   3.401638362948988*^9, 3.401638418971439*^9}, {3.401638471398796*^9, 
   3.401638639295916*^9}, {3.40163868088993*^9, 3.401638969641282*^9}, {
   3.4016390891093884`*^9, 3.401639098117646*^9}, {3.401639511253438*^9, 
   3.401639523545733*^9}, {3.4016418959263573`*^9, 3.401641956673377*^9}, {
   3.40164257150076*^9, 3.401642574339963*^9}, 3.401644442109459*^9, {
   3.4016455127172613`*^9, 3.40164553103907*^9}, {3.401725723871428*^9, 
   3.4017259181163483`*^9}},
 TextJustification->1.]
}, Open  ]],

Cell[CellGroupData[{

Cell["\"blank\" symbol vs. arbitrary background", "Subsection",
 CellChangeTimes->{{3.401373605659685*^9, 3.4013736913324213`*^9}, 
   3.4013743221652737`*^9}],

Cell["\<\
Over the years, small universal machines were given for a number of variants \
on the standard model that in principle preserve the essence and most minimal \
technical requirements on computation and universality. One variation on the \
standard model is, for instance, to allow the \"blank\"  symbol of the Turing \
machine\[CloseCurlyQuote]s tape to be an infinitely repeated word to one or \
both sides of the tape.

One can imagine feeding this machine with finite inputs while the background \
over which the machine operates looks computationaly simple supporting the \
computation but neither doing it nor contributing to the overall \
computational power as we said in the section above.

So one immediate question that one can draw is why changing an infinite \
background of period n=1 \t\[AliasDelimiter]--the \"blank\"--for n>1 would \
matter by also using more colors as long as the content of the tape remains \
computationally simple. Let's dig further into that matter:

Let's define a couple (M,A) of 2 automata M and A with M={S,C} where S is the \
set of states and C the set of colors, and A={s,c} where s is a subset of S \
and c a subset of C. Then we will say that M and A are compatible since they \
have compatible states and colors, i.e. states and colors that both can \
syntactically manipulate. And let's assume that the couple (M,A) is proved to \
be universal, and that A is proved to be not, does that imply that M is \
universal? Not necessarily, that depends on how important is A in the \
operation of (M,A). If M is universal by its own, it shouldn' t be necessary \
to keep A. But if A interacts with M at every step t, then M cannot reach \
universality by itself but with external help. On the other hand, if A is \
used to feed M at t=1, A is a translator of M from the output of another \
system into the vocabulary of M in terms of S and C. Therefore, if A is not \
universal and does not intervene in any other step but t=1 then M stands for \
the computational power of the couple (M,A), i.e. it is universal. 

An auxiliary machine like A could be, for instance, a finite automaton \
generating a tape with a background for M. The role of A in Alex Smith's \
proof for the Wolfram's 2,3 Turing machine consists in translating rather \
than computing. However, even when the background is computationally simple, \
the simplicity of the 2,3 Turing machine is impaired by its extensive \
operation-dependent processing of the sequential cyclic tag-system that \
emulates and a direct consequence of the lack of elements SxC. A cyclic tag \
system is a tag system in which the list of rules is applied in sequential \
order.  

The useful part can be therefore recognized by the bounds determined by the \
background and the background actually works as a support for the computation \
itself. Minsky required initially finite-length initial conditions over a \
tape filled with a repetitive \"blank\" character. Later, others allowed and \
proposed infinite but repetitive backgrounds which was already a common \
situation in the study of cellular automata from which rule 110 took \
advantage for its own universality  proof. Alex Smith is pushing this \
generalization further up to its border by allowing non-repetitive \
backgrounds. By emulating a sequence of computational systems Smith proves \
that the 2,3 Turing machine by emulating any 2-color tag systems for an \
arbitrary number of steps, using a finite-length initial condition defining \
an initial condition in which only finitely many cells are relevant, and no \
other cells are visited during the evolution of that initial condition.

Basically the possible scenarios consist in adding a condition of background \
with an unbounded simple pattern going all along the tape surrounding the \
\"meaningful\" part (the actual input for M). This special pattern or (also \
called word) is constituted by a subset of the set of colors C filling the \
unbounded tape as follows: a repeated pattern to the left of the actual input \
and another pattern repeated to the right of the input word, i.e. at the \
initial configuration the tape looks like . . .LLLLLwRRRRR. . . where w is \
the input for M and L and R are arbitrary patterns or \"blank\" words over \
the tape, all w, R and L belonging, when decomposed, to the set of colors C. \
Furthermore, the configuration of the tape can look as LwR with L and R \
non-repetitive backgrounds but produced by A, the non-universal device.

In accordance to Martin Davis definition of universality from the paper cited \
in the bibliography, a condition that must be added is that the encoding \
itself be computationally simple. For there would not be much point of \
claiming universality for a Turing machine for which the encoding would \
require another universal machine to carry it out. The problem is then to \
encode the computation in terms of M such that the encoding itself does not \
require another universal machine. So even when the state of the tape could \
look rather sophisticated since the beginning, it is computationally speaking \
very simple.

This proof extends what is done in systems such as cellular automata and by \
doing so one can even go further asking which other systems could benefit \
from this in a reasonable and sound way. Alex Smith's use of non-periodic \
backgrounds is a natural generalization of the sort of ideas in Wolfram's New \
Kind of Science, and somebody was bound to make that generalization \
eventually. As I suggested above, this considerations approaches a more \
natural and closer connection with physical reality and physical constraints \
which is by itself a rich field of further analysis. \
\>", "Text",
 CellChangeTimes->{{3.401373605659685*^9, 3.401373696532996*^9}, {
   3.401374322246167*^9, 3.4013743244656*^9}, {3.401552967479301*^9, 
   3.4015530181145887`*^9}, 3.4015606648659067`*^9, {3.40163202736395*^9, 
   3.401632038385322*^9}, 3.4016375239795027`*^9, {3.401637559731948*^9, 
   3.401637686417245*^9}, {3.401638981046916*^9, 3.4016390073918877`*^9}, {
   3.401639065707103*^9, 3.401639134439904*^9}, {3.401639252431896*^9, 
   3.401639403768371*^9}, 3.401639470010066*^9, {3.4016396797853737`*^9, 
   3.401639872998804*^9}, {3.401639985947464*^9, 3.4016401240920963`*^9}, {
   3.401641758289229*^9, 3.401641864424505*^9}, {3.401642204939803*^9, 
   3.401642504036861*^9}, {3.401642534725066*^9, 3.401642548795157*^9}, {
   3.4016425802216578`*^9, 3.4016429411080017`*^9}, {3.401642983032551*^9, 
   3.401642984866501*^9}, {3.401643394347293*^9, 3.401643395009858*^9}, {
   3.4016444501904287`*^9, 3.40164462740911*^9}, {3.4016455755387383`*^9, 
   3.401645694525725*^9}, {3.401646588750939*^9, 3.401646696271721*^9}, {
   3.401646780944976*^9, 3.401647067354594*^9}, {3.401648414114609*^9, 
   3.401648447179932*^9}, {3.4016485459294777`*^9, 3.401648546038569*^9}, {
   3.401648627099052*^9, 3.401648632356805*^9}, {3.401648684589407*^9, 
   3.401648743248493*^9}, {3.401648775015038*^9, 3.4016490132322206`*^9}, {
   3.401649319665441*^9, 3.401649420125188*^9}, {3.401649454857766*^9, 
   3.4016494972075768`*^9}, {3.4016495512862043`*^9, 3.401649601346365*^9}, {
   3.401649633430893*^9, 3.4016498311931953`*^9}, {3.4016537803929234`*^9, 
   3.4016539000485563`*^9}, {3.401654033322886*^9, 3.401654058261335*^9}, {
   3.401654096201886*^9, 3.40165427484439*^9}, {3.401654320854806*^9, 
   3.401654322557786*^9}, {3.401654353063448*^9, 3.401654395555151*^9}, {
   3.401717741173319*^9, 3.401717742793244*^9}, {3.4154895593477182`*^9, 
   3.41548958769243*^9}},
 TextJustification->1.]
}, Open  ]],

Cell[CellGroupData[{

Cell["On the feasibility of non-periodic configurations", "Subsection",
 CellChangeTimes->{{3.401373605659685*^9, 3.401373698797036*^9}, {
   3.401374011479559*^9, 3.401374021951687*^9}, 3.4015530647624683`*^9, {
   3.401560569343932*^9, 3.4015605727307167`*^9}, 3.401560618666727*^9, {
   3.401560884297031*^9, 3.401560884712322*^9}, 3.401632023747116*^9, {
   3.401653653796423*^9, 3.401653660015914*^9}}],

Cell["\<\
As explained above these particular kind of backgrounds not playing a main \
role in the computation can  be defined as generated by a computationally \
simple program so one can provide the Turing machine with a tape filled with \
the suitable pattern without having to perform any further computation. One \
can think that the process is tantamount to filling an unbounded tape with a \
blank, it doesn' t matter how you color the tape, as far that that color \
doesn't encode the actual computation nor performs it by itself. Therefore, \
one can think about it as the support over which the machine operates, just \
as the same role the blank plays in the traditional model. This approachs \
seems even more closer to possible physical constraints since one can think \
in computations having place around over some kind of background/noise and \
not over \"blank\" fixed tapes. In other terms, one can think on the process \
as providing a filled tape with a sequence of symbols previously calculated \
or calculated just before the actual computation simple enough to be able to \
provide with more tape as the computation requires, just as it does for the \
\"blank tape\".\
\>", "Text",
 CellChangeTimes->{{3.4015606573095303`*^9, 3.401561088442252*^9}, {
   3.401567294922907*^9, 3.401567309352871*^9}, {3.401567346266193*^9, 
   3.401567425836833*^9}, {3.401653332065332*^9, 3.401653490786932*^9}, 
   3.401653727251823*^9, 3.4016574135408907`*^9},
 TextJustification->1.],

Cell["\<\
Computationally simple backgrounds (initial fragments of one-directional \
tapes) :
 \
\>", "Text",
 CellChangeTimes->{{3.401564773029211*^9, 3.401564783646996*^9}, 
   3.401564815599434*^9, {3.401565226307393*^9, 3.401565232560734*^9}, 
   3.401567274303268*^9, {3.4016349055694437`*^9, 3.4016349100411386`*^9}, {
   3.401645723014525*^9, 3.401645738854751*^9}, {3.401653713740553*^9, 
   3.4016537146171217`*^9}}],

Cell[CellGroupData[{

Cell["\<\
The traditional \"blank\" tape, with \"blank\" as an actual white color.\
\>", "Subsubsection",
 CellChangeTimes->{{3.401564773029211*^9, 3.401564783646996*^9}, {
  3.401564815599434*^9, 3.401564834959704*^9}, {3.401564930813395*^9, 
  3.401564941077392*^9}, {3.4015672800631227`*^9, 3.4015672803268433`*^9}, {
  3.4016537405592203`*^9, 3.4016537690592117`*^9}}],

Cell[CellGroupData[{

Cell[BoxData[
 RowBox[{"Row", "[", 
  RowBox[{"{", 
   RowBox[{
    RowBox[{"ArrayPlot", "[", 
     RowBox[{
      RowBox[{"{", 
       RowBox[{"Table", "[", 
        RowBox[{"White", ",", " ", 
         RowBox[{"{", "30", "}"}]}], "]"}], "}"}], ",", " ", 
      RowBox[{"Mesh", " ", "->", " ", "All"}], ",", " ", 
      RowBox[{"ImageSize", " ", "->", " ", "600"}]}], "]"}], ",", 
    "\"\<. . .\>\""}], "}"}], "]"}]], "Code",
 CellChangeTimes->{{3.4015627109591827`*^9, 3.40156272302815*^9}, {
  3.401562762091845*^9, 3.401562791570455*^9}, {3.401562883026375*^9, 
  3.4015628880583553`*^9}, {3.401564589894164*^9, 3.401564617442624*^9}, {
  3.4015650389127398`*^9, 3.401565040042852*^9}, {3.401634924877717*^9, 
  3.4016349761812773`*^9}}],

Cell[BoxData[
 InterpretationBox[
  RowBox[{
   GraphicsBox[{
     RasterBox[{{{1., 1., 1.}, {1., 1., 1.}, {1., 1., 1.}, {1., 1., 1.}, {1., 
      1., 1.}, {1., 1., 1.}, {1., 1., 1.}, {1., 1., 1.}, {1., 1., 1.}, {1., 
      1., 1.}, {1., 1., 1.}, {1., 1., 1.}, {1., 1., 1.}, {1., 1., 1.}, {1., 
      1., 1.}, {1., 1., 1.}, {1., 1., 1.}, {1., 1., 1.}, {1., 1., 1.}, {1., 
      1., 1.}, {1., 1., 1.}, {1., 1., 1.}, {1., 1., 1.}, {1., 1., 1.}, {1., 
      1., 1.}, {1., 1., 1.}, {1., 1., 1.}, {1., 1., 1.}, {1., 1., 1.}, {1., 
      1., 1.}}}, {{0, 0}, {30, 1}}, {0, 1}], {
      {GrayLevel[
        NCache[-1 + GoldenRatio, 0.6180339887498949]], 
       StyleBox[LineBox[{{{0, 1}, {30, 1}}, {{0, 0}, {30, 0}}}],
        Antialiasing->False]}, 
      {GrayLevel[
        NCache[-1 + GoldenRatio, 0.6180339887498949]], 
       StyleBox[
        LineBox[{{{0, 0}, {0, 1}}, {{1, 0}, {1, 1}}, {{2, 0}, {2, 1}}, {{3, 
         0}, {3, 1}}, {{4, 0}, {4, 1}}, {{5, 0}, {5, 1}}, {{6, 0}, {6, 1}}, {{
         7, 0}, {7, 1}}, {{8, 0}, {8, 1}}, {{9, 0}, {9, 1}}, {{10, 0}, {10, 
         1}}, {{11, 0}, {11, 1}}, {{12, 0}, {12, 1}}, {{13, 0}, {13, 1}}, {{
         14, 0}, {14, 1}}, {{15, 0}, {15, 1}}, {{16, 0}, {16, 1}}, {{17, 0}, {
         17, 1}}, {{18, 0}, {18, 1}}, {{19, 0}, {19, 1}}, {{20, 0}, {20, 
         1}}, {{21, 0}, {21, 1}}, {{22, 0}, {22, 1}}, {{23, 0}, {23, 1}}, {{
         24, 0}, {24, 1}}, {{25, 0}, {25, 1}}, {{26, 0}, {26, 1}}, {{27, 0}, {
         27, 1}}, {{28, 0}, {28, 1}}, {{29, 0}, {29, 1}}, {{30, 0}, {30, 
         1}}}],
        Antialiasing->False]}}},
    Frame->False,
    FrameLabel->{None, None},
    FrameTicks->{{None, None}, {None, None}},
    ImageSize->600], "\[InvisibleSpace]", "\<\". . .\"\>"}],
  Row[{
    Graphics[{
      Raster[{{{1., 1., 1.}, {1., 1., 1.}, {1., 1., 1.}, {1., 1., 1.}, {1., 
       1., 1.}, {1., 1., 1.}, {1., 1., 1.}, {1., 1., 1.}, {1., 1., 1.}, {1., 
       1., 1.}, {1., 1., 1.}, {1., 1., 1.}, {1., 1., 1.}, {1., 1., 1.}, {1., 
       1., 1.}, {1., 1., 1.}, {1., 1., 1.}, {1., 1., 1.}, {1., 1., 1.}, {1., 
       1., 1.}, {1., 1., 1.}, {1., 1., 1.}, {1., 1., 1.}, {1., 1., 1.}, {1., 
       1., 1.}, {1., 1., 1.}, {1., 1., 1.}, {1., 1., 1.}, {1., 1., 1.}, {1., 
       1., 1.}}}, {{0, 0}, {30, 1}}, {0, 1}], {{Antialiasing -> False, 
        GrayLevel[-1 + GoldenRatio], 
        Line[{{{0, 1}, {30, 1}}, {{0, 0}, {30, 0}}}]}, {
       Antialiasing -> False, 
        GrayLevel[-1 + GoldenRatio], 
        Line[{{{0, 0}, {0, 1}}, {{1, 0}, {1, 1}}, {{2, 0}, {2, 1}}, {{3, 0}, {
         3, 1}}, {{4, 0}, {4, 1}}, {{5, 0}, {5, 1}}, {{6, 0}, {6, 1}}, {{7, 
         0}, {7, 1}}, {{8, 0}, {8, 1}}, {{9, 0}, {9, 1}}, {{10, 0}, {10, 
         1}}, {{11, 0}, {11, 1}}, {{12, 0}, {12, 1}}, {{13, 0}, {13, 1}}, {{
         14, 0}, {14, 1}}, {{15, 0}, {15, 1}}, {{16, 0}, {16, 1}}, {{17, 0}, {
         17, 1}}, {{18, 0}, {18, 1}}, {{19, 0}, {19, 1}}, {{20, 0}, {20, 
         1}}, {{21, 0}, {21, 1}}, {{22, 0}, {22, 1}}, {{23, 0}, {23, 1}}, {{
         24, 0}, {24, 1}}, {{25, 0}, {25, 1}}, {{26, 0}, {26, 1}}, {{27, 0}, {
         27, 1}}, {{28, 0}, {28, 1}}, {{29, 0}, {29, 1}}, {{30, 0}, {30, 
         1}}}]}}}, Frame -> False, FrameLabel -> {None, None}, 
     FrameTicks -> {{None, None}, {None, None}}, ImageSize -> 600], 
    ". . ."}]]], "Output",
 CellChangeTimes->{3.401634976709642*^9}]
}, Open  ]]
}, Open  ]],

Cell[CellGroupData[{

Cell["A blue-colored \"blank\" tape.", "Subsubsection",
 CellChangeTimes->{{3.401564773029211*^9, 3.401564783646996*^9}, {
   3.401564815599434*^9, 3.401564834959704*^9}, 3.4015649280892267`*^9, {
   3.401564958542143*^9, 3.401564960462336*^9}, {3.401565049586371*^9, 
   3.401565121115715*^9}, {3.401567433204228*^9, 3.401567433603711*^9}, {
   3.4016275716387463`*^9, 3.401627580644185*^9}, 3.401653767499175*^9}],

Cell[CellGroupData[{

Cell[BoxData[
 RowBox[{"Row", "[", 
  RowBox[{"{", 
   RowBox[{
    RowBox[{"ArrayPlot", "[", 
     RowBox[{
      RowBox[{"{", 
       RowBox[{"Table", "[", 
        RowBox[{"LightBlue", ",", " ", 
         RowBox[{"{", "30", "}"}]}], "]"}], "}"}], ",", " ", 
      RowBox[{"Mesh", " ", "->", " ", "All"}], ",", " ", 
      RowBox[{"ImageSize", " ", "->", " ", "600"}]}], "]"}], ",", 
    "\"\<. . .\>\""}], "}"}], "]"}]], "Code",
 CellChangeTimes->{{3.4015627109591827`*^9, 3.40156272302815*^9}, {
  3.401562762091845*^9, 3.401562791570455*^9}, {3.401562883026375*^9, 
  3.4015628880583553`*^9}, {3.401564589894164*^9, 3.401564617442624*^9}, {
  3.40156496331602*^9, 3.40156507345224*^9}, {3.401565124076926*^9, 
  3.4015651245255823`*^9}, {3.401567438639402*^9, 3.40156743940585*^9}, {
  3.401634996994781*^9, 3.4016350033863087`*^9}}],

Cell[BoxData[
 InterpretationBox[
  RowBox[{
   GraphicsBox[{
     RasterBox[{{{0.87, 0.94, 1.}, {0.87, 0.94, 1.}, {0.87, 0.94, 1.}, {0.87, 
      0.94, 1.}, {0.87, 0.94, 1.}, {0.87, 0.94, 1.}, {0.87, 0.94, 1.}, {0.87, 
      0.94, 1.}, {0.87, 0.94, 1.}, {0.87, 0.94, 1.}, {0.87, 0.94, 1.}, {0.87, 
      0.94, 1.}, {0.87, 0.94, 1.}, {0.87, 0.94, 1.}, {0.87, 0.94, 1.}, {0.87, 
      0.94, 1.}, {0.87, 0.94, 1.}, {0.87, 0.94, 1.}, {0.87, 0.94, 1.}, {0.87, 
      0.94, 1.}, {0.87, 0.94, 1.}, {0.87, 0.94, 1.}, {0.87, 0.94, 1.}, {0.87, 
      0.94, 1.}, {0.87, 0.94, 1.}, {0.87, 0.94, 1.}, {0.87, 0.94, 1.}, {0.87, 
      0.94, 1.}, {0.87, 0.94, 1.}, {0.87, 0.94, 1.}}}, {{0, 0}, {30, 1}}, {0, 
      1}], {
      {GrayLevel[
        NCache[-1 + GoldenRatio, 0.6180339887498949]], 
       StyleBox[LineBox[{{{0, 1}, {30, 1}}, {{0, 0}, {30, 0}}}],
        Antialiasing->False]}, 
      {GrayLevel[
        NCache[-1 + GoldenRatio, 0.6180339887498949]], 
       StyleBox[
        LineBox[{{{0, 0}, {0, 1}}, {{1, 0}, {1, 1}}, {{2, 0}, {2, 1}}, {{3, 
         0}, {3, 1}}, {{4, 0}, {4, 1}}, {{5, 0}, {5, 1}}, {{6, 0}, {6, 1}}, {{
         7, 0}, {7, 1}}, {{8, 0}, {8, 1}}, {{9, 0}, {9, 1}}, {{10, 0}, {10, 
         1}}, {{11, 0}, {11, 1}}, {{12, 0}, {12, 1}}, {{13, 0}, {13, 1}}, {{
         14, 0}, {14, 1}}, {{15, 0}, {15, 1}}, {{16, 0}, {16, 1}}, {{17, 0}, {
         17, 1}}, {{18, 0}, {18, 1}}, {{19, 0}, {19, 1}}, {{20, 0}, {20, 
         1}}, {{21, 0}, {21, 1}}, {{22, 0}, {22, 1}}, {{23, 0}, {23, 1}}, {{
         24, 0}, {24, 1}}, {{25, 0}, {25, 1}}, {{26, 0}, {26, 1}}, {{27, 0}, {
         27, 1}}, {{28, 0}, {28, 1}}, {{29, 0}, {29, 1}}, {{30, 0}, {30, 
         1}}}],
        Antialiasing->False]}}},
    Frame->False,
    FrameLabel->{None, None},
    FrameTicks->{{None, None}, {None, None}},
    ImageSize->600], "\[InvisibleSpace]", "\<\". . .\"\>"}],
  Row[{
    Graphics[{
      Raster[{{{0.87, 0.94, 1.}, {0.87, 0.94, 1.}, {0.87, 0.94, 1.}, {0.87, 
       0.94, 1.}, {0.87, 0.94, 1.}, {0.87, 0.94, 1.}, {0.87, 0.94, 1.}, {0.87,
        0.94, 1.}, {0.87, 0.94, 1.}, {0.87, 0.94, 1.}, {0.87, 0.94, 1.}, {
       0.87, 0.94, 1.}, {0.87, 0.94, 1.}, {0.87, 0.94, 1.}, {0.87, 0.94, 
       1.}, {0.87, 0.94, 1.}, {0.87, 0.94, 1.}, {0.87, 0.94, 1.}, {0.87, 0.94,
        1.}, {0.87, 0.94, 1.}, {0.87, 0.94, 1.}, {0.87, 0.94, 1.}, {0.87, 
       0.94, 1.}, {0.87, 0.94, 1.}, {0.87, 0.94, 1.}, {0.87, 0.94, 1.}, {0.87,
        0.94, 1.}, {0.87, 0.94, 1.}, {0.87, 0.94, 1.}, {0.87, 0.94, 1.}}}, {{
       0, 0}, {30, 1}}, {0, 1}], {{Antialiasing -> False, 
        GrayLevel[-1 + GoldenRatio], 
        Line[{{{0, 1}, {30, 1}}, {{0, 0}, {30, 0}}}]}, {
       Antialiasing -> False, 
        GrayLevel[-1 + GoldenRatio], 
        Line[{{{0, 0}, {0, 1}}, {{1, 0}, {1, 1}}, {{2, 0}, {2, 1}}, {{3, 0}, {
         3, 1}}, {{4, 0}, {4, 1}}, {{5, 0}, {5, 1}}, {{6, 0}, {6, 1}}, {{7, 
         0}, {7, 1}}, {{8, 0}, {8, 1}}, {{9, 0}, {9, 1}}, {{10, 0}, {10, 
         1}}, {{11, 0}, {11, 1}}, {{12, 0}, {12, 1}}, {{13, 0}, {13, 1}}, {{
         14, 0}, {14, 1}}, {{15, 0}, {15, 1}}, {{16, 0}, {16, 1}}, {{17, 0}, {
         17, 1}}, {{18, 0}, {18, 1}}, {{19, 0}, {19, 1}}, {{20, 0}, {20, 
         1}}, {{21, 0}, {21, 1}}, {{22, 0}, {22, 1}}, {{23, 0}, {23, 1}}, {{
         24, 0}, {24, 1}}, {{25, 0}, {25, 1}}, {{26, 0}, {26, 1}}, {{27, 0}, {
         27, 1}}, {{28, 0}, {28, 1}}, {{29, 0}, {29, 1}}, {{30, 0}, {30, 
         1}}}]}}}, Frame -> False, FrameLabel -> {None, None}, 
     FrameTicks -> {{None, None}, {None, None}}, ImageSize -> 600], 
    ". . ."}]]], "Output",
 CellChangeTimes->{3.401635004663241*^9}]
}, Open  ]]
}, Open  ]],

Cell[CellGroupData[{

Cell["Other possible repetitive backgrounds.", "Subsubsection",
 CellChangeTimes->{{3.401564773029211*^9, 3.401564783646996*^9}, {
   3.401564815599434*^9, 3.401564834959704*^9}, 3.4015649280892267`*^9, {
   3.401564958542143*^9, 3.401564960462336*^9}, {3.401565049586371*^9, 
   3.401565148468313*^9}, {3.40156745339765*^9, 3.4015674823653173`*^9}, {
   3.4016537541072702`*^9, 3.401653765187182*^9}}],

Cell["\<\
The easiest way to make a recurrent sequence is to form a periodic sequence, \
one where the sequence repeats entirely after a given number m of steps.\
\>", "Text"],

Cell[CellGroupData[{

Cell[BoxData[
 RowBox[{"Row", "[", 
  RowBox[{"{", 
   RowBox[{
    RowBox[{"ArrayPlot", "[", 
     RowBox[{
      RowBox[{"{", 
       RowBox[{"Flatten", "[", 
        RowBox[{"Table", "[", 
         RowBox[{
          RowBox[{"{", 
           RowBox[{"0", ",", "1"}], "}"}], ",", 
          RowBox[{"{", "15", "}"}]}], "]"}], "]"}], "}"}], ",", 
      RowBox[{"Mesh", "->", "All"}], ",", 
      RowBox[{"ImageSize", "\[Rule]", "600"}]}], "]"}], ",", 
    "\"\<. . .\>\""}], "}"}], "]"}]], "Code",
 CellChangeTimes->{{3.401562940622827*^9, 3.4015629828928337`*^9}, {
  3.401563032781674*^9, 3.401563039981379*^9}, {3.4015631716703*^9, 
  3.4015632619225817`*^9}, {3.4015645592937317`*^9, 3.40156456372902*^9}, {
  3.4015646223924913`*^9, 3.401564629307261*^9}, {3.4016350110433817`*^9, 
  3.401635015339024*^9}}],

Cell[BoxData[
 InterpretationBox[
  RowBox[{
   GraphicsBox[{
     RasterBox[{{1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 
      1, 0, 1, 0, 1, 0, 1, 0, 1, 0}}, {{0, 0}, {30, 1}}, {0, 1}], {
      {GrayLevel[
        NCache[-1 + GoldenRatio, 0.6180339887498949]], 
       StyleBox[LineBox[{{{0, 1}, {30, 1}}, {{0, 0}, {30, 0}}}],
        Antialiasing->False]}, 
      {GrayLevel[
        NCache[-1 + GoldenRatio, 0.6180339887498949]], 
       StyleBox[
        LineBox[{{{0, 0}, {0, 1}}, {{1, 0}, {1, 1}}, {{2, 0}, {2, 1}}, {{3, 
         0}, {3, 1}}, {{4, 0}, {4, 1}}, {{5, 0}, {5, 1}}, {{6, 0}, {6, 1}}, {{
         7, 0}, {7, 1}}, {{8, 0}, {8, 1}}, {{9, 0}, {9, 1}}, {{10, 0}, {10, 
         1}}, {{11, 0}, {11, 1}}, {{12, 0}, {12, 1}}, {{13, 0}, {13, 1}}, {{
         14, 0}, {14, 1}}, {{15, 0}, {15, 1}}, {{16, 0}, {16, 1}}, {{17, 0}, {
         17, 1}}, {{18, 0}, {18, 1}}, {{19, 0}, {19, 1}}, {{20, 0}, {20, 
         1}}, {{21, 0}, {21, 1}}, {{22, 0}, {22, 1}}, {{23, 0}, {23, 1}}, {{
         24, 0}, {24, 1}}, {{25, 0}, {25, 1}}, {{26, 0}, {26, 1}}, {{27, 0}, {
         27, 1}}, {{28, 0}, {28, 1}}, {{29, 0}, {29, 1}}, {{30, 0}, {30, 
         1}}}],
        Antialiasing->False]}}},
    Frame->False,
    FrameLabel->{None, None},
    FrameTicks->{{None, None}, {None, None}},
    ImageSize->600], "\[InvisibleSpace]", "\<\". . .\"\>"}],
  Row[{
    Graphics[{
      Raster[{{1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 
       0, 1, 0, 1, 0, 1, 0, 1, 0}}, {{0, 0}, {30, 1}}, {0, 1}], {{
       Antialiasing -> False, 
        GrayLevel[-1 + GoldenRatio], 
        Line[{{{0, 1}, {30, 1}}, {{0, 0}, {30, 0}}}]}, {
       Antialiasing -> False, 
        GrayLevel[-1 + GoldenRatio], 
        Line[{{{0, 0}, {0, 1}}, {{1, 0}, {1, 1}}, {{2, 0}, {2, 1}}, {{3, 0}, {
         3, 1}}, {{4, 0}, {4, 1}}, {{5, 0}, {5, 1}}, {{6, 0}, {6, 1}}, {{7, 
         0}, {7, 1}}, {{8, 0}, {8, 1}}, {{9, 0}, {9, 1}}, {{10, 0}, {10, 
         1}}, {{11, 0}, {11, 1}}, {{12, 0}, {12, 1}}, {{13, 0}, {13, 1}}, {{
         14, 0}, {14, 1}}, {{15, 0}, {15, 1}}, {{16, 0}, {16, 1}}, {{17, 0}, {
         17, 1}}, {{18, 0}, {18, 1}}, {{19, 0}, {19, 1}}, {{20, 0}, {20, 
         1}}, {{21, 0}, {21, 1}}, {{22, 0}, {22, 1}}, {{23, 0}, {23, 1}}, {{
         24, 0}, {24, 1}}, {{25, 0}, {25, 1}}, {{26, 0}, {26, 1}}, {{27, 0}, {
         27, 1}}, {{28, 0}, {28, 1}}, {{29, 0}, {29, 1}}, {{30, 0}, {30, 
         1}}}]}}}, Frame -> False, FrameLabel -> {None, None}, 
     FrameTicks -> {{None, None}, {None, None}}, ImageSize -> 600], 
    ". . ."}]]], "Output",
 CellChangeTimes->{3.401635015778769*^9}]
}, Open  ]],

Cell[CellGroupData[{

Cell[BoxData[
 RowBox[{"Row", "[", 
  RowBox[{"{", 
   RowBox[{
    RowBox[{"ArrayPlot", "[", 
     RowBox[{
      RowBox[{"{", 
       RowBox[{"Flatten", "[", 
        RowBox[{"Table", "[", 
         RowBox[{
          RowBox[{"{", 
           RowBox[{"0", ",", "1", ",", "1"}], "}"}], ",", 
          RowBox[{"{", "10", "}"}]}], "]"}], "]"}], "}"}], ",", 
      RowBox[{"Mesh", "->", "All"}], ",", 
      RowBox[{"ImageSize", "\[Rule]", "600"}]}], "]"}], ",", 
    "\"\<. . .\>\""}], "}"}], "]"}]], "Code",
 CellChangeTimes->{{3.401562902225375*^9, 3.401562910561925*^9}, {
  3.401563950805872*^9, 3.401564010755638*^9}, {3.4015646382865677`*^9, 
  3.4015646737407*^9}, {3.401631924219008*^9, 3.401631952211133*^9}, {
  3.4016350239315577`*^9, 3.401635027795372*^9}}],

Cell[BoxData[
 InterpretationBox[
  RowBox[{
   GraphicsBox[{
     RasterBox[{{1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 
      0, 1, 0, 0, 1, 0, 0, 1, 0, 0}}, {{0, 0}, {30, 1}}, {0, 1}], {
      {GrayLevel[
        NCache[-1 + GoldenRatio, 0.6180339887498949]], 
       StyleBox[LineBox[{{{0, 1}, {30, 1}}, {{0, 0}, {30, 0}}}],
        Antialiasing->False]}, 
      {GrayLevel[
        NCache[-1 + GoldenRatio, 0.6180339887498949]], 
       StyleBox[
        LineBox[{{{0, 0}, {0, 1}}, {{1, 0}, {1, 1}}, {{2, 0}, {2, 1}}, {{3, 
         0}, {3, 1}}, {{4, 0}, {4, 1}}, {{5, 0}, {5, 1}}, {{6, 0}, {6, 1}}, {{
         7, 0}, {7, 1}}, {{8, 0}, {8, 1}}, {{9, 0}, {9, 1}}, {{10, 0}, {10, 
         1}}, {{11, 0}, {11, 1}}, {{12, 0}, {12, 1}}, {{13, 0}, {13, 1}}, {{
         14, 0}, {14, 1}}, {{15, 0}, {15, 1}}, {{16, 0}, {16, 1}}, {{17, 0}, {
         17, 1}}, {{18, 0}, {18, 1}}, {{19, 0}, {19, 1}}, {{20, 0}, {20, 
         1}}, {{21, 0}, {21, 1}}, {{22, 0}, {22, 1}}, {{23, 0}, {23, 1}}, {{
         24, 0}, {24, 1}}, {{25, 0}, {25, 1}}, {{26, 0}, {26, 1}}, {{27, 0}, {
         27, 1}}, {{28, 0}, {28, 1}}, {{29, 0}, {29, 1}}, {{30, 0}, {30, 
         1}}}],
        Antialiasing->False]}}},
    Frame->False,
    FrameLabel->{None, None},
    FrameTicks->{{None, None}, {None, None}},
    ImageSize->600], "\[InvisibleSpace]", "\<\". . .\"\>"}],
  Row[{
    Graphics[{
      Raster[{{1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 
       1, 0, 0, 1, 0, 0, 1, 0, 0}}, {{0, 0}, {30, 1}}, {0, 1}], {{
       Antialiasing -> False, 
        GrayLevel[-1 + GoldenRatio], 
        Line[{{{0, 1}, {30, 1}}, {{0, 0}, {30, 0}}}]}, {
       Antialiasing -> False, 
        GrayLevel[-1 + GoldenRatio], 
        Line[{{{0, 0}, {0, 1}}, {{1, 0}, {1, 1}}, {{2, 0}, {2, 1}}, {{3, 0}, {
         3, 1}}, {{4, 0}, {4, 1}}, {{5, 0}, {5, 1}}, {{6, 0}, {6, 1}}, {{7, 
         0}, {7, 1}}, {{8, 0}, {8, 1}}, {{9, 0}, {9, 1}}, {{10, 0}, {10, 
         1}}, {{11, 0}, {11, 1}}, {{12, 0}, {12, 1}}, {{13, 0}, {13, 1}}, {{
         14, 0}, {14, 1}}, {{15, 0}, {15, 1}}, {{16, 0}, {16, 1}}, {{17, 0}, {
         17, 1}}, {{18, 0}, {18, 1}}, {{19, 0}, {19, 1}}, {{20, 0}, {20, 
         1}}, {{21, 0}, {21, 1}}, {{22, 0}, {22, 1}}, {{23, 0}, {23, 1}}, {{
         24, 0}, {24, 1}}, {{25, 0}, {25, 1}}, {{26, 0}, {26, 1}}, {{27, 0}, {
         27, 1}}, {{28, 0}, {28, 1}}, {{29, 0}, {29, 1}}, {{30, 0}, {30, 
         1}}}]}}}, Frame -> False, FrameLabel -> {None, None}, 
     FrameTicks -> {{None, None}, {None, None}}, ImageSize -> 600], 
    ". . ."}]]], "Output",
 CellChangeTimes->{3.4016350284889517`*^9}]
}, Open  ]]
}, Open  ]],

Cell[CellGroupData[{

Cell["\<\
Non-repetitive but computationally simple.\
\>", "Subsubsection",
 CellChangeTimes->{{3.401564773029211*^9, 3.401564783646996*^9}, {
   3.401564815599434*^9, 3.401564834959704*^9}, 3.4015649280892267`*^9, {
   3.401564958542143*^9, 3.401564960462336*^9}, {3.401565049586371*^9, 
   3.401565121115715*^9}, {3.401565166072755*^9, 3.401565218926598*^9}, {
   3.401567464956996*^9, 3.4015674871574593`*^9}, {3.401627605453643*^9, 
   3.401627626501542*^9}, 3.40163125926383*^9, {3.401631355148005*^9, 
   3.4016314466210833`*^9}, {3.401631735530225*^9, 3.401631849307601*^9}, {
   3.401631887264461*^9, 3.4016318905915213`*^9}, {3.401649129084051*^9, 
   3.401649134967362*^9}}],

Cell["\<\
Based on the recurrent construction of a non-rational number by appending a \
black to each group after putting a white.\
\>", "Text",
 CellChangeTimes->{{3.4016318988347054`*^9, 3.401631899127927*^9}, {
  3.401631974836164*^9, 3.401631976868347*^9}}],

Cell[CellGroupData[{

Cell[BoxData[
 RowBox[{"Row", "[", 
  RowBox[{"{", 
   RowBox[{
    RowBox[{"ArrayPlot", "[", 
     RowBox[{
      RowBox[{"{", 
       RowBox[{"Flatten", "[", 
        RowBox[{"NestList", "[", 
         RowBox[{
          RowBox[{
           RowBox[{"Prepend", "[", 
            RowBox[{"#", ",", "1"}], "]"}], "&"}], ",", 
          RowBox[{"{", "0", "}"}], ",", "6"}], "]"}], "]"}], "}"}], ",", " ", 
      
      RowBox[{"Mesh", " ", "\[Rule]", " ", "All"}], ",", " ", 
      RowBox[{"ImageSize", " ", "->", " ", "600"}]}], "]"}], ",", 
    "\"\<. . .\>\""}], "}"}], "]"}]], "Code",
 CellChangeTimes->{{3.401564457471506*^9, 3.401564473226953*^9}, {
  3.401564725050577*^9, 3.401564745951227*^9}, {3.401635037965499*^9, 
  3.40163504242033*^9}, {3.401655743873557*^9, 3.401655756550961*^9}}],

Cell[BoxData[
 InterpretationBox[
  RowBox[{
   GraphicsBox[{
     RasterBox[{{1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 
      1, 0, 0, 0, 0, 0, 0, 1}}, {{0, 0}, {28, 1}}, {0, 1}], {
      {GrayLevel[
        NCache[-1 + GoldenRatio, 0.6180339887498949]], 
       StyleBox[LineBox[{{{0, 1}, {28, 1}}, {{0, 0}, {28, 0}}}],
        Antialiasing->False]}, 
      {GrayLevel[
        NCache[-1 + GoldenRatio, 0.6180339887498949]], 
       StyleBox[
        LineBox[{{{0, 0}, {0, 1}}, {{1, 0}, {1, 1}}, {{2, 0}, {2, 1}}, {{3, 
         0}, {3, 1}}, {{4, 0}, {4, 1}}, {{5, 0}, {5, 1}}, {{6, 0}, {6, 1}}, {{
         7, 0}, {7, 1}}, {{8, 0}, {8, 1}}, {{9, 0}, {9, 1}}, {{10, 0}, {10, 
         1}}, {{11, 0}, {11, 1}}, {{12, 0}, {12, 1}}, {{13, 0}, {13, 1}}, {{
         14, 0}, {14, 1}}, {{15, 0}, {15, 1}}, {{16, 0}, {16, 1}}, {{17, 0}, {
         17, 1}}, {{18, 0}, {18, 1}}, {{19, 0}, {19, 1}}, {{20, 0}, {20, 
         1}}, {{21, 0}, {21, 1}}, {{22, 0}, {22, 1}}, {{23, 0}, {23, 1}}, {{
         24, 0}, {24, 1}}, {{25, 0}, {25, 1}}, {{26, 0}, {26, 1}}, {{27, 0}, {
         27, 1}}, {{28, 0}, {28, 1}}}],
        Antialiasing->False]}}},
    Frame->False,
    FrameLabel->{None, None},
    FrameTicks->{{None, None}, {None, None}},
    ImageSize->600], "\[InvisibleSpace]", "\<\". . .\"\>"}],
  Row[{
    Graphics[{
      Raster[{{1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 
       0, 0, 0, 0, 0, 0, 1}}, {{0, 0}, {28, 1}}, {0, 1}], {{
       Antialiasing -> False, 
        GrayLevel[-1 + GoldenRatio], 
        Line[{{{0, 1}, {28, 1}}, {{0, 0}, {28, 0}}}]}, {
       Antialiasing -> False, 
        GrayLevel[-1 + GoldenRatio], 
        Line[{{{0, 0}, {0, 1}}, {{1, 0}, {1, 1}}, {{2, 0}, {2, 1}}, {{3, 0}, {
         3, 1}}, {{4, 0}, {4, 1}}, {{5, 0}, {5, 1}}, {{6, 0}, {6, 1}}, {{7, 
         0}, {7, 1}}, {{8, 0}, {8, 1}}, {{9, 0}, {9, 1}}, {{10, 0}, {10, 
         1}}, {{11, 0}, {11, 1}}, {{12, 0}, {12, 1}}, {{13, 0}, {13, 1}}, {{
         14, 0}, {14, 1}}, {{15, 0}, {15, 1}}, {{16, 0}, {16, 1}}, {{17, 0}, {
         17, 1}}, {{18, 0}, {18, 1}}, {{19, 0}, {19, 1}}, {{20, 0}, {20, 
         1}}, {{21, 0}, {21, 1}}, {{22, 0}, {22, 1}}, {{23, 0}, {23, 1}}, {{
         24, 0}, {24, 1}}, {{25, 0}, {25, 1}}, {{26, 0}, {26, 1}}, {{27, 0}, {
         27, 1}}, {{28, 0}, {28, 1}}}]}}}, Frame -> False, 
     FrameLabel -> {None, None}, FrameTicks -> {{None, None}, {None, None}}, 
     ImageSize -> 600], ". . ."}]]], "Output",
 CellChangeTimes->{3.401635042947009*^9}]
}, Open  ]],

Cell["\<\
By using the Thue-Morse sequence. A computationally simple recurrent \
sequence, but non-periodic.\
\>", "Text",
 CellChangeTimes->{{3.401631641199017*^9, 3.401631685566807*^9}, {
  3.401631834254737*^9, 3.401631878630905*^9}, {3.401635857603243*^9, 
  3.401635862946969*^9}}],

Cell[CellGroupData[{

Cell[BoxData[
 RowBox[{"Row", "[", 
  RowBox[{"{", 
   RowBox[{
    RowBox[{"ArrayPlot", "[", 
     RowBox[{
      RowBox[{"{", 
       RowBox[{"Nest", "[", 
        RowBox[{
         RowBox[{
          RowBox[{"Join", "[", 
           RowBox[{"#", ",", 
            RowBox[{"1", "-", "#"}]}], "]"}], "&"}], ",", 
         RowBox[{"{", "1", "}"}], ",", "5"}], "]"}], "}"}], ",", " ", 
      RowBox[{"Mesh", " ", "\[Rule]", " ", "All"}], ",", " ", 
      RowBox[{"ImageSize", " ", "->", " ", "600"}]}], "]"}], ",", " ", 
    "\"\<. . .\>\""}], "}"}], "]"}]], "Code",
 CellChangeTimes->{{3.401631276810108*^9, 3.401631306802312*^9}, {
  3.4016350518449097`*^9, 3.401635055404519*^9}, {3.401649191698271*^9, 
  3.4016491997118883`*^9}, {3.401655761359473*^9, 3.401655762187913*^9}}],

Cell[BoxData[
 InterpretationBox[
  RowBox[{
   GraphicsBox[{
     RasterBox[{{0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 
      0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1}}, {{0, 0}, {32, 1}}, {0, 1}], {
      {GrayLevel[
        NCache[-1 + GoldenRatio, 0.6180339887498949]], 
       StyleBox[LineBox[{{{0, 1}, {32, 1}}, {{0, 0}, {32, 0}}}],
        Antialiasing->False]}, 
      {GrayLevel[
        NCache[-1 + GoldenRatio, 0.6180339887498949]], 
       StyleBox[
        LineBox[{{{0, 0}, {0, 1}}, {{1, 0}, {1, 1}}, {{2, 0}, {2, 1}}, {{3, 
         0}, {3, 1}}, {{4, 0}, {4, 1}}, {{5, 0}, {5, 1}}, {{6, 0}, {6, 1}}, {{
         7, 0}, {7, 1}}, {{8, 0}, {8, 1}}, {{9, 0}, {9, 1}}, {{10, 0}, {10, 
         1}}, {{11, 0}, {11, 1}}, {{12, 0}, {12, 1}}, {{13, 0}, {13, 1}}, {{
         14, 0}, {14, 1}}, {{15, 0}, {15, 1}}, {{16, 0}, {16, 1}}, {{17, 0}, {
         17, 1}}, {{18, 0}, {18, 1}}, {{19, 0}, {19, 1}}, {{20, 0}, {20, 
         1}}, {{21, 0}, {21, 1}}, {{22, 0}, {22, 1}}, {{23, 0}, {23, 1}}, {{
         24, 0}, {24, 1}}, {{25, 0}, {25, 1}}, {{26, 0}, {26, 1}}, {{27, 0}, {
         27, 1}}, {{28, 0}, {28, 1}}, {{29, 0}, {29, 1}}, {{30, 0}, {30, 
         1}}, {{31, 0}, {31, 1}}, {{32, 0}, {32, 1}}}],
        Antialiasing->False]}}},
    Frame->False,
    FrameLabel->{None, None},
    FrameTicks->{{None, None}, {None, None}},
    ImageSize->600], "\[InvisibleSpace]", "\<\". . .\"\>"}],
  Row[{
    Graphics[{
      Raster[{{0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 
       1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1}}, {{0, 0}, {32, 1}}, {0, 1}], {{
       Antialiasing -> False, 
        GrayLevel[-1 + GoldenRatio], 
        Line[{{{0, 1}, {32, 1}}, {{0, 0}, {32, 0}}}]}, {
       Antialiasing -> False, 
        GrayLevel[-1 + GoldenRatio], 
        Line[{{{0, 0}, {0, 1}}, {{1, 0}, {1, 1}}, {{2, 0}, {2, 1}}, {{3, 0}, {
         3, 1}}, {{4, 0}, {4, 1}}, {{5, 0}, {5, 1}}, {{6, 0}, {6, 1}}, {{7, 
         0}, {7, 1}}, {{8, 0}, {8, 1}}, {{9, 0}, {9, 1}}, {{10, 0}, {10, 
         1}}, {{11, 0}, {11, 1}}, {{12, 0}, {12, 1}}, {{13, 0}, {13, 1}}, {{
         14, 0}, {14, 1}}, {{15, 0}, {15, 1}}, {{16, 0}, {16, 1}}, {{17, 0}, {
         17, 1}}, {{18, 0}, {18, 1}}, {{19, 0}, {19, 1}}, {{20, 0}, {20, 
         1}}, {{21, 0}, {21, 1}}, {{22, 0}, {22, 1}}, {{23, 0}, {23, 1}}, {{
         24, 0}, {24, 1}}, {{25, 0}, {25, 1}}, {{26, 0}, {26, 1}}, {{27, 0}, {
         27, 1}}, {{28, 0}, {28, 1}}, {{29, 0}, {29, 1}}, {{30, 0}, {30, 
         1}}, {{31, 0}, {31, 1}}, {{32, 0}, {32, 1}}}]}}}, Frame -> False, 
     FrameLabel -> {None, None}, FrameTicks -> {{None, None}, {None, None}}, 
     ImageSize -> 600], ". . ."}]]], "Output",
 CellChangeTimes->{3.401635055756135*^9}]
}, Open  ]],

Cell["\<\
A 2,3 Turing machine possible bi-directional configuration, potentially \
non-periodic but still recurrent.\
\>", "Text",
 CellChangeTimes->{{3.401631641199017*^9, 3.401631685566807*^9}, {
   3.401631834254737*^9, 3.401631878630905*^9}, {3.401635857603243*^9, 
   3.401635862946969*^9}, {3.4016556364806223`*^9, 3.401655713744012*^9}, {
   3.4016560454934473`*^9, 3.40165607451017*^9}, 3.401656877033142*^9, {
   3.401657382202462*^9, 3.40165738752892*^9}}],

Cell[CellGroupData[{

Cell[BoxData[
 RowBox[{"Row", "[", 
  RowBox[{"{", 
   RowBox[{"\"\<. . .\>\"", ",", " ", 
    RowBox[{"ArrayPlot", "[", 
     RowBox[{
      RowBox[{"{", 
       RowBox[{"Flatten", "[", 
        RowBox[{"Module", "[", 
         RowBox[{
          RowBox[{"{", 
           RowBox[{"w", "=", "2"}], "}"}], ",", 
          RowBox[{"{", 
           RowBox[{
            RowBox[{"Table", "[", 
             RowBox[{
              RowBox[{"{", 
               RowBox[{
                RowBox[{"Nest", "[", 
                 RowBox[{
                  RowBox[{
                   RowBox[{"Append", "[", 
                    RowBox[{"#", ",", "2"}], "]"}], "&"}], ",", 
                  RowBox[{"{", "}"}], ",", 
                  RowBox[{
                   RowBox[{"2", "^", 
                    RowBox[{"(", 
                    RowBox[{"w", "+", "1"}], ")"}]}], "-", "1"}]}], "]"}], 
                ",", "0"}], "}"}], ",", 
              RowBox[{"{", 
               RowBox[{
                RowBox[{"2", "^", 
                 RowBox[{"(", 
                  RowBox[{"w", "+", "1"}], ")"}]}], "-", "4"}], "}"}]}], 
             "]"}], ",", 
            RowBox[{"Nest", "[", 
             RowBox[{
              RowBox[{
               RowBox[{"Append", "[", 
                RowBox[{"#", ",", "2"}], "]"}], "&"}], ",", 
              RowBox[{"{", "}"}], ",", 
              RowBox[{
               RowBox[{"2", "^", 
                RowBox[{"(", 
                 RowBox[{"w", "+", "1"}], ")"}]}], "-", "2"}]}], "]"}], ",", 
            "1"}], "}"}]}], "]"}], "]"}], "}"}], ",", " ", 
      RowBox[{"Mesh", " ", "->", " ", "All"}], ",", " ", 
      RowBox[{"ImageSize", " ", "->", " ", "700"}]}], "]"}], ",", " ", 
    "\"\<. . .\>\""}], "}"}], "]"}]], "Code",
 CellChangeTimes->{
  3.401655258910356*^9, {3.401655597852694*^9, 3.4016555989171352`*^9}, {
   3.40165576696128*^9, 3.401655776072929*^9}, {3.4016559881717033`*^9, 
   3.4016560111988688`*^9}, {3.401656161509774*^9, 3.401656165565586*^9}, {
   3.4016563630313807`*^9, 3.40165638906848*^9}, 3.401656452490645*^9}],

Cell[BoxData[
 InterpretationBox[
  RowBox[{"\<\". . .\"\>", "\[InvisibleSpace]", 
   GraphicsBox[{
     RasterBox[{{0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 
      0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 1}}, {{0, 0}, {39,
       1}}, {0, 2}], {
      {GrayLevel[
        NCache[-1 + GoldenRatio, 0.6180339887498949]], 
       StyleBox[LineBox[{{{0, 1}, {39, 1}}, {{0, 0}, {39, 0}}}],
        Antialiasing->False]}, 
      {GrayLevel[
        NCache[-1 + GoldenRatio, 0.6180339887498949]], 
       StyleBox[
        LineBox[{{{0, 0}, {0, 1}}, {{1, 0}, {1, 1}}, {{2, 0}, {2, 1}}, {{3, 
         0}, {3, 1}}, {{4, 0}, {4, 1}}, {{5, 0}, {5, 1}}, {{6, 0}, {6, 1}}, {{
         7, 0}, {7, 1}}, {{8, 0}, {8, 1}}, {{9, 0}, {9, 1}}, {{10, 0}, {10, 
         1}}, {{11, 0}, {11, 1}}, {{12, 0}, {12, 1}}, {{13, 0}, {13, 1}}, {{
         14, 0}, {14, 1}}, {{15, 0}, {15, 1}}, {{16, 0}, {16, 1}}, {{17, 0}, {
         17, 1}}, {{18, 0}, {18, 1}}, {{19, 0}, {19, 1}}, {{20, 0}, {20, 
         1}}, {{21, 0}, {21, 1}}, {{22, 0}, {22, 1}}, {{23, 0}, {23, 1}}, {{
         24, 0}, {24, 1}}, {{25, 0}, {25, 1}}, {{26, 0}, {26, 1}}, {{27, 0}, {
         27, 1}}, {{28, 0}, {28, 1}}, {{29, 0}, {29, 1}}, {{30, 0}, {30, 
         1}}, {{31, 0}, {31, 1}}, {{32, 0}, {32, 1}}, {{33, 0}, {33, 1}}, {{
         34, 0}, {34, 1}}, {{35, 0}, {35, 1}}, {{36, 0}, {36, 1}}, {{37, 0}, {
         37, 1}}, {{38, 0}, {38, 1}}, {{39, 0}, {39, 1}}}],
        Antialiasing->False]}}},
    Frame->False,
    FrameLabel->{None, None},
    FrameTicks->{{None, None}, {None, None}},
    ImageSize->700], "\[InvisibleSpace]", "\<\". . .\"\>"}],
  Row[{". . .", 
    Graphics[{
      Raster[{{0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 
       0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 1}}, {{0, 0}, {39, 
       1}}, {0, 2}], {{Antialiasing -> False, 
        GrayLevel[-1 + GoldenRatio], 
        Line[{{{0, 1}, {39, 1}}, {{0, 0}, {39, 0}}}]}, {
       Antialiasing -> False, 
        GrayLevel[-1 + GoldenRatio], 
        Line[{{{0, 0}, {0, 1}}, {{1, 0}, {1, 1}}, {{2, 0}, {2, 1}}, {{3, 0}, {
         3, 1}}, {{4, 0}, {4, 1}}, {{5, 0}, {5, 1}}, {{6, 0}, {6, 1}}, {{7, 
         0}, {7, 1}}, {{8, 0}, {8, 1}}, {{9, 0}, {9, 1}}, {{10, 0}, {10, 
         1}}, {{11, 0}, {11, 1}}, {{12, 0}, {12, 1}}, {{13, 0}, {13, 1}}, {{
         14, 0}, {14, 1}}, {{15, 0}, {15, 1}}, {{16, 0}, {16, 1}}, {{17, 0}, {
         17, 1}}, {{18, 0}, {18, 1}}, {{19, 0}, {19, 1}}, {{20, 0}, {20, 
         1}}, {{21, 0}, {21, 1}}, {{22, 0}, {22, 1}}, {{23, 0}, {23, 1}}, {{
         24, 0}, {24, 1}}, {{25, 0}, {25, 1}}, {{26, 0}, {26, 1}}, {{27, 0}, {
         27, 1}}, {{28, 0}, {28, 1}}, {{29, 0}, {29, 1}}, {{30, 0}, {30, 
         1}}, {{31, 0}, {31, 1}}, {{32, 0}, {32, 1}}, {{33, 0}, {33, 1}}, {{
         34, 0}, {34, 1}}, {{35, 0}, {35, 1}}, {{36, 0}, {36, 1}}, {{37, 0}, {
         37, 1}}, {{38, 0}, {38, 1}}, {{39, 0}, {39, 1}}}]}}}, Frame -> False,
      FrameLabel -> {None, None}, FrameTicks -> {{None, None}, {None, None}}, 
     ImageSize -> 700], ". . ."}]]], "Output",
 CellChangeTimes->{
  3.4016550088439693`*^9, 3.4016552595028763`*^9, 3.401655599218877*^9, 
   3.4016559888063383`*^9, {3.401656162059493*^9, 3.401656165899951*^9}, {
   3.401656363534536*^9, 3.401656389528509*^9}, 3.4016564529618053`*^9}]
}, Open  ]],

Cell[TextData[{
 "In each of the above examples the ",
 StyleBox["Mathematica",
  FontSlant->"Italic"],
 " code is shown and highlighted in order to exhibit the computational \
simplicity of each of them, and how can they be easily generated by a \
function for providing a Turing machine with the required unbounded tape \
filled with such a pattern. Any of them stand for a universal system by \
themselves. The background can be as sophisticated as, for instance, the \
tiling generated by the output of a finite or pushdown automaton and still be \
computationally simple enough"
}], "Text",
 CellChangeTimes->{{3.401631641199017*^9, 3.401631685566807*^9}, {
  3.401631834254737*^9, 3.401631878630905*^9}, {3.401635076257022*^9, 
  3.401635128064254*^9}, {3.401635161493784*^9, 3.401635178729897*^9}, {
  3.4016490257495193`*^9, 3.4016490259647427`*^9}, {3.4016491451018457`*^9, 
  3.4016492778366337`*^9}}]
}, Open  ]]
}, Open  ]],

Cell[CellGroupData[{

Cell["Undecidability/universality, the final frontier", "Subsection",
 CellChangeTimes->{{3.401373605659685*^9, 3.40137371088536*^9}, 
   3.401373745518271*^9, {3.401651948048571*^9, 3.401651951296163*^9}, {
   3.401653297688579*^9, 3.4016533041004457`*^9}}],

Cell["\<\
The 2,3 Turing machine universality proof main contribution has a great \
persuasive power: how to identify the minimal sound description of \
universality? which are the ultimate necessary and sufficient conditions for \
reaching it? what would be the best formalization capturing the phenomena? \
would it fully capture it the mathematical and/or the intuitive notion of it? \
could the same 2, 3 Turing machine behave universally over a repetitive \
background? what would be the relationship between the nature of the the type \
of backgrounds? All them seem of foundational value but also with practical \
meaning. Imagine that the computational power of a device is perturbed by the \
background over which it lies, one can even think in devices behaving \
sometimes universal and sometimes not, depending on the support over which \
they compute. This also takes the Turing machine model into a closer contact \
with more physically realistic situations with many branches for further \
investigation. \
\>", "Text",
 CellChangeTimes->{{3.401373605659685*^9, 3.401373716173691*^9}, {
  3.401374286870965*^9, 3.401374326060793*^9}, {3.401651944726202*^9, 
  3.4016521038946857`*^9}, {3.4016521362023067`*^9, 3.401652179369257*^9}, {
  3.4016526027507553`*^9, 3.401652837109372*^9}, {3.401652903490409*^9, 
  3.401653001899695*^9}, {3.401653046215618*^9, 3.4016530885665817`*^9}, {
  3.401653130198406*^9, 3.401653244911193*^9}, {3.401653281285681*^9, 
  3.401653282841795*^9}},
 TextJustification->1.]
}, Open  ]],

Cell[CellGroupData[{

Cell["On the abundance of universal systems", "Subsection",
 CellChangeTimes->{{3.401373605659685*^9, 3.401373701797113*^9}, {
  3.401373755790391*^9, 3.4013737567745028`*^9}}],

Cell["\<\
After the universality of rule 110, this discovery establishes once again a \
new remarkably low threshold for universality, and this time the ultimate \
boundary for the most important of the abstract models of computation : the \
Turing machine. This scientific discovery was made possible by the fact the \
computational universe is even richer than we had imagined. Not only because \
there are plenty of these systems around but because, as proved again, even \
the most simple conceivable systems are capable of universal computation. \
Wolfram's Principle of Computational Equivalence (PCE) claims that all kinds \
of simple systems support universal computation.

A relaxed definition of universality would make any sense only as far as it \
is able to distinguish between what it is from what it is not, under the \
definition. Suppose that under this relaxation it turns out that any Turing \
machine could be set for universal computation. So, let's explore the only \
two conceivable possibilities : (a) that it turns out that any Turing machine \
can become a universal Turing machine under some suitable encoding with the \
encoding itself not being universal; or (b) it turns out that the set of \
universal Turing machines is bigger than what was initially expected but \
still not big enough so that there are  non-trivial Turing machines for \
which, under all possible encodings, they still do not and cannot reach \
computational universality. Concerning (a), it seems very unlikely since one \
can still consider completely silly machines always moving their head to the \
right or to the left or simply repeating an instruction disregarding the \
content of the tape. But both (a) and (b) strongly strength Wolfram's PCE by \
placing the notion of computation itself as an ubiquitous phenomena.\
\>", "Text",
 CellChangeTimes->{{3.401373605659685*^9, 3.401373704781288*^9}, {
   3.401374324506591*^9, 3.401374325048208*^9}, 3.4015674981712933`*^9, {
   3.401568892823863*^9, 3.4015688937421083`*^9}, {3.401649838088574*^9, 
   3.401649866573283*^9}, {3.401650409272738*^9, 3.4016506024967422`*^9}, {
   3.401650869471195*^9, 3.40165125584949*^9}, {3.4016513562252827`*^9, 
   3.40165137194289*^9}, {3.401651471594037*^9, 3.401651473177802*^9}, {
   3.401651522202767*^9, 3.401651585692697*^9}, {3.401651631334037*^9, 
   3.4016518499977407`*^9}, {3.401652199924595*^9, 3.401652313309251*^9}, {
   3.401652351748789*^9, 3.401652563469409*^9}},
 TextJustification->1.]
}, Open  ]]
}, Open  ]],

Cell[CellGroupData[{

Cell["References and bibliography", "Section",
 CellChangeTimes->{{3.401373605659685*^9, 3.401373700341078*^9}, {
  3.401373748414403*^9, 3.401373752734248*^9}, {3.401374044178894*^9, 
  3.401374051544119*^9}}],

Cell["\<\
Davis, M.D. \"A note on universal Turing machines.\" Automata Studies, \
Shannon C.E. and McCarthy, J, editors, Annals of Mathematics Studies, \
Princeton university Press : 1956.\
\>", "Subsection",
 CellChangeTimes->{{3.401373605659685*^9, 3.4013737395902233`*^9}, 
   3.401374223921749*^9, {3.401374326097351*^9, 3.401374326133747*^9}, {
   3.401634750406192*^9, 3.4016347572855062`*^9}, {3.401640933295867*^9, 
   3.401640959642123*^9}, {3.401642117969512*^9, 3.401642189251191*^9}}],

Cell["\<\
Margenstern, M. \"Frontier between Decidability and Undecidability: A Survey.\
\" Theoretical Computer Science 231, no.2 (2000) : 217 - 251.\
\>", "Subsection",
 CellChangeTimes->{{3.401634650286742*^9, 3.401634650966498*^9}, {
   3.401634688555359*^9, 3.401634688851529*^9}, 3.401634878040369*^9}],

Cell["\<\
Margenstern, M. and Pavlotskaya, L. \"On the optimal number of instructions \
for universality of Turing machines connected with a finite automaton.\" \
International Journal of Algebra and Computation, 13 (2) (2003): 133 \[Dash] \
202.\
\>", "Subsection",
 CellChangeTimes->{{3.4016407461289997`*^9, 3.401640769421212*^9}, {
  3.401640819908683*^9, 3.401640842502777*^9}}],

Cell["\<\
Minsky, M. Computation : Finite and Infinite Machines. Prentice-Hall, Inc., \
1967.\
\>", "Subsection",
 CellChangeTimes->{{3.401634643953323*^9, 3.401634646463029*^9}, 
   3.4016348709679747`*^9}],

Cell["\<\
Post, E. \"Finite Combinatory Processes--Formulation 1.\" Journal of Symbolic \
Logic 1, no.3 (1936) : 103 - 105.\
\>", "Subsection",
 CellChangeTimes->{3.401634686894719*^9}],

Cell["\<\
Rogozhin, Yu. \"Small Universal Turing Machines.\" Theoretical Computer \
Science 168, no.2 (1996) : 215 - 240.\
\>", "Subsection",
 CellChangeTimes->{3.401634868007875*^9}],

Cell["\<\
Shannon, C. \"A Universal Turing Machine with Two Internal States.\" Automata \
Studies.Princeton University Press (1956) : 157 - 165\
\>", "Subsection",
 CellChangeTimes->{3.401634866799876*^9}],

Cell["\<\
Turing, A. \"On Computable Numbers, with an Application to the \
Entscheidungsproblem.\" Proceedings of the London Mathematical Society Series \
2, 42 (1937) : 230 - 265.\
\>", "Subsection",
 CellChangeTimes->{3.4016348652963943`*^9}],

Cell["\<\
Turing, A. \"On Computable Numbers, with an Application to the \
Entscheidungsproblem. A Correction. \"Proceedings of the London Mathematical \
Society Series 2, 43 (1938) : 544 - 546\
\>", "Subsection",
 CellChangeTimes->{{3.401634860015753*^9, 3.4016348633439007`*^9}}],

Cell["\<\
Woods, D and N. Turlough, \"The Complexity of Small Universal Turing Machines\
\", Springer, 2007\
\>", "Subsection",
 CellChangeTimes->{{3.401640440634561*^9, 3.401640490098839*^9}}],

Cell["\<\
Woods, D and N. Turlough, \"Small weakly universal Turing machines.\", \
\>", "Subsection",
 CellChangeTimes->{{3.401640602322651*^9, 3.401640623494516*^9}, {
  3.401640779228561*^9, 3.4016407825562077`*^9}}],

Cell["Wolfram, S. A New Kind of Science. Wolfram Media, 2002", "Subsection",
 CellChangeTimes->{3.401634856635375*^9, 3.401634894099186*^9}]
}, Open  ]]
}, Open  ]]
},
AutoGeneratedPackage->None,
WindowSize->{1147, 743},
WindowMargins->{{28, Automatic}, {0, Automatic}},
Magnification->1.25,
FrontEndVersion->"6.0 for Mac OS X x86 (32-bit) (March 10, 2008)",
StyleDefinitions->"Default.nb"
]
(* End of Notebook Content *)

(* Internal cache information *)
(*CellTagsOutline
CellTagsIndex->{}
*)
(*CellTagsIndex
CellTagsIndex->{}
*)
(*NotebookFileOutline
Notebook[{
Cell[CellGroupData[{
Cell[590, 23, 338, 6, 213, "Title"],
Cell[CellGroupData[{
Cell[953, 33, 953, 20, 72, "Input"],
Cell[1909, 55, 1065, 23, 119, "Print"]
}, {2}]],
Cell[CellGroupData[{
Cell[3008, 83, 145, 2, 83, "Section"],
Cell[3156, 87, 1065, 17, 100, "Text"]
}, Open  ]],
Cell[CellGroupData[{
Cell[4258, 109, 145, 2, 83, "Section"],
Cell[4406, 113, 7897, 113, 782, "Text"],
Cell[12306, 228, 255, 5, 32, "Text"],
Cell[CellGroupData[{
Cell[12586, 237, 1159, 37, 53, "Input"],
Cell[13748, 276, 1319, 47, 124, "Output"]
}, {2}]],
Cell[15079, 326, 343, 6, 32, "Text"],
Cell[CellGroupData[{
Cell[15447, 336, 206, 4, 33, "Input"],
Cell[15656, 342, 2229, 42, 78, "Output"]
}, {2}]],
Cell[CellGroupData[{
Cell[17919, 389, 681, 11, 42, "Subsection",
 CellGroupingRules->{GroupTogetherGrouping, 10000.}],
Cell[18603, 402, 506, 11, 33, "Input",
 CellGroupingRules->{GroupTogetherGrouping, 10000.}],
Cell[19112, 415, 530, 11, 33, "Input",
 CellGroupingRules->{GroupTogetherGrouping, 10000.}],
Cell[19645, 428, 2859, 75, 148, "Input",
 CellGroupingRules->{GroupTogetherGrouping, 10000.}],
Cell[22507, 505, 1273, 37, 53, "Input",
 CellGroupingRules->{GroupTogetherGrouping, 10000.}],
Cell[23783, 544, 1033, 29, 53, "Input",
 CellGroupingRules->{GroupTogetherGrouping, 10000.}],
Cell[24819, 575, 942, 25, 53, "Input",
 CellGroupingRules->{GroupTogetherGrouping, 10000.}]
}, Closed]],
Cell[CellGroupData[{
Cell[25798, 605, 626, 17, 25, "Input"],
Cell[26427, 624, 7625, 203, 359, "Output"]
}, {2}]]
}, Open  ]],
Cell[CellGroupData[{
Cell[34098, 833, 212, 4, 83, "Section"],
Cell[34313, 839, 1678, 24, 164, "Text"],
Cell[CellGroupData[{
Cell[36016, 867, 201, 2, 42, "Subsection"],
Cell[36220, 871, 1695, 25, 164, "Text"],
Cell[CellGroupData[{
Cell[37940, 900, 425, 6, 31, "Subsubsection"],
Cell[CellGroupData[{
Cell[38390, 910, 569, 13, 33, "Input",
 CellGroupingRules->{GroupTogetherGrouping, 10000.}],
Cell[38962, 925, 1570, 30, 268, "Input",
 CellGroupingRules->{GroupTogetherGrouping, 10000.}]
}, {2}]]
}, Open  ]],
Cell[CellGroupData[{
Cell[40578, 961, 684, 11, 31, "Subsubsection"],
Cell[CellGroupData[{
Cell[41287, 976, 6923, 190, 281, "Input",
 CellID->1440177572],
Cell[48213, 1168, 3863, 101, 268, "Output"]
}, {2}]]
}, Open  ]]
}, Open  ]],
Cell[CellGroupData[{
Cell[52134, 1276, 143, 2, 42, "Subsection"],
Cell[52280, 1280, 4864, 69, 482, "Text"]
}, Open  ]],
Cell[CellGroupData[{
Cell[57181, 1354, 159, 2, 42, "Subsection"],
Cell[57343, 1358, 7629, 114, 857, "Text"]
}, Open  ]],
Cell[CellGroupData[{
Cell[65009, 1477, 407, 5, 42, "Subsection"],
Cell[65419, 1484, 1492, 22, 145, "Text"],
Cell[66914, 1508, 425, 9, 51, "Text"],
Cell[CellGroupData[{
Cell[67364, 1521, 372, 6, 31, "Subsubsection"],
Cell[CellGroupData[{
Cell[67761, 1531, 742, 17, 53, "Code"],
Cell[68506, 1550, 3349, 58, 74, "Output"]
}, Open  ]]
}, Open  ]],
Cell[CellGroupData[{
Cell[71904, 1614, 415, 5, 31, "Subsubsection"],
Cell[CellGroupData[{
Cell[72344, 1623, 838, 18, 53, "Code"],
Cell[73185, 1643, 3619, 62, 74, "Output"]
}, Open  ]]
}, Open  ]],
Cell[CellGroupData[{
Cell[76853, 1711, 402, 5, 31, "Subsubsection"],
Cell[77258, 1718, 175, 3, 32, "Text"],
Cell[CellGroupData[{
Cell[77458, 1725, 813, 20, 53, "Code"],
Cell[78274, 1747, 2622, 49, 74, "Output"]
}, Open  ]],
Cell[CellGroupData[{
Cell[80933, 1801, 769, 19, 53, "Code"],
Cell[81705, 1822, 2624, 49, 74, "Output"]
}, Open  ]]
}, Open  ]],
Cell[CellGroupData[{
Cell[84378, 1877, 684, 11, 31, "Subsubsection"],
Cell[85065, 1890, 261, 5, 32, "Text"],
Cell[CellGroupData[{
Cell[85351, 1899, 795, 20, 53, "Code"],
Cell[86149, 1921, 2511, 47, 75, "Output"]
}, Open  ]],
Cell[88675, 1971, 286, 6, 32, "Text"],
Cell[CellGroupData[{
Cell[88986, 1981, 779, 19, 53, "Code"],
Cell[89768, 2002, 2715, 49, 72, "Output"]
}, Open  ]],
Cell[92498, 2054, 467, 8, 32, "Text"],
Cell[CellGroupData[{
Cell[92990, 2066, 2075, 53, 53, "Code"],
Cell[95068, 2121, 3330, 57, 76, "Output"]
}, Open  ]],
Cell[98413, 2181, 911, 16, 89, "Text"]
}, Open  ]]
}, Open  ]],
Cell[CellGroupData[{
Cell[99373, 2203, 258, 3, 42, "Subsection"],
Cell[99634, 2208, 1517, 23, 145, "Text"]
}, Open  ]],
Cell[CellGroupData[{
Cell[101188, 2236, 176, 2, 42, "Subsection"],
Cell[101367, 2240, 2498, 36, 239, "Text"]
}, Open  ]]
}, Open  ]],
Cell[CellGroupData[{
Cell[103914, 2282, 210, 3, 83, "Section"],
Cell[104127, 2287, 497, 8, 61, "Subsection"],
Cell[104627, 2297, 308, 5, 50, "Subsection"],
Cell[104938, 2304, 383, 7, 50, "Subsection"],
Cell[105324, 2313, 207, 5, 31, "Subsection"],
Cell[105534, 2320, 185, 4, 31, "Subsection"],
Cell[105722, 2326, 183, 4, 31, "Subsection"],
Cell[105908, 2332, 205, 4, 50, "Subsection"],
Cell[106116, 2338, 244, 5, 50, "Subsection"],
Cell[106363, 2345, 281, 5, 50, "Subsection"],
Cell[106647, 2352, 193, 4, 31, "Subsection"],
Cell[106843, 2358, 218, 4, 31, "Subsection"],
Cell[107064, 2364, 140, 1, 31, "Subsection"]
}, Open  ]]
}, Open  ]]
}
]
*)

(* End of internal cache information *)