A (one dimensional) cellular automaton is a function1 F : Σ → Σ with the property that there is a K > 0 such that F (x)i depends only on the 2K + 1 coordinates xi−K , xi−K+1, . . . , xi−1, xi, xi+1, . . . , xi+K . A periodic point of σ is any x such that σ^p (x) = x for some p ∈ N, and a periodic point of F is any x such that F^q (x) = x for some q ∈ N. Given a cellular automaton F, a point x ∈ Σ is jointly periodic if there are p, q ∈ N such that σ^p (x) = F^q (x) = x, that is, it is a periodic point under both functions.
This project aims to explore the nature of one-dimensional Cellular Automata, in the hope of finding the structure of cellular automata through its periodic points.
LEMMA Research Project / Code / Source code / Program (1) / Program / FProbPeriod / README_FProbPeriod.txt
2033 viewsLicense: MIT
ubuntu2004
Copyright (C) 2004 Bryant Lee12This program is free software; you can redistribute it and/or3modify it under the terms of the GNU General Public License4as published by the Free Software Foundation; either version 25of the License, or (at your option) any later version.67This program is distributed in the hope that it will be useful,8but WITHOUT ANY WARRANTY; without even the implied warranty of9MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the10GNU General Public License for more details.1112You should have received a copy of the GNU General Public License13along with this program; if not, write to the Free Software14Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.151617README18-------------1920FProbPeriod v3.6721Written by: Bryant Lee ([email protected])228/30/0523last modified: 1/18/062425This document describes how to use the FProbPeriod program. For information on how to compile from source code, see COMPILE.txt.2627Run FProbPeriod28-------------2930The FProbPeriod program samples points of a given shift period and determines their period and preperiod under the function f. The purpose is to give some indication of the period and preperiod information of all the points of the given shift period.3132To run, type:33FProbPeriod < INPUT_FILE3435The easiest way to explain how the program works is to use an example. Suppose we use the following input file:3637Input1.txt38-------------39output after each40out/FP_8_30_2005_4124210; 11; [14,16]43100044BEGIN DEFINITIONS45func1 = t(4, 0001 1101 1110 0010)46M = x[0] + x[1]47A = x[0] + x[1] * x[2]48BEGIN COMMANDS49M#A50func15152Explanation of the input53--------------------------------54Line 1: Output mode. There are only two valid inputs for line 1, either "output after each" or "output at end". If "output at end" is chosen, then the program does not produce output files until the runs for all values of K are complete. If "output after each" is chosen, then the program generates output files at the end of each run for a different value of K. This is helpful when using a long range of K values where some of the larger values may cause the program to crash (due to running out of memory), which results in no output at all in the "output at end" mode. However, it wastes a little time because outputting after each K value is redundant.5556Line 2: Prefix for output files. When the program finishes, output will be written into several different files. In the example, all the output files will be written into the subdirectory "out" and will start with the prefix FP_8_30_2005_.5758Line 3: N = Number of symbols in the shift.5960Line 4: Values for K, the shift period. Specify ranges of values using [a,b] notation or specify single values as a number. Different sets of values are separated by ';'. The use of whitespace on this line is not important.6162Line 5: m = number of points to sample6364Points are randomly generated by using an implementation of the Mersenne Twister random number generator of Matsumoto and Nishimura; see M. Matsumoto and T. Nishimura, "Mersenne Twister: A 623-dimensionally equidistributed uniform pseudorandom number generator", ACM Trans. on Modeling and Computer Simulation Vol. 8, No. 1, January pp.3-30 (1998). This specific implementation was written by Richard Wagner in 2003.6566Line 6: "BEGIN DEFINITIONS." This signifies that on the following lines you will define functions (give them names). This line is not case sensitive: "BeGiN DeFiNiTiOnS" is equally valid.6768The definitions section is used to name functions so that the names can be used in the command section. Defining a function does not mean that FProbPeriod will analyze that function. You must give the command to analyze a function in the command section.6970Lines 7 - 9: The first function is named "func1." A function can be named with any single word (i.e., a string of characters with no spaces). The = signifies that the function on the RHS is named by the LHS. This function, "func1," is specified in lookup table syntax. The 't' signifies that the function is specified as a table. The first value in parenthesis is the span of the function and the second value is the table itself. The rules for specifying lookup tables are explained in "Lookup table syntax" below.7172The second and third functions are specified as polynomials. Certain rules apply to specifying functions as polynomials: see the section "Polynomial syntax" below.7374NOTE: Using a lookup table is many times faster than calculating a polynomial (in tests, one function was 25 times faster as a table than as a polynomial). However, one can optimize functions specified as polynomials to make them as fast as a lookup table. See the section "Optimizing polynomial functions" below.7576Line 10: "BEGIN COMMANDS." This signifies that you are done defining functions and will now give commands on the following lines.7778The commands tell the program which functions it should analyze. In the command section, you specify functions and compositions by using the names you defined in the definitions section. You cannot write polynomials or lookup tables themselves in the command section. The program generates two output files for each function/composition in the command section (see "Output" section).7980Lines 11 - 12: The # character signifies composition. Hence, the line "M#A" tells the program to analyze the composition (A(x)). Compositions can be arbitrarily long; you can compose 3, 4, 5, or as many functions as you would like. Both functions that were specified as polynomials and lookup tables can be used in compositions. The next line "func1" tells the program to analyze the function "func1."8182Output83----------8485Running the program on Input1.txt generates four files in the subdirectory "out": FP_8_30_2005_M#A.txt, FP_8_30_2005_M#A_preperiods.txt, FP_8_30_2005_func1.txt, and FP_8_30_2005_func1_preperiods.txt. If files already exist with these names, they are overwritten. Note that the subdirectory "out" must already exist for this to work. FProbPeriod will not create directories.8687It happens that M#A = func1, so the results for both sets of files is the same. The file with the name of the function (or composition) gives the summary and period multiplicities, while the file with the name of the function (or composition) and with suffix "_preperiods" contains the preperiod multiplicities.8889Summary and period file:90The top of the file gives the input information. Following is information concerning all points of shift period K (these results count the points not of least period K). First are tables of summary information. Note that AvgPd refers to the average "eventual" period (a point's eventual period is the period of its orbit, regardless of whether the point itself is periodic). Similarly, MaxPd is the maximum "eventual" period. Then comes a table of the periods: Mult(#points) is the number of sampled points having the given period as their eventual period.9192Preperiod file:93This file has the table of preperiod multiplicities for period K.9495If the "output after each" option was used, then some entries in the summary or the preperiod file may be listed as "PENDING". This happens when the program crashes before filling in those entries.9697Polynomial syntax98-------------------------99The operators +, -, *, and ^ may be used. No parentheses are allowed, so strict order of operations must be followed. Often this means that you must simplify by hand a function you wish to express. The coordinates of the x terms are relative (and can be positive or negative). When calculating image[i], the term x[j] refers to the absolute coordinate x[i + j] (e.g., when calculating image[2], the term x[-5] refers to the absolute coordinate x[-3]). Positive integer constants are allowed. Do not use negative constants; instead, change an addition (+) to a subtraction (-). There is one exception to this rule: you may use a negative constant if it is the very first thing in the function (in this case you could not create a subtraction). When writing multiplication, be sure to use *. You cannot juxtapose terms/constants to imply multiplication. The use of white space is not important.100101Examples of valid polynomials:102a = x[0] + x[1] * x[2]103b = x[-9] ^ 5 + x[2] * x[3] * 3 + x[5] * x[102] + x[17] + x[-300] * 3104c = - x[99]105106Examples of invalid polynomials:107d = x[0] * -1108e = (x[0] + x[1]) * x[2]109f = x[0]x[1]110111Lookup table syntax112---------------------------113Suppose we want to specify the function f = x[0] + x[1]*x[2] as a table. First, note that the function is of span 3. Enumerate the values of the function for values of x[0], x[1], and x[2], going through them in lexicographic order as demonstrated below. Notice that incrementing starts at x[2] rather than x[0].1141150 1 2 3 4 5 6 7116x[0] 0 0 0 0 1 1 1 1117x[1] 0 0 1 1 0 0 1 1118x[2] 0 1 0 1 0 1 0 1119f 0 0 0 1 1 1 1 0120121Then the lookup table is "t(3, 0001 1110)". The use of whitespace is not important.122123Commenting out124---------------------------125Lines in the definitions section (after "BEGIN DEFINITIONS" and before "BEGIN COMMANDS") and the commands section (after "BEGIN COMMANDS") can be commented out by preceding them with "//". Commented out lines are completely ignored. In the example Input1.txt, if the last line was replaced with "//func1", the program would not analyze func1.126127Optimizing polynomial functions128---------------------------129Optimizing a polynomial function can be a good way of making the program run faster. To optimize a polynomial function, precede the definition of the function with "OPT" (case-insensitive). In the example Input1.txt, one could replace the definition of A with "opt A = x[0] + x[1] * x[2]". FProbPeriod optimizes the polynomial by precomputing the value of the function for all possible input x[i] values and storing the results in a table. This allows the function to be evaluated very quickly later on.130131It is almost always a good idea to optimize polynomial functions, but there are instances when optimization is inadvisable. Consider the function "opt func2 = x[0] + x[1] + . . . + x[99] + x[100]". This function has 100 distinct x[i]'s. Supposing FPeriod was run with N = 2, precomputing the function would require storing 2^100 values, far more than the capacity of any computer in existence. As a rule of thumb, precomputing and storing up to a million values is probably fine as this would require memory in the range of megabytes or dozens of megabytes. Much more than that is not advised. Also be aware that only the number of distinct x[i]'s is important and not the span. For example, "func3 = x[-1000] + x[1000] + x[1000]^2" has only 2 terms and is easily optimized.132133NOTE: preceding the definition of a lookup table function with "OPT" does nothing.134135136