8 On the classifiability of Cellular Automata 9 9 1 John T. Baldwin ∗ n Department of Mathematics, Statistics and Computer Science a J University of Illinois at Chicago 5 1 Saharon Shelah† Department of Mathematics ] O Hebrew University of Jerusalem L University of Wisconsin, Madison . h February 8, 2008 t a m [ 1 1 Background v 2 5 BasedoncomputersimulationsWolframpresentedinseveralpapersconjectured 1 classifications of cellular automata into 4 types. In [9] Wolfram distinguishes 1 the 4 classes of cellular automata by the evolution of the pattern generated by 0 applying a cellular automaton to a finite input. We quote from page 161. 8 9 1. Pattern disappears with time. / h t 2. Pattern evolves to a fixed finite size. a m 3. Pattern grows indefinitely at a fixed rate. : v 4. Pattern grows and contracts with time. i X Wolfram’s qualitative classification is based on the examination of a large r a number of simulations. In addition to this classification based on the rate of growth,heconjecturedasimilarclassificationaccordingtotheeventualpattern. We consider here one formalization of his rate of growth suggestion. After completing our major results (based only on Wolfram’s work), we investigated other contributions to the area and we report the relation of some them to our ∗PartiallysupportedbyNSFgrant9308768. †This is paper 623 in Shelah’s bibliography. Both authors thank the Binational Science Foundationforpartialsupportofthisresearch. Shelah’sworkonthisprojectbeganduringa visittotheUniversityofWisconsinpartiallysupportedbyNSF#144-EF67. 1 discoveries. We thank Lyman Hurd, Nino Boccaro, and Henryk Fuks for their suggestions in this regard. There are really two questions. Can one classify the action of a cellular automaton on a particular input x? Can this be extended to a classification of automata in terms, e.g., of the average behavior of the automaton on all inputs? It is straightforwardto prove such a classificationof pairs hA,xi. That classification essentially is on the lines Wolfram suggests. (Only essentially, because class three can be more precisely described as monotone growth. The rate of growth can vary from logt to t.) But we show that this classification of pairs (A,x) does not yield a classification of automata A. That is, for any nonnegative rationals p,q with p+q =1, we construct an automaton A that p,q depending onthe inputis likelytobe inClass3with probabilityp andinClass 4withprobabilityq. Inthe process,we describeseveralpatternswhichseemto be qualitatively different from those reported by Wolfram; in particular, with growthoforderlogt. Wedealprimarilywithonedimensionalcellularautomata sincetheyareadequateforthecounterexamplesweneed. Thebasicideasextend naturally to higher dimensional cellular automata. Therearea number ofquestions aboutthe connections ofthese results with Wolfram’s conjectures. First, Wolfram proposed several different schemes for classifying cellular automata. Our result argues that one of these conjectured classifications fails. This does not, a priori, invalidate the other classifications. In particular, the formalization of the classification provided by Culik and Yu [4] clearly divides all automata into 4 classes. Similarly, that of [2] divides all automata into 3 classes. They show the question of which class a particular automata falls into is undecidable. Both of these formalizations classify an automaton by its ‘worst case’ or most complicated behavior (as input varies). Suchaworstcaseclassificationis completelyconsistentwithfailureofan‘aver- age behavior’ classification. Sutner [8] has shown the positions of the Culik-Yu classes in the arithmetic hierarchy. Like ours, these results dealwith the action of cellular automataon finite sequences; Ishii[7] has establisheda classification for the action on infinite sequences. 2 Classification of automaton-input pairs 2.1 Notation. Our finite alphabets, usually denoted Σ, will always contain the symbols 0,1,S,F,∗,B. B will represent blank. A finite input on a two-way infinite tape will always be an initial string of B’s, followed by a finite word in Σ (can include B’s) and then an infinite string of B’s. We assume that at least one cell in an input string is not B. 2.2 Definition. The size of a 1-dimensional cellular automaton A (or Turing machine) acting on input x is the function, S (t) which assigns to each time A,x t the size of the configurationonthe tape after t steps of the computation with 2 input x, that is the distance between left most and right most non-B cells at time t. The following division into four cases is almost immediate from the defini- tions. 2.3 Lemma. For every cellular automaton A and finite input x, exactly one of the following holds. 1. lim S (t)=0. t→∞ A,x 2. For some constant c, 0<limsup S (t)<c. t→∞ A,x 3. lim S (t)=∞ and S (t) is eventually monotone. t→∞ A,x A,x 4. lim S (t)=∞ and S (t) is not eventually monotone. t→∞ A,x A,x Proof. The key point is to note thatif liminf S (t) is bounded then a t→∞ A,x configuration is repeated and the action of A on x falls into the first or second class.2 We can refine this observation. 2.4 Lemma. Let p=|Σ|+1. In either case 3 or 4 for a 1-dimensional cellular automaton of radius r we have: ln t≤S (t)<|x|+rt. p A,x Proof. The upper bound is immediate. For, the lower bound note that if S (t) < ln t, two configurations must be repeated. But then the cellular A,x p automaton will cycle and we are in case 2. 2 Note that the second class - pattern evolves to a fixed finite size - encom- passes both periodic and glider configurations. In a glider, the pattern repeats cyclically but moves across the domain. 3 Simulation of Turing Machines by Cellular Au- tomata WedevelopinthissectionameansfirsttosimulateanarbitraryTuringmachine onstandardinputbyacellularautomataandthentosimulateTuringmachines, which compute total recursive functions, on arbitrary finite input. This gives risetoaconvenientclassofautomatawhichwecalldominating automata. Most discussions of recursive functions are interested only in the computation of the value of a function and input to the Turing machine is restricted to a standard form. However, Shepherdson [6] dealt with arbitrary inputs and proved, for example,thatforeveryr.e. degreeαthereisaTuringmachineM suchthatthe collection of pairs of configurations hC1,C2i such that C2 appears if M starts on C1 has degree α. 3 3.1 Definition. 1. A standard Σ-configuration for a two-way tape contains a unique S and F and all non-B cells are between them. 2. A Σ-i/o (input/output)configuration for a two-way tape is a finite string surroundedbyB’sandbeginningwiththesymbolS followedbyastringof 0’sand1’s(binaryrepresentationofanumberm)followedbya*,followed by another string of 0’s and 1’s (binary representation of a number n) followedbyanF.Thestringsmaybeempty. Wewritesuchaconfiguration as Sm∗nF. 3. We say a Turing machine is on a standard configuration if the head is reading a cell between the S and F. A Turing machine is specified by an alphabet Σ, a set Q of internal states, andatransitionrule. Thetransitionrulemapsthecurrentstateandthesymbol currently read to a new state, prints a symbol from Σ and moves the head left orright. Itiseasytocodetheinternalstatesbyexpandingthealphabet;Turing machines thus become formally more similar to cellular automata. This coding is carried out more precisely below. 3.2 Operating Conventions. We restrict to Turing machines with alphabet Σ which obey the following. 1. When reading S, the head can move left only if the S is replaced by a 0 or 1 (and S is printed on the cell to the left in the next step). 2. When reading F, the head can move right only if the F is replaced by a 0 or 1 (and F is printed on the cell to the right in the next step). 3. S or F is printed only in one of these two ways. 4. A ∗ is printed only if on the immediately preceding step a ∗ has been overprintedwith a 0 or 1. . With these conventions it is easy to check the following lemma. 3.3 Lemma. If a Turing machine begins on a standard Σ-configuration then every successive configuration is a standard Σ-configuration. 3.4 Definition. A 1-dimensional cellular automaton acts on a 2-way infinite tape. Each cell contains a symbol from a finite alphabet Σ (possibly B). The automaton has radius r if the value of a cell at time t+1 depends on the value at time t of the cell and its r predecessors and r successors. We deal primarily with radius 1 rules which determine the next value of a cell depending only on the current value of the cell and its left and right 4 neighbors. We require that state B is quiescent, any cellular automaton takes an input which is all B to B. Thus, beginning on finite input our tape will always contain only a finite number of non-B cells. 3.5 The Simulation Language. LettheTuringmachineT havethealphabet Σ={S,F,0,∗,1,B,},operations O ={L,R}and states Q={q0,...qk}. Thus T isgivenbyafunctionT :Q×Σ7→Σ×O×Q. Wewillcontructa1-dimensional cellular automaton with radius 1 that simulates T. Let Q1 = Q∪{B}. Let Σ1 =Σ×Q1×{L,R,H,B}. Thus eachmember of Σ1 codes a symbol of the originallanguage,a state of the original machine and the head position of the Turing machine. (In effect, thiscreatesa3tracktape.) Whenconfusionisunlikelytoensue,wewilldescribe only the projectionof the tape onto one coordinate. Thus we may say the tape readsSm∗nF tomeanthesequenceofnon-Bfirstcoordinates. Thecellisactive ifthe headposition(thirdcoordinate)is H. We clarifythisdescriptionwiththe following definition. Note that while Σ and Σ-i/o configurations involved only the symbols from Σ, in Σ1-configurations we also code the head position and state (of the simulated Turing machine). 3.6 Definition. 1. A standard Σ1-configuration of a two-way infinite tape satisfies the following. (a) All but finitely many cells contain B′ =hB,B,Bi. (b) Thefirstcoordinatesofthenon-B′cellsformastandardΣ-configuration. (c) There is a unique cell whose third coordinate is H; all non-B′ cells to the left of it have R as third coordinate; all non-B′ cells to the right of it have L as third coordinate. 2. A standard Σ1-configuration is a standard Σ1-i/o configuration if in ad- dition (a) The first coordinates form a standard Σ-i/o configuration. (b) One cell contains the entry hS,q ,Hi. The head position is L for all o other non-B′ cells. Now we show that there is a simple computation of each partial recursive function by a cellular automaton. This is, of course, well known. For example, the basic idea of the simulation here occurs in [3][6.3]. The argument we give here clarifies and motivates our later constructions. We see now how our sim- ulation works on standard input. Later, we introduce further complications to deal with nonstandard input. is, Thefollowingargumentissimilartothesimulationdescribedindependently but earlier in [4]. The novelty of the simulation in this paper appears in the 5 treatment of nonstandard configurations. The important role of initial condi- tions and the possibility of heads was pointed out independently but earlier in [1]; our analysis of this situation is new. 3.7 Lemma. For every Turing machine M, there is a cellular automaton A M such that the action of M, beginning in state q0 at the symbol S, on a standard Σ-i/o configuration is exactly the action of A on the first coordinates of the M associated standard Σ1-i/o configuration. Moreover, if the operation of AM be- gins on any standard Σ1-configuration, all later configurations are also standard Σ1-configurations. Proof. The automatonA has dimension and radius 1. We describe the action M of A on a cell i based on cells i−1, i, i+1 (the site at i) with contents (for M j =i−1,i,i+1): hsymbol,state,headpositioni=hs ,q ,p i. The description j j j here is for cells which appear in a standard Σ1-configuration. The definition is extended to nonstandard configurations below. 1. The first coordinate (i.e. the symbol) at the next stage is determined entirely by cell i. (a) If p 6=H, the first coordinate remains the same. i (b) If p = H, the first coordinate becomes the symbol printed by M in i state q reading s . i i 2. If p is H, the new state and head position of cell i is determined by cell i i. The state remains the same; the head position is L or R depending on whether M moves left or right when reading s in state q . i i 3. Ifpi+1 isH,thenewstateandheadpositionofcelliisdeterminedbycell i+1. (a) If instateqi+1 readingsi+1, M movesleftandgoesintostate q′, the new positionofcelliisH andthe new stateisq′. (The new position of cell i+1 is L.) (b) If in state qi+1 reading si+1, M moves right, the position of cell i remainsR andthe state remainsthe same. (The new positionofcell i+1 is R.) 4. If pi+1 is R, then the new head position is again R and the state and symbol are also unchanged. 5. If neither cell i, nor i+1 has head position H or R, the new state and head position of cell i depend on cell i−1. (a) Ifpi−1 isL,thenthenewheadpositionisLandthestateandsymbol are unchanged. 6 (b) If pi−1 =H, the new state and head position of cell i is determined by cell i−1. i. If in state qi−1 reading si−1, M moves right and goes into state q′, the new position of cell i is H and the new state is q′. (The new position of i−1 is R.) ii. If in state qi−1 reading si−1, M moves left, the new position of cell i is L and the state remains the same. (The new position of i−1 is L.) Just checking, one sees that on a standard Σ1 i/o configuration, the simulation works as desired.2 We want to deal with arbitrary inputs. We will arrange that on a finite input, the rightmost active cell will eventually dominate the computation. In order to do this we have to restrict to certain kinds of computations of total recursive functions. 3.8 Normal input-output conventions. The Turing machine M normally computes thefunctionf,ifforeachm,oninputSmF,beginningonS ininitial state q0, it computes Sf(m)F and halts. We want to consider a nonstandard input-output convention. 3.9 Definition. 1. The Turing machine M is said to copy/compute f if be- ginning at S on a tape with standard configuration Sm∗F, it computes Sm∗f(m)F and halts. 2. The Turing machine T is said to fully compute the function f on empty imput if the machine successively computes the sequences Sn∗f(n)F for each natural number n. Obviously, every total recursive f can be copy/computed by a Turing ma- chine T . The next remark is equally obvious; we spell it out because we make f use of the details in our simulation. 3.10 Lemma. For any total recursive function f, there is a Turing machine T which fully computes f on empty input. f Proof. Fix a Turing machine M which normally computes f. Now we describe the operation of the new machine T which fully computes f on empty input. f We assume the initial state is q . Using special states it writes S0∗F. Now we o begin the main loop. It moves left erasing as it goes until it reaches *. It then movesleft adding 1 to the number onthe left of * and movingthe S one cellto the left if necessary. The configuration now begins Sm+1∗. Then head moves right and copies m+1 after *. Now it behaves on the sequence ∗m+1 as M behaves on Sm+1 to compute f(m+1). When it reaches the halting state of M, this finishes one iteration of the loop. 2 7 Notethatsinceinincrementingm,S ispushedtoleft(every2nsteps)andm is copiedto the right pushing F to the right(unless the computationis already longer than logm), any finite interval containing the initial configuration will eventually lie between S and F. We need one more refinement on our Turing computations; its use in this contextwassuggestedtousbyGyorgyTuran. Byaninitial positionofaTuring machine, we mean an input string, a position of the head on the tape, and an initial state. 3.11 Lemma. For any Turing machine T, there is a Turing machine T′ in a language Σ′, which on standard input simulates T, but does not cycle on any initial position. Moreover, on any Σ′-input x, ST′,x(t) = max(ST′,x|Σ(t),t). Moreoverfortbiggerthanthelengthoftheinput,ST′,x(t)isastrictlyincreasing function. Proof. Let Σ′ add a second track to the tape. The only symbols which occur on the second track are 0,1 and B. In accordance with the convention in Notation2.1,thistrackcontainsonlyafinitenumberof1’sand0’s. T′actsasT onthefirsttrack. Ateachstepinthecomputationthemachineprintsa0onthe 2ndtrackatthe positioncurrentlybeing read. Ifthat cellwasblankit replaces the 0 with 1 and proceeds to the next step of the computation. Otherwise, it movestothe rightuntilitreachesthe firstcellnot1,printsa1onit, returnsto the 0, changesit to 1 andproceeds to the next stepof the computation. blanks 2 3.12 Definition. The cellular automaton A is said to completely compute the totalfunctionf,ifforsomem,themachinesuccessivelycomputesthesequences Sn∗f(n)F for each natural number n>m. coordinates Sm∗xF, natural number n>m. The initialinput maycontaina correctpartialcomputationoff(m); inthis case the machine just continues the computation. 3.13 Theorem. For any total recursive function f, there is a cellular automa- ton A which completely computes f. f Proof Outline. Fix T , a Turing machine, which fully computes f, and f which, using Lemma 3.11, does not cycle on any input. We will establish two properties of the action of the simulating automaton. 1. ThesuccessorofastandardΣ1-configurationCisastandardΣ1-configuration C′. Moreover,the firstcoordinatesofC′ arethe resultofthe actionofT f on the first coordinates of C. 2. Any tape input with only finitely many non-B′-cells will evolvein finitely many steps to a standard Σ1-configuration. 8 Together these two facts yield the theorem. The first property follows directly from Lemma 3.7. For the second, we regard a cellular automaton with alphabet Σ1 as a number of heads each per- forming a Σ-computation. We will arrange that the rightmost of these heads eventually dominates the computation and computes f. We would like to con- struct an automaton that acted independently of input and just started com- pletely computing f. But, we have to allow for the possibility that the initial position is in the midst of a correct computation. An arbitrary configuration may contain many heads; it may contain none. Consider first that the initial configurationcontains only one non-blank cell which contains hS,q0,Hi. From such a site the machine proceeds to fully com- pute f as in Lemma 3.10. It will print ∗ once and this ∗ will never move. We call this the generating subroutine. We must explain what happens when there are other nonblank cells. We saya subsequenceofaconfiguration(in particulara site)isacceptable if it occurs in a simulation (as in Lemma 3.7) of a computation beginning on the standardΣ1-i/oconfigurationassociatedwithS∗F. (Ifthe middle cellofasite ishS,q0,Hiandthe pairofthe secondtwocellsoccurinsuchasimulationthen thesiteisacceptable.) AstopcellisoneofhS,q0,RiorhS,q0,Hi. Asiteisquiet iftherightmostcellisastopcell;the centercellbecomeshB,q,Riwhereq was the current state. Any other site is called a generating site and the new entry of cell i is hS,q0,Hi. The operation of the machine on a cell which contains a head depends on whether the site centered on the cell is acceptable, quiet, or generating. If it is acceptable, the simulation continues as in Lemma 3.7; the other actions have just been described. Now we give a global picture of the operation of the automata. 1. From any generating site the machine begins the generating subroutine. Thisoperationhaspriority(writingoveranyotherinput) unlessthe head finds a stop cell to its right. 2. If a site is acceptable and contains a head, this head will either trace out a complete computation of f or find a stop cell to its right. In either case when the computation finds a stop cell the left H becomes R and remains quiescent until it is eventually overwritten by the head on the right. (If there is a head on the right this will happen because the * written by the right Head will never move; eventually the rightmost Head will write over anything written by the other Heads.) Toseethatthismachinecomputesafinalsequenceofvaluesforf,weanalyze the initial stringfromthe right. Either the entire configurationis acceptableor thereisarightmostgeneratingsitefollowedbyanacceptablestring. Inthefirst case,the configurationis a standardΣ1-i/o configurationandthe resultfollows by Lemma 3.7. In the second case a complete computation of f will propagate 9 from the rightmost generating site. The input to the right of this state will be used; the input to the left is irrelevant to the eventual computation.2 3.14 Definition. WecallanautomatonA constructedasintheproofofThe- f orem 3.13, a dominating automaton. Note that a dominating automaton uses unbounded space on any input, so a classification of automata according to the schema suggested would have to put each dominating automaton in class 3 or 4. 4 Composition and Nonclassifiability of Cellular Automata In this section we show how to compose a finite set of dominating cellular automata A1...An into a single automaton A with a larger alphabet whose growthratesreflectsthat ofeachA . Moreover,this compositioncanbe chosen i sothattheclassificationofthe behaviorofAoninputxfallsintospecifiedtype 3 or 4 with arbitrary probability. 4.1 Definition. LetA1,...An becellularautomataofthesamedimensionand radius with alphabet Σ0 ⊆ Σ. Let X = Si<nXi be an additional set of finite symbols(wheretheXi aredisjoint). FormthelanguageΣ1 =Σ×X. Definethe cellular automaton A = ⊕ A with the following transition rule. If the central i i cell has an element of X as its second component use the transition rule from i A on the first components. A is called the composition of the A with respect i i to X. We clearly have: 4.2 Lemma. If A1 and A2 are dominating automata then so is their composi- tion (for any X). 4.3 Definition. For each n, let P be the probability measure assigning the n same probability to each element of Σn (i.e. each finite input of length n). 4.4 Definition. Let P (i,A) be the probability that among all inputs x of n length n, the function S is in class i (from the classification in Lemma 2.3). A,x We now show that the classificationofSection 2 does not extend frompairs hA,xi to cellular automata A. 4.5 Lemma. Letp,qberationalnumbers0≤p,q ≤1withp+q=1. Thereisa cellular automaton A such that for every n, P ({x:hA ,xi∈Class 3})=p p,q n p,q and P ({x:hA ,xi∈Class4})=q. n p,q 10